约瑟夫斯问题

约瑟夫斯问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

有$n$个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过$k-2$个人，并杀掉第k个人。接着，再越过$k-1$个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

问题是，给定了$n$和$k$，一开始要站在什么地方才能避免被处决？

历史

这个问题是以弗拉维奥·约瑟夫斯命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

解法

我们将明确解出$k=2$时的问题。对于$k\neq 2$的情况，我们在下面给出一个一般的解法。

设$f(n)$为一开始有$n$个人时，生还者的位置。走了一圈以后，所有偶数号码的人被杀。再走第二圈，则新的第二、第四、……个人被杀，等等；就像没有第一圈一样。如果一开始有偶数个人，则第二圈时位置为$x$的人一开始在第$2x - 1$个位置。因此位置为$f(2n)$的人开始时的位置为$2f(n) - 1$。这便给出了以下的递推公式：

$f(2n)=2f(n)-1.\,$

如果一开始有奇数个人，则走了一圈以后，最终是号码为1的人被杀。于是同样地，再走第二圈时，新的第二、第四、……个人被杀，等等。在这种情况下，位置为$x$的人原先位置为$2x+1$。这便给出了以下的递推公式：

$f(2n+1)=2f(n)+1.\,$

如果我们把$n$和$f(n)$的值列成表，我们可以看出一个规律：

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$f(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

从中可以看出，$f(n)$是一个递增的奇数数列，每当n是2的幂时，便重新从$f(n)=1$开始。因此，如果我们选择m和l，使得$n=2^m+l$且$0\leq l<2^m$，那么$f(n)=2 \cdot l+1$。显然，表格中的值满足这个方程。我们用数学归纳法给出一个证明。

定理：如果$n=2^m+l$且$0\leq l<2^m$，则$f(n) = 2l+1$。

证明：对$n$应用数学归纳法。$n=1$的情况显然成立。我们分别考虑$n$是偶数和$n$是奇数的情况。

如果$n$是偶数，则我们选择$l_1$和$m_1$，使得$n/2 = 2^{m_1}+l_1$，且$0\leq l_1 < 2^{m_1}$。注意$l_1 = l/2$。我们有$f(n) = 2f(n/2)-1=2((2l_1)+1) - 1=2l+1$，其中第二个等式从归纳假设推出。

如果$n$是奇数，则我们选择$l_1$和$m_1$，使得$(n-1)/2 = 2^{m_1}+l_1$，且$0\leq l_1 < 2^{m_1}$。注意$l_1 = (l-1)/2$。我们有$f(n) = 2f((n-1)/2)+1=2((2l_1)+1) + 1=2l+1$，其中第二个等式从归纳假设推出。证毕。

答案的最漂亮的形式，与$n$的二进制表示有关：把$n$的第一位移动到最后，便得到$f(n)$。如果$n$的二进制表示为$n=b_0 b_1 b_2 b_3\dots b_m$，则$f(n)=b_1 b_2 b_3 \dots b_m b_0$。这可以通过把$n$表示为$2^m+l$来证明。

在一般情况下，这个问题的最简单的解决方法是使用动态规划。利用这种方法，我们可以得到以下的递推公式：

$f(n,k)=(f(n-1,k)+k) \bmod n$，$f(1,k)=0$

如果考虑生还者的号码从$n-1$到$n$是怎样变化的，则这个公式是明显的。这种方法的运行时间是$O(n)$，但对于较小的$k$和较大的$n$，有另外一种方法，这种方法也用到了动态规划，但运行时间为$O(k\log n)$。它是基于把杀掉第k、2k、……、2$\lfloor n/k \rfloor$个人视为一个步骤，然后把号码改变。

参考文献

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 14: Augmenting Data Structures, pp.318.

外部链接

• cut-the-knot上的约瑟夫斯游戏（Java Applet）
• Eric W. Weisstein, 约瑟夫斯问题, MathWorld.