约瑟夫环问题

参考文章

约瑟夫环之二(用递归的思想解决Josephus问题)

解释

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

解法

初始情况： 0, 1, 2 ......n-2, n-1 (共n个人)

第一个人,编号一定是(m-1)%n（或者写成m%n-1）出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k==m%n的人开始）:

k k+1 k+2 ... n-2, n-1, 0, 1, 2, ...,k-3, k-2

现在我们把他们的编号做一下转换：

x' --> x的情况

k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗！

x ->ｘ＇？(这正是从n-1时的结果反过来推n个人时的编号！)
0 -> k
1 -> k+1
2 -> k+2
...
...
n-2 -> k-2

变回去的公式　x'=(x+k)%n　　　(注：k=m%n)

那么，如何知道(n-1)个人报数的问题的解？只要知道(n-2)个人的解就行了。(n-2)个人的解呢？只要知道(n-3)的情况就可以了 ---- 这显然就是一个递归问题：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果就是f[n]

递推公式

f[1]=0;

f[i]=(f[i-1]+k)%i = (f[i-1] +m%i) % i = (f[i-1] + m) % i ; (i>1)

代码

#include <stdio.h>
int main() {
    int n, m, i, result;
    while (scanf("%d", &n) == 1) {
        if (!n) {
            break;
        }
        scanf("%d", &m);
        result = 0;
        for (i = 2; i <= n; i++) {
            result = (result + m) % i;
        }
        printf("%d\n", result + 1);
    }
    return 0;
}