Python对约瑟夫问题(Josephus Problem)的高效解决方法

Made by Mike_Zhang

数据结构与算法主题：

1.约瑟夫问题引入

约瑟夫问题由来

先看一下百度百科对约瑟夫问题的介绍：

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。(来自百度百科-约瑟夫问题)

实际问题案例
以下问题来自我的一个作业，经过改编：
There are n people sitting around a circle, and all are numbered from 1 to n. Starting from the first person, they count from 1 to m and the one who counts m will be eliminated. The process will be started again from the next person until all people are eliminated. Your task now is to write a program to derive the order of the elimination for given n and m. That is, your program should ask the user to input integers n and m, and then print the sequence of elimination on screen.

翻译如下：

一圈有n个人坐着，所有人从1到n编号，从第一个人开始，他们从1数到m，数到m的人将被淘汰。这个过程将从下一个人重新开始，直到所有人都被淘汰。现在的任务是编写一个程序，根据给定的n和m来推导淘汰的顺序。也就是说，程序应该要求用户输入整数n和m，然后在屏幕上输出淘汰的顺序。

举例：
总人数n=5，数到m=2

第一轮：(从1开始数)
1 2 3 4 5 （淘汰：2, 4）
第二轮:（上次淘汰为4号，则从5号开始数，5号数完回到1号）
1 3 5 （淘汰：2, 4, 1, 5）
第三轮：
3 （淘汰：2, 4, 1, 5, 3）
结束

所以，最后淘汰顺序为2, 4, 1, 5, 3

现在需要用Python编写一个程序来解决这一个问题，但是在此之前，我们先来看一个在生活中类似的问题——星期计算问题。

2.星期计算问题

假设今天是1号星期一，问：过n天后是星期几？

日	一	二	三	四	五	六
-	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

举例：
过19天后，为20号，星期六
过8天后，为9号，星期二
过6天后，为7号，星期日

以上例子根据日历来数是非常简单的，但是问10000天之后是星期几就没有这样简单了。
但是我们可以根据规律，以7天为一个周期，用数学方法来计算。把经过的日子除以7取余数就可以找到规律并计算出目标日期的星期。

验证：
过19天后，为20号 >>> (1+19)/7 = 2余6 >>> 星期六
过8天后，为9号 >>> (1+8)/7 = 1余2 >>> 星期二

过6天后，为7号 >>> (1+6)/7 = 1余0 >>> 星期日(余0看作星期日)
取余数(take the remainder)，在Python中的运算符是%(mod运算):
1
2
3
(1+19)%7
(1+8)%7
(1+6)%7
以下为Python实现代码：
1
2
3
4
5
6
print("今天是1号星期一")
weekstr = '日一二三四五六'
n = int(input("输入经过的天数："))
m = (1 + n) % 7
week = weekstr[m]
print("经过",n,"天后是星期",week,sep='')
输出如下：
1
2
3
今天是1号星期一
输入经过的天数：19
经过19天后是星期六
3.Python代码实现
回到上面介绍的约瑟夫问题
一圈有n个人坐着，所有人从1到n编号，从第一个人开始，他们从1数到m，数到m的人将被淘汰。这个过程将从下一个人重新开始，直到所有人都被淘汰。现在的任务是编写一个程序，根据给定的n和m来推导淘汰的顺序。也就是说，程序应该要求用户输入整数n和m，然后在屏幕上输出淘汰的顺序。

和刚刚的星期计算问题十分的类似，都是一种周期性的问题，星期问题的周期是7，而约瑟夫问题的周期是一个变量m，也就是一圈人报的数字。这也不奇怪，因为在编程算法中，类似这样的问题又被成为约瑟夫环

类比星期问题

还是用之前的星期列表，如果从1号开始从1报数，每次报到7的出列，那出列的就是和1号同一个星期（星期一）的日子，也就是8日，15日，22日，29日。

日	一	二	三	四	五	六
-	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

现在我们把约瑟夫环也类比成星期问题：
举例：总人数n=5，数到m=2

一	二
1（开始）	2
3	4
5	-

从1号开始报数，每次报到2的出列，类比成星期问题，那就是只用两个星期（星期一和星期二），并且星期二的就是需要出列的日子，那就不难发现，在上面的表中，需要出列的就是2号和4号。

但是约瑟夫环有一点和星期问题不同，那就是约瑟夫环需要把所有一圈的人（日子）全部淘汰才能结束，那我们就可以把还没有被淘汰的人（日子）顺次接到第一轮的后面，如下：

一	二
1	2
3	4
5（开始）	1
3	5

继续报数，这一次从上一次被淘汰（4号）的下一个开始报数（5号），那这一次需要出列的是星期二的1号和5号
继续把还没有出列的（3号）接到上一轮的后面：

一	二
1	2
3	4
5	1
3	5
3

最后只剩下3号，那就自然变成最后一个出列的
综上：淘汰（出列）的顺序就是2号，4号，1号，5号，3号，和我们在开头例子中得出的结果是一样的。

