约瑟夫斯问题

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

问题是,给定了nk,一开始要站在什么地方才能避免被处决?

历史[编辑]

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

解法[编辑]

我们将明确解出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.\,

如果我们把nf(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+l0\leq l<2^m,那么f(n)=2 \cdot l+1。显然,表格中的值满足这个方程。我们用数学归纳法给出一个证明。

定理:如果n=2^m+l0\leq l<2^m,则f(n) = 2l+1

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

如果n是偶数,则我们选择l_1m_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_1m_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 nf(1,k)=0

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

注释[编辑]

  1. ^ The War of the Jews 3.387-391

参考文献[编辑]

外部链接[编辑]