查看“︁约瑟夫斯问题”︁的源代码

{{NoteTA
|G1= IT
|T = zh-hant:約瑟夫問題; zh-hans:约瑟夫问题;
|1 = zh-hant:約瑟夫問題; zh-hans:约瑟夫问题; 
}}
'''約瑟夫斯置換'''是一個出現在[[計算機科學]]和[[數學]]中的問題。在計算機[[編程]]的算法中，類似問題又被稱為'''約瑟夫環'''。

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

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

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

== 解法 ==
比较简单的做法是用[[循环链表|循环单链表]]模拟整个过程，时间复杂度是O(n*m)。如果只是想求得最后剩下的人，则可以用数学推导的方式得出公式。且先看看模拟过程的解法。
=== Python版本 ===
<syntaxhighlight lang=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)

</syntaxhighlight>

=== C++版本 ===
<syntaxhighlight lang=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;
}
</syntaxhighlight>

== 数学推导解法 ==
我们将明确解出<math>k=2</math>时的问题。对于<math>k\neq 2</math>的情况，我们在下面给出一个一般的解法。

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

: <math>f(2n)=2f(n)-1.\,</math>

如果一开始有奇数个人，则走了一圈以后，最终是号码为1的人被杀。于是同样地，再走第二圈时，新的第二、第四、……个人被杀，等等。在这种情况下，位置为<math>x</math>的人原先位置为<math>2x+1</math>。这便给出了以下的递推公式：

:<math>f(2n+1)=2f(n)+1.\,</math>

如果我们把<math>n</math>和<math>f(n)</math>的值列成表，我们可以看出一个规律：

{|
|<math>n</math> || 1  || 2  || 3  || 4  || 5  || 6  || 7  || 8  || 9  || 10 || 11 || 12 || 13 || 14 || 15 || 16
|-
|<math>f(n)</math> || 1  || 1  || 3  || 1  || 3  || 5  || 7  || 1  || 3  || 5 || 7 || 9 || 11 || 13 || 15 || 1
|}

从中可以看出，<math>f(n)</math>是一个递增的奇数数列，每当''n''是2的幂时，便重新从<math>f(n)=1</math>开始。因此，如果我们选择m和l，使得<math>n=2^m+l</math>且<math>0\leq l<2^m</math>，那么<math>f(n)=2 \cdot l+1</math>。注意：2^m是不超过n的最大幂，l是留下的量。显然，表格中的值满足这个方程。我们用数学归纳法给出一个证明。

'''定理：'''如果<math>n=2^m+l</math>且<math>0\leq l<2^m</math>，则<math>f(n) = 2l+1</math>。

'''证明：'''对<math>n</math>应用[[数学归纳法]]。<math>n=1</math>的情况显然成立。我们分别考虑<math>n</math>是偶数和<math>n</math>是奇数的情况。

如果<math>n</math>是偶数，则我们选择<math>l_1</math>和<math>m_1</math>，使得<math>n/2 = 2^{m_1}+l_1</math>，且<math>0\leq l_1 < 2^{m_1}</math>。注意<math>l_1 = l/2</math>。我们有<math>f(n) = 2f(n/2)-1=2((2l_1)+1) - 1=2l+1</math>，其中第二个等式从归纳假设推出。

如果<math>n</math>是奇数，则我们选择<math>l_1</math>和<math>m_1</math>，使得<math>(n-1)/2 = 2^{m_1}+l_1</math>，且<math>0\leq l_1 < 2^{m_1}</math>。注意<math>l_1 = (l-1)/2</math>。我们有<math>f(n) = 2f((n-1)/2)+1=2((2l_1)+1) + 1=2l+1</math>，其中第二个等式从归纳假设推出。证毕。

答案的最漂亮的形式，与<math>n</math>的二进制表示有关：把<math>n</math>的第一位移动到最后，便得到<math>f(n)</math>。如果<math>n</math>的二进制表示为<math>n=b_0 b_1 b_2 b_3\dots b_m</math>，则<math>f(n)=b_1 b_2 b_3 \dots b_m b_0</math>。这可以通过把<math>n</math>表示为<math>2^m+l</math>来证明。

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

<math>f(n,k)=(f(n-1,k)+k) \bmod n</math>，<math>f(1,k)=0</math>

这种方法的[[大O符号|运行时间]]是<math>O(n)</math>。

程序實現（C++）
<syntaxhighlight lang=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;
}
</syntaxhighlight>

对于<math>k<n</math>，可以将上述方法推广，将杀掉第''k''、''2k''、……、<math>\lfloor n/k \rfloor</math>个人视为一个步骤，然后把号码改变，可得如下递推公式, 运行时间为<math>O(k\log n)</math>。
:<math>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} </math>
程序實現（C++）

<syntaxhighlight lang=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;
}
</syntaxhighlight>

== 注释 ==
{{reflist|2}}

== 参考文献 ==
* [[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]]上的[http://www.cut-the-knot.org/recurrence/flavius.shtml 约瑟夫斯游戏] {{Wayback|url=http://www.cut-the-knot.org/recurrence/flavius.shtml |date=20210426050702 }}（Java Applet）
* {{MathWorld|urlname=JosephusProblem|title=约瑟夫斯问题}}

[[Category:组合数学]]
[[Category:置换]]
[[Category:计算机科学基础理论]]
[[Category:数学问题]]