小结：类比成星期问题，约瑟夫环每次需要淘汰的人位置都可以通过取余数的方式确定下来，还需要把未淘汰的人顺次接到上一轮的后面。因此，我们只需先确定每次需要淘汰的位置，然后通过遍历这一圈人，当遍历到的位置和需要淘汰的位置相同时，就把此位置的人移除，并把移除的后一个人作为下一次遍历的起点，不断循环，直到全部的人都被淘汰。

为了实现以上的想法，我们就需要用到Python中的队列queue来当作载体，因为队列的FIFO（即First in First Out,先进先出）的特性能保持这一圈人的顺序不发生变化。

Python代码

代码下载链接：
https://github.com/zhangwengyu999/Josephus_Problem_with_Python

也欢迎到我的开发性页面使用UltraFish Plus - 在线约瑟夫问题计算器 Online Josephus Problem Calculator

from queue import Queue #引入队列queue
n = int(input("\n输入总人数n（n为正整数）:"))
m = int(input("输入每次报数 m（m为正整数） :"))
position = 1 #需要被淘汰的位置，初始为1
nowposition = 1 #当前遍历的位置，初始为1
outqueue = Queue() #储存输出的队列
nqueue = Queue() #储存每一遍中还没有被淘汰的人
for i in range(1,n+1): #新建一个从1到n的队列
    nqueue.put(i)

while nqueue.empty() is False: #循环直到列表为空
    #>>>第一步是确定下一次需要被淘汰的位置<<<
    position = (m - 1) % nqueue.qsize() + 1 #使用取余数%来确定下一次需要被淘汰的位置("-1" 和 "+1" 的作用会在后文解释)
    #>>>第二步就是把遍历到的人移到队列的末尾或者输出的队列中<<<
    if nowposition != position: #当遍历到的人不是淘汰的目标时，就把他移到队列的末尾
        nqueue.put(nqueue.get())
        nowposition += 1 #遍历后一个人
    else: #当遍历到的人是需要被淘汰的时，把他移动到输出的队列中
        outqueue.put(nqueue.get())
        nowposition = 1 #下一个人作为遍历的起点
print(">>>结果如下，总人数[",n,"]人，每次报数[",m,"]:",sep="")
while not outqueue.empty():
     print(outqueue.get(), end=' ')#输出队列

解释以下代码：

1	`position = (m - 1) % nqueue.qsize() + 1`

这句代码中的”-1” 和 “+1”是为了解决当报数m是剩下队列长度的倍数时所产生的bug

验证

接下来，我用一个例子验证以上代码和这个bug的解决方法

举例：n=5，m=2

第1次:

1 2 3 4 5

nowposition(人编号)	position	outqueue
1(1)	2	-

第2次:

2 3 4 5 1

nowposition(人编号)	position	outqueue
2(2)	2	2

第3次:

3 4 5 1

nowposition(人编号)	position	outqueue
1(3)	2	2

第4次:

4 5 1 3

nowposition(人编号)	position	outqueue
2(4)	2	2, 4

第5次:

5 1 3

nowposition(人编号)	position	outqueue
1(5)	2	2, 4

第6次:

1 3 5

nowposition(人编号)	position	outqueue
2(1)	2	2, 4, 1

第7次:

3 5

nowposition(人编号)	position	outqueue
1(3)	2	2, 4, 1

解释：此时m=2，剩下队列长度=2，报数m是剩下队列长度的倍数
若直接运行以下代码：

1	`position = m % nqueue.qsize()`

得到的position返回值是0，并不是正确的position=2，会出现bug
因此，加上”-1” 和 “+1”就能解决这个bug，变成以下代码：

1	`position = (m - 1) % nqueue.qsize() + 1`

第8次:

5 3

nowposition(人编号)	position	outqueue
2(5)	2	2, 4, 1, 5

第9次:

3

nowposition(人编号)	position	outqueue
1(3)	2	2, 4, 1, 5

第10次:

3

nowposition(人编号)	position	outqueue
2(3)	2	2, 4, 1, 5, 3

nqueue队列变空，循环结束，输出outqueue：

1	`2, 4, 1, 5, 3`

和开头举的例子结果相同。

4.总结

去掉注释后的代码其实没有多少行：

from queue import Queue 
n = int(input("\n输入总人数n（n为正整数）:"))
m = int(input("输入每次报数 m（m为正整数） :"))
position = 1 
nowposition = 1 
outqueue = Queue() 
nqueue = Queue() 
for i in range(1,n+1): 
    nqueue.put(i)
while nqueue.empty() is False: 
    position = (m - 1) % nqueue.qsize() + 1 
    if nowposition != position:
        nqueue.put(nqueue.get())
        nowposition += 1 
    else: 
        outqueue.put(nqueue.get())
        nowposition = 1 
print(">>>结果如下，总人数[",n,"]人，每次报数[",m,"]:",sep="")
while not outqueue.empty():
     print(outqueue.get(), end=' ')