约瑟夫环问题

n 个人（编号 0 ~ n-1）围成环，从 0 开始报数（最开始从编号 0 开始），报到（m-1）的退出，剩下的人继续从 0 开始报数（从退出的人下一个人开始）。求最后留下来的人的编号。

解法：

• 用数组或者链表模拟整个过程。
• 数学推导。

这里就只写数学推导的方法了。

第一次：从 0 开始报数，(m-1) mod n 出圈。

第二次：从 m mod n 开始报数，假设 k = m mod n，这里形成了新的约瑟夫环 k, k+1, …, n - 1, 0, 1, 2, …, k-2。将编号整体减 k 模 n - 1，得到 0, 1, 2, … , n-2，这又变成了 n-1 个人的约瑟夫环问题了。

由此类推，可以得知约瑟夫环问题存在递推关系。

设 i 个人报 m 个数情况下的胜者编号为 f[i]，可以轻易地得出以下递推关系：

• f[1] = 0
• f[i] = (f[i-1] + m) mod i (i > 1)

于是便可以容易地编写出代码了。

1
2
3
4
5
6
7
8
9
10
11

int Josephus(int n, int m)
    {
        if (m < 0 || n < 1)
            return -1;
        int* f = new int[n + 1];
        f[1] = 0;
        for (int i = 2; i <= n; i++) 
            f[i] = (f[i - 1] + m) % i;
        delete[] f;
        return f[n];
    }