经典算法:从约瑟夫问题(Josephus problem)说开去...
By Long Luo
约瑟夫问题(Josephus problem) [1] 是每个学计算机的同学都会遇到的经典编程题,可以考察链表、递归、数学等知识,下面我们就来通过这道题对好好学习下算法和编程吧,Let’s go!
一、约瑟夫问题
据说著名犹太历史学家 有过以下的故事:
在罗马人占领乔塔帕特后, 个犹太人与 及他的朋友躲到一个洞中, 个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式, 个人排成一个圆圈,由第 个人开始报数,每报数到第 人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。
然而 和他的朋友并不想遵从这个规则, 要他的朋友先假装遵从,他将朋友与自己安排在第 个与第 个位置,于是逃过了这场死亡游戏。
二、约瑟夫问题算法分析
约瑟夫问题可用代数分析来求解,将这个问题扩大好了,假设现在您与 个朋友不幸参与了这个游戏,您要如何保护您与您的朋友?
只要画两个圆圈就可以让自己与朋友免于死亡游戏,这两个圆圈内圈是排列顺序,而外圈是自杀顺序,如下图所示:
假如使用编程来求解的话,只要将 当作环状来处理就可以了,在 中由计数 开始,每找到 个无数据区就填入 个计数,直到计数达 为止,然后将 由索引 开始列出,就可以得知每个位置的自杀顺序,这就是约瑟夫排列, 个人而报数 的约琴夫排列如下所示:
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
由上可知,最后一个自杀的是在第 个位置,而倒数第二个自杀的要排在第 个位置,而之前的人都死光了,所以他们也就不知道约瑟夫与他的朋友并没有遵守游戏规则了。
这是一道经典算法问题,每个学编程的同学都会遇到。一般常见的问法有以下几种:
- 输出自杀顺序;
- 输出最后一个自杀同学编号。
下面我们就来动手实践下,具体实现代码如下所示:
1 | private static int Josephus(int n, int m) { |
三、递归实现
这道题也可以使用递归来实现,原理如下:
令 表示当有 个候选人时,最后当选者的编号。则:
-
递归结束条件,;
-
方法证明:
上述公式可以用数据归纳法简单证明其正确性:
-
,当只有一个候选人的时候,显然结果应该是 ;
-
, 为第 次数到的 序列,则第n次就是再往下数 个,最后进行取模运算即可得到结果序列。
这种算法的时间复杂度为 ,空间复杂度为 ,效率有所提高!
以 , 为例,一开始有这么 个人:
0 1 2 3 4
第一轮报数后 号死亡,圈子里剩下来的人的编号是这些:
3 4 0 1
这里把 号写在最前面了,因为轮到 开始报数。如果我们有办法知道 时的答案,即初始圈子为:
0 1 2 3
时的答案,那么可以把 的初始圈子的所有数x变换成 ,得到:
3 4 0 1
这个恰好就是 时第一轮结束后的圈子状态,也就是说我们可以根据 的答案推出 时的答案。
归纳如下:
设 为初始有 人时最后一个自杀的人的编号,那么有如下递推式:
手工演算一下就能发现 时的圈子第一轮结束后(即 号自杀后)的圈子状态,可以由 的初始圈子施以变换 得到。于是我们可以从 开始(此时的答案是 ),推出 的答案,再推出 ,直到计算到所要求的 。
下面为具体实现:
1 | private static int Josephus(int n, int m) { |
四、扩展
假如有 个好人,和 个坏人,所有人站成一圈,前 个人是好人,后 个人是坏人, 编写程序计算一个最小的 ,使 个坏人都被处决,而不处决任何好人。
输入:
为正整数
输出:
返回: 最小的 ,使 个坏人都被处决,而不处决任何好人。
算法及代码实现如下:
1 | public static int getMinimumM(int K) { |
五、实践
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日