经典算法：从约瑟夫问题(Josephus problem)说开去...
By Long Luo
约瑟夫问题( \(\textit{Josephus Problem}\) )是每个学计算机的同学都会遇到的经典编程题，可以考察链表、递归、数学等知识，下面我们就来通过这道题对好好学习下算法和编程吧，Let’s go!
一、什么是约瑟夫问题？
据说著名犹太历史学家 \(\textit{Josephus}\) 有过以下的故事：
在罗马人占领乔塔帕特后，\(39\) 个犹太人与 \(\textit{Josephus}\) 及他的朋友躲到一个洞中，\(39\) 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，\(41\) 个人排成一个圆圈，由第 \(1\) 个人开始报数，每报数到第 \(3\) 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
然而 \(\textit{Josephus}\) 和他的朋友并不想遵从这个规则，\(\textit{Josephus}\) 要他的朋友先假装遵从，他将朋友与自己安排在第 \(16\) 个与第 \(31\) 个位置，于是逃过了这场死亡游戏。
二、约瑟夫问题算法分析
约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与 \(N\) 个朋友不幸参与了这个游戏，您要如何保护您与您的朋友？
只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆圈内圈是排列顺序，而外圈是自杀顺序，如下图所示：
假如使用编程来求解的话，只要将 \(\textit{array}\) 当作环状来处理就可以了，在 \(\textit{array}\) 中由计数 \(1\) 开始，每找到 \(3\) 个无数据区就填入 \(1\) 个计数，直到计数达 \(41\) 为止，然后将 \(\textit{array}\) 由索引 \(1\) 开始列出，就可以得知每个位置的自杀顺序，这就是约瑟夫排列，\(41\) 个人而报数 \(3\) 的约琴夫排列如下所示：
14 36 1 38 15 2 24 30 3 16 34 425 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23
由上可知，最后一个自杀的是在第 \(31\) 个位置，而倒数第二个自杀的要排在第 \(16\) 个位置，而之前的人都死光了，所以他们也就不知道约瑟夫与他的朋友并没有遵守游戏规则了。
这是一道经典算法问题，每个学编程的同学都会遇到。一般常见的问法有以下几种：
- 输出自杀顺序；
- 输出最后一个自杀同学编号。
下面我们就来动手实践下，具体实现代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31private static int Josephus(int n, int m) {
int[] peopleArr = new int[n];
for (int i = 0; i < n; i++) {
peopleArr[i] = i + 1;
}
int index = 0;
int length = n;
int count = 1;
while (length > 0) {
if (peopleArr[index % n] > 0) {
if (count % m == 0) {
// 找到要出圈的人，并把圈中人数减1
System.out.print(peopleArr[index % n] + " ");
peopleArr[index % n] = -1;
count = 1;
index++;
length--;
} else {
index++;
count++;
}
} else {
// 遇到空位了，就跳到下一位，但count不加1，也就是这个位置没有报数
index++;
}
}
return index;
}
三、递归实现
这道题也可以使用递归来实现，原理如下：
令 \(f_n\) 表示当有 \(n\) 个候选人时，最后当选者的编号。则：
递归结束条件，\(f_1 = 0\)；
\(f_n \equiv (f_{n - 1} + K) \quad mod \quad n\)
方法证明：
上述公式可以用数据归纳法简单证明其正确性：
\(f_1= 0\)，当只有一个候选人的时候，显然结果应该是 \(0\)；
\(f_n = (f_{n - 1} + K) \mod n\)，\(f_{n - 1}\) 为第 \(n - 1\) 次数到的 \(id\) 序列，则第n次就是再往下数 \(k\) 个，最后进行取模运算即可得到结果序列。
这种算法的时间复杂度为 \(O(N)\) ，空间复杂度为 \(O(1)\) ，效率有所提高！
以 \(n = 5\)，\(m = 3\) 为例，一开始有这么 \(5\) 个人：
0 1 2 3 4第一轮报数后 \(2\) 号死亡，圈子里剩下来的人的编号是这些：
3 4 0 1这里把 \(3\) 号写在最前面了，因为轮到 \(3\) 开始报数。如果我们有办法知道 \(n = 4\) 时的答案，即初始圈子为：
0 1 2 3时的答案，那么可以把 \(n = 4\) 的初始圈子的所有数x变换成 \((x + 3) \mod 5\)，得到：
3 4 0 1这个恰好就是 \(n = 5\) 时第一轮结束后的圈子状态，也就是说我们可以根据 \(n = 4\) 的答案推出 \(n = 5\) 时的答案。
归纳如下：
设 \(f_n\) 为初始有 \(n\) 人时最后一个自杀的人的编号，那么有如下递推式：
\[ f_n = (f_{n - 1} + m) \mod n \]
手工演算一下就能发现 \(n = z\) 时的圈子第一轮结束后(即 \(m - 1\) 号自杀后)的圈子状态，可以由 \(n = z - 1\) 的初始圈子施以变换 \(x \to (x + m) \mod z\) 得到。于是我们可以从 \(n=1\) 开始(此时的答案是 \(0\) )，推出 \(n = 2\) 的答案，再推出 \(n = 3\) ，直到计算到所要求的 \(n\) 。
下面为具体实现：1
2
3
4
5
6
7
8private static int Josephus(int n, int m) {
int s = 0;
for (int i = 2; i <= n; i++) {
s = (s + m) % i;
}
return s;
}
四、扩展
假如有 \(k\) 个好人，和 \(k\) 个坏人，所有人站成一圈，前 \(k\) 个人是好人，后 \(k\) 个人是坏人， 编写程序计算一个最小的 \(m\) ，使 \(k\) 个坏人都被处决，而不处决任何好人。
输入: \(k\) 为正整数
输出: 返回: 最小的 \(m\) ，使 \(k\) 个坏人都被处决，而不处决任何好人。
算法及代码实现如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public static int getMinimumM(int K) {
/* 在这里实现功能 */
int m = K + 1;
while (true) {
int index = 0;
int size = 2 * K;
while (true) {
index = (index + m - 1) % size;
if (index < K) {
break;
}
size--;
}
if (size == K) {
return m;
}
m++;
}
}
五、实践
Leetcode上面有几道题目就是关于约瑟夫问题及其变形：
以上。
修改历史
v1.0 By Long Luo at Shenzhen 19th, Aug, 2019. v1.1 By Long Luo at Shenzhen 2022年5月1日10点20分. v2.0 By Long Luo at Shenzhen 2023年07月05日