約瑟夫斯問題

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

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

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

## 歷史

這個問題是以弗拉維奧·約瑟夫斯命名的，他是1世紀的一名猶太歷史學家。他在自己的日記中寫道，他和他的40個戰友被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘，最終決定自殺，並以抽籤的方式決定誰殺掉誰。約瑟夫斯和另外一個人是最後兩個留下的人。約瑟夫斯說服了那個人，他們將向羅馬軍隊投降，不再自殺。約瑟夫斯把他的存活歸因於運氣或天意，他不知道是哪一個。

## 解法

比較簡單的做法是用循環單鍊表模擬整個過程，時間複雜度是O(n*m)。如果只是想求得最後剩下的人，則可以用數學推導的方式得出公式。且先看看模擬過程的解法。

### Python版本

```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++版本

```cpp
#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++）

```cpp
#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 \le n\\ \end{cases}$$

程序實現（C++）

```cpp
#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;
}
```

## 外部連結

- cut-the-knot上的 約瑟夫斯遊戲 （Java Applet）