約瑟夫問題

約瑟夫斯置換是一個出現在計算機科學和數學中的問題。在計算機編程的算法中，類似問題又被稱為約瑟夫環。

人們站在一個等待被處決的圈子裡。計數從圓圈中的指定點開始，並沿指定方向圍繞圓圈進行。在跳過指定數量的人之後，處刑下一個人。對剩下的人重複該過程，從下一個人開始，朝同一方向跳過相同數量的人，直到只剩下一個人，並被釋放。

問題即，給定人數、起點、方向和要跳過的數字，選擇初始圓圈中的位置以避免被處決。

歷史

這個問題是以弗拉維奧·約瑟夫斯命名的，他是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>
#include <cstdlib>
#include <cstdio>

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("%d\n", 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() {
        if (argc < 3) return -1;
	run(atoi(argv[1]), atoi(argv[2]));
	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() {
    int n, k;
	while (scanf("%d%d", &n, &k) == 2)
		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]