Joseph_Ring
@ | Monday, May 31, 2021 | 2 minute read | Update at Monday, May 31, 2021

证明过程尽量写的简洁、易懂,参考自文章:这或许是你能找到的最详细约瑟夫环数学推导!

约瑟夫环问题是一个数学问题。我们定义一个函数f(n, k)表示:在n个人围成的环中,从1开始数,数到k的人被杀掉,然后接着从1开始数,直到只剩下一个人,幸存者的编号就是f(n, k)。

1、 假设我们把n个人从0开始编号,分别为0, 1, 2, …, n-2, n-1;

2、 那么很明显,我们的函数有一个最基本的值,就是f(1, k) = 0;

3、 第一个被淘汰的数字肯定是编号为(k-1)%n的数,那么剩余的序列为0, 1, 2, 3, …, k-3, k-2, k, k+1

4、 换句话说,要从编号为k的人重新开始数,即转化为n-1个人的约瑟夫环问题(过程是递归的,所以肯定有递归式),只不过序列从0, 1, 2, …, n-1变成了新序列k, k+1, k+2, …, n-1, 0, 1, 2, …, k-2。

5、 因为这个序列不同于从0开始编号,所以f(n, k)已经不适用于新序列,故建立新函数L(n – 1, k)表示从k开始编号的n-1个人的约瑟夫环的解。由于新序列其实是原先序列的子问题,所以L(n – 1, k)的解与f(n, k)的解是同一个序号,即L(n – 1, k) = f(n, k)。

6、 可是两个函数不同,无法建立递归式,所以我们需要建立一个在两个序列之间转化的映射,以求把L(n – 1, k)转化f(n – 1, k)的类型:

k -> 0 k + 1 -> 1 … n - 1 -> n – k - 1 0 -> n - k 1 -> n – k + 1 … k - 2 -> n - 2

7、 观察上面的映射可以发现,我们可以用一个函数g(x) = ( x + n – k ) % n来表示从左到右的映射。反过来,如果需要从右边到左边的映射,那么可以用h(x) = ( x + k) % n。

8、 那么在映射之后进行操作的约瑟夫环就有:

f(n – 1, k) = g( L(n – 1, k) ) 所以: L(n – 1, k) = g-1( f(n - 1, k) ) = h( f(n - 1, k) ) = [ f(n – 1, k) + k ] % n

9、 很好,又因为5中我们已经解释过L(n – 1, k) = f(n, k),那么递归公式就已经得到了:

f(n, k) = [ f(n – 1, k) + k ] % n f(1, k) = 0

可以,递归式有了,那么这道题就已经解决了,代码用循环就可以简单的写出来了:

#include <iostream>
using namespace std;

int main()
{
    int T, n, k, ans;
    cin>>T;//样例数
    int temp = T;
    while(T--){
        cin>>n>>k;//n个人,从1数到k
        ans = 0;
        for(int i = 2; i <= n; ++i){
            ans = (ans + k)%i;//利用f(n, k) = [ f(n – 1, k) + k ] % n
        }
        cout<<"Case "<<temp-T<<": "<<ans+1<<endl;
    }
    return 0;
}

Social Links