约瑟夫斯问题

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

人们站在一个等待被处决的圈子里。计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。在跳过指定数量的人之后，执行下一个人。对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。

问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

历史

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

解法

比较简单的做法是用循环单链表模拟整个过程，时间复杂度是O(n*m)。如果只是想求得最后剩下的人，则可以用数学推导的方式得出公式。且先看看模拟过程的解法。

Python版本

# -*- coding: utf-8 -*- 
class Node(object):
	def __init__(self, value):
		self.value = value 
		self.next = None

def create_linkList(n):
	head = Node(1)
	pre = head
	for i in range(2, n+1):
		newNode = Node(i)
		pre.next= newNode
		pre = newNode
	pre.next = head
	return head

n = 5 #总的个数
m = 2 #数的数目
if m == 1: #如果是1的话，特殊处理，直接输出
	print (n)  
else:
	head = create_linkList(n)
	pre = None
	cur = head
	while cur.next != cur: #终止条件是节点的下一个节点指向本身
		for i in range(m-1):
			pre =  cur
			cur = cur.next
		print (cur.value)
		pre.next = cur.next
		cur.next = None
		cur = pre.next
	print (cur.value)

C++版本

#include <iostream>
using namespace std;
typedef struct _LinkNode {
	int value;
	struct _LinkNode* next;
} LinkNode, *LinkNodePtr;

LinkNodePtr createCycle(int total) {
	int index = 1;
	LinkNodePtr head = NULL, curr = NULL, prev = NULL;
	head = (LinkNodePtr) malloc(sizeof(LinkNode));
	head->value = index;
	prev = head;

	while (--total > 0) {
		curr = (LinkNodePtr) malloc(sizeof(LinkNode));
		curr->value = ++index;
		prev->next = curr;
		prev = curr;
	}
	curr->next = head;
	return head;
}

void run(int total, int tag) {
	LinkNodePtr node = createCycle(total);
	LinkNodePtr prev = NULL;
	int start = 1;
	int index = start;
	while (node && node->next) {
		if (index == tag) {
			printf("\n%d", node->value);
			if (tag == start) {
				prev = node->next;
				node->next = NULL;
				node = prev;
			} else {
				prev->next = node->next;
				node->next = NULL;
				node = prev->next;
			}
			index = start;
		} else {
			prev = node;
			node = node->next;
			index++;
		}
	}
}
int main() {
	run(5, 999999);
	return 0;
}

数学推导解法

我们将明确解出 $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$ 。注意：2^m是不超过n的最大幂，l是留下的量。显然，表格中的值满足这个方程。我们用数学归纳法给出一个证明。

定理：如果 $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$ 来证明。

一般情况下，考虑生还者的号码从 $n-1$ 到 $n$ 的变化, 我们可以得到以下的递推公式(编号从0开始)：

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

这种方法的运行时间是 $O(n)$ 。

程序實現（C++）

#include <iostream>
using namespace std;
//編號從0開始，也就是說如果編號從1開始結果要加1
int josephus(int n, int k) { //非遞回版本
	int s = 0;
	for (int i = 2; i <= n; i++)
		s = (s + k) % i;
	return s;
}
int josephus_recursion(int n, int k) { //遞回版本
	return n > 1 ? (josephus_recursion(n - 1, k) + k) % n : 0;
}
int main() {
	for (int i = 1; i <= 100; i++)
		cout << i << ' ' << josephus(i, 5) << ' ' << josephus_recursion(i, 5) << endl;
	return 0;
}

对于 $k<n$ ，可以将上述方法推广，将杀掉第k、2k、……、 $\lfloor n/k\rfloor$ 个人视为一个步骤，然后把号码改变，可得如下递推公式, 运行时间为 $O(k\log n)$ 。

f(n,k)={\begin{cases}0&{\text{if }}n=1\\(f(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\\left\lfloor {\frac {k((f(n',k)-n{\bmod {k}}){\bmod {n}}')}{k-1}}\right\rfloor {\text{where }}n'=n-\left\lfloor {\frac {n}{k}}\right\rfloor &{\text{if }}k\leq n\\\end{cases}}

程序實現（C++）

#include <cstdio>
using namespace std;
//編號從1開始，結果要加1
int josephus(int n, int k) { 
    if (k==1) return n-1;
    int ans=0;
    for (int i=2;i<=n;)
    {
	if (ans+k>=i)
	{
	     ans=(ans+k)%i;
	     i++;
	     continue;
	}
	int Step=(i-1-ans-1)/(k-1);//向下取整
	if (i+Step>n) 
	{
	    ans+=(n-(i-1))*k;break;
	}
	i+=Step;ans+=Step*k;
    }
    return ans;
}

int main() {
	while (~scanf("%d%d",&n,&k)
            printf("%d\n",josephus(n,k)%n+1);
	return 0;
}

注释

^ The War of the Jews 3.387-391

参考文献

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）
埃里克·韦斯坦因. 约瑟夫斯问题. MathWorld.

[1] The War of the Jews 3.387-391

[1]