约瑟夫问题

约瑟夫问题

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

举个例子：

有64名战士被敌人俘虏了。敌人命令他们拍成一圆圈，编上号码1，2，3…，64。敌人把1号杀了，又把3号杀了，他们隔着一个杀一个这样转着圈杀。最后只剩下一个人，这个人就是约瑟夫斯。请问约瑟夫斯是多少号？（这就是“约瑟夫斯”问题。）

这个问题解答起来比较简单：敌人从1号开始，隔一个杀一个，第一圈把所有的奇数号码的战士圈杀光了。剩下的32名战士需要重新编号，而敌人在第二圈杀死的是重新编号的奇数号码。

由于第一圈剩下的全部是偶数号2，4，6，…，64。把它们全部用2去除，得1，2，3，…，32。这是第二圈编的号码。第二圈杀过以后，又把奇数号码都杀掉了，还剩16个人。如此下去，可以想到最后剩下的必然是64号。

$64=2^6$，它可以连续被2整除6次，是从1到64中能被2整除次数最多的数，因此，最后必然把64 号留下。

如果有65名战士被俘，敌人还是按上述的方法残杀战士，最后还会剩下约瑟夫斯吗？

经过计算，很容易得到结论，不是。因为第一个人被杀后，也就是1号被杀后，第二个被杀的是必然3号。如果把1号排除在外，那么还剩下的仍是64人，新1号就是3号。这样原来的2号就变成了新的64 号，所以剩下的必然是2号。

进一步的归类，不难发现如果原来有$2^k$个人，最后剩下的必然$2^k$号；如果原来有$2^k+1$个人，最后剩下2号；如果原来有$2^k+2$个人，最后剩下4号……如果原来有$2^k+m$个人，最后剩下2m号.

比如：原来有100人，由于$100=64+36=2^6+36$，所以最后剩下的就是36×2=72号；又如：原来有111人，由于$100=64+47=2^6+47$，所以最后剩下的就是47×2=94号

传说古代有一批人被蛮族俘虏了，敌人命令他们排成圆圈，编上号码1，2，3，…然后把1号杀了，把3号杀了，总之每隔一个人杀一个人，最后剩下一个人，这个人就是约瑟夫斯。你能知道约瑟夫斯的号码是多少吗？

这个问题与上一节的问题有些类似，又有所不同。上一节是排成一列，报了一次又一次，这次是排成圆圈，数了一圈又一圈。

要是人数是2的幂，比如说是64，这时和上一节的问题有什么关系？

第一圈数过去，留下的是偶数；然后从2开始再数一圈，留下的是4的倍数。这样继

续下去，留下的是64。

啊。要是把这个圆圈在64与1之间剪开，拉成一条直线，那这个问题，实际上和上一节的问题完全一样。

对。这样的推理，适用于2的任意次幂——2k，k是正整数。在人数为2k时，约瑟夫斯的编号是2k。

人数不是2的幂呢？

我们可以认为人数n满足2k＜n≤2k+1。然后，考虑最简单的情况n＝2k+1，看看它和人数为2k的情况有什么关系。

知道了。在1号被杀死后，人数就变成2k了。

问题是在这2k个人中，第一个被杀的是几号？最后留下的是几号？

第一个被杀的当然是3号，最后留下的应当是2号。因为这时3号是第一个人，2号就是第2k个人。

现在，再考虑一下从n-1个人进到n个人。也就是说，人数是n-1时，最后留下的是X号，那人数是n时，最后留下的是谁？

在第一个人——1号被杀后，人数就变成n-1了。

在这n-1个人中，因为第一个被杀的是3号，所以最后留下的应当是x＋2号。看起

来，每增加一个人，最后留下的人的号数就增加2，是可以导出一个公式来的。2k+1个人，最后留下2号；2k+2个人，最后留下4号，依此类推，2k＋m个人，最后留下的是2m号。对吗？

对。换句话说，要是人数是n，2k＜n≤2k+1，那最后留下的就是2（n-2k）号。

与约瑟夫斯问题类似的问题很多。例如：

一、50枚棋子围成圆圈，编上号码1，2，3，…每隔一枚棋子取出一枚，要求最后留下的一枚棋子的号码是42，那该从几号棋子开始取呢？

二、41枚棋子围成圆圈，编上号码1，2，3，…沿圆圈自1开始，每数三枚棋子，就取出第3枚棋子，这样陆续取出1，4，7，…问最后留下的是第几枚？

三、用1到6摆成一个圆圈如图。先取1，然后每数k枚棋子就取出第k枚棋子。要是取出的顺序刚好是1，2，3，4，5，6。问k＝？

约瑟夫斯是公元1世纪的犹太历史学家，他领导了反抗罗马人的武装起义，

但是失败了。他和四十名犹太士兵被罗马人围困在一个山洞中。这四十个士兵

宁死不屈，决定杀身成仁。但约瑟夫斯不是这样想，但又不便公开反对，于是

提出一个方法，就是四十一个人站成一个圈，从某人开始数起，凡数到三的人

就让大家成全他升天，这样下去直到剩下最后一个人，这个人就自杀。大家都

没有意见，于是约瑟夫斯就挑选了第31号的位置。结果所有人都死了，剩下他

一个活下来投降了罗马人。这也是约瑟夫斯问题的最初提法。

而约瑟夫斯问题的一般提法是这样的：设有n个人，以1、2、……、n编号，

按编号顺序排列，并且围成一圈，从1号开始，每数到m就淘汰一人，则最后淘

汰的人是几好呢？

令L(n,m)为上述最后被淘汰的人的号码，于是就可以将约瑟夫斯问题最初

提法写成L(41,3)＝31。对于具体不同的n，m最好能有一个计算公式。当m＝2时

公式是有的L(n,2)＝2b＋1。

a

其中b是这样得出的，我们把n写成2 ＋b，而a必须尽可能大，例如当n等于100，

5 6 7

则100可以写成2 ＋68，也可以写成2 ＋36，但是不能再写成2 的了，所以，a

是6，而b就是36。

m＝2的情况如是，那么如果m＝3、4、……呢？有没有公式呢？这个不知道，

反正到现在还没有人找到。但存在一个递推式对任意n，m求出L(n,m)：

L(1,m)＝1

L(k＋1,m)≡L(k,m)＋m(mod n+1)

这里“≡”为同余符号，表示L(k＋1,m)与L(k,m)＋m除以n＋1同余数。

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

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

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

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

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

如果一开始有奇数个人，则走了一圈以后，最终是号码为1的人被杀。于是同样地，

再走第二圈时，新的第二、第四、……个人被杀，等等。在这种情况下，位置为x的人原先位置为2x + 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 = 2m + l且，那么。显然，表格中的值满足这个方程。我们用数学归纳法给出一个证明。

定理：如果n = 2m + l且，则f(n) = 2l + 1。

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

如果n是偶数，则我们选择l1和m1，使得，且。注意l1 = l / 2。我们有f(n) = 2f(n / 2) − 1 = 2((2l1) + 1) − 1 = 2l + 1，其中第二个等式从归纳假设推出。

如果n是奇数，则我们选择l1和m1，使得，且。注意l1 = (l − 1) / 2。我们有f(n) = 2f((n − 1) / 2) + 1 = 2((2l1) + 1) + 1 = 2l + 1，其中第二个等式从归纳假设推出。证毕。

答案的最漂亮的形式，与n的二进制表示有关：把n的第一位移动到最后，便得到f(n)。

如果n的二进制表示为，则。这可以通过把n表示为2m + l来证明。

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

f(n,k) = (f(n − 1,k) + k)mod n，f(1,k) = 0

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