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

阅读数: 次 2020-08-05

Made by Mike_Zhang

博客名称及其域名变更提醒:
我的个人博客名称已由 UltraFisher 改为 UltraFish.
相应的域名已由ultrafisher.github.io改为ultrafish.cn.
后续所有的更新将会在ultrafish.cn进行, 本网站将停止更新.
十分感谢您的浏览以及支持, 让我们在UltraFish再次相遇!

Notification
The name of my personal blog has been changed from UltraFisher to UltraFish.
Its domain name has been changed from ultrafisher.github.io to ultrafish.cn.
ONLY ultrafish.cn will be updated, this website will NOT be updated.
Thank you very much for your browsing and support, see you on the UltraFish!
Mike_Zhang
2020/10/15

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实现代码：

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代码

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=' ')