经典算法：从约瑟夫问题(Josephus problem)说开去...

By Long Luo

约瑟夫问题(Josephus problem) ^[1] 是每个学计算机的同学都会遇到的经典编程题，可以考察链表、递归、数学等知识，下面我们就来通过这道题对好好学习下算法和编程吧，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. 输出最后一个自杀同学编号。

下面我们就来动手实践下，具体实现代码如下所示：

private 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$ 个候选人时，最后当选者的编号。则：

1. 递归结束条件，$f_1 = 0$；

2. $f_n \equiv (f_{n - 1} + K) \quad mod \quad n$

方法证明：

上述公式可以用数据归纳法简单证明其正确性：

1. $f_1= 0$，当只有一个候选人的时候，显然结果应该是 $0$；

2. $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$ 。

下面为具体实现：

private 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$ 个坏人都被处决，而不处决任何好人。

算法及代码实现如下：

public 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上面有几道题目就是关于约瑟夫问题及其变形：

剑指 Offer 62. 圆圈中最后剩下的数字

390. 消除游戏

以上。

修改历史

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日

参考资料

---

1. 1823. Find the Winner of the Circular Game
   
   ](https://www.exploringbinary.com/powers-of-two-in-the-josephus-problem/) ↩︎