问题描述

在一间房间总共有n个人,给定一个数k,然后按照如下规则去杀人:

  1. 所有人围成一个圆圈,按顺时针依次给所有人编号:1, 2, 3…, n
  2. 由编号1开始报数,按顺时针方向,报到数字k的人将被杀掉
  3. 被杀掉的人从房间内被移走,从被杀的下一个人重新由1开始报数
  4. 报到数字k的人再次被杀掉,再移走,再次开始报数,一直杀到最后剩余一个人

最后剩余的人活命。

那么,给定了 n 和 k,最后活下来的人的编号是几?

思路一

根据问题描述,可以使用循环单链表模拟杀人过程:

  1. 表头是1号,表尾是n号,循环单链表的表尾指向表头模拟圆圈
  2. 指针从表头1号开始走,当指到第k个节点时,即当报k的被杀时,就将该节点从链表中删除。
  3. 删除该节点后,从该节点的下一个节点开始,再从1走到k,
  4. 再次删除第k节点,一直到某节点的下一个节点指向自己,说明只有一个节点了,即最后活下的人

根据上面分析循环单链表的操作过程,代码实现如下:

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
31
32
33
34
35
36
37
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
def create_linkList(people_num):
"""创新循环单链表"""
head = Node(1)
pre = head
for i in range(2, people_num+1):
newNode = Node(i)
pre.next = newNode
pre = newNode
pre.next = head
return head
people_num = 5 # 总人数
k = 2 #报k被杀
if k == 1:
print("最后存活编号:" + str(people_num))
else:
head = create_linkList(people_num)
pre = None
cur = head # 当前报数的人
while cur.next != cur: # #终止条件是节点的下一个节点指向本身,即只剩一个节点
for i in range(k-1):
# 走到第k节点
pre = cur
cur = cur.next
print("杀掉:" + str(cur.value)) # 被删除节点编号
# 删除节点
pre.next = cur.next
# 从被删除节点的下一个节点从新报数
cur.next = None
cur = pre.next
print("最后存活者编号是:" + str(cur.value))

这种方法的时间复杂度为:O(n*k),当人数量n很大,报的数k也很大时,并不适用。

思路二

递归思路,假设房间共有n = 10个人,初始编号为1,2,3,…10,设初始编号对应的编号位置为0, 1, 2, …9, 每次数到k = 3的人杀死,求最后活下来的人的初始编号是几?

来看杀人过程:

约瑟夫问题递归思路求解过程

(表中红色为报数k=3的被杀死的人的编号,绿色为最后活下来的人的编号)

仔细观察表中每一轮初始编号的移动规律:

第二轮到第一轮的编号移动规律: (第二轮的编号x的编号位置 + k) % 10 ==> 第一轮编号x的编号位置
比如第二轮编号5的编号位置是1, (1 + 3) % 10 ==> 4, 得到第一轮编号5的的编号位置是4

进而得到第三轮到第二轮的编号移动规律:(第三轮编号x的编号位置 + k) % 9 ==> 第二轮编号x的编号位置
比如第三轮编号5的编号位置是7, (7 + 3) % 9 –> 1, 得到第二轮编号5的的编号位置是1

进而得到第N轮与第N-1轮的编号移动规律:(第N轮的编号x的编号位置 + k) % 第N-1轮总人数 ==> 第N-1轮编号x的编号位置

最后一轮存活着的编号x对应的编号位置一定是0, 那么根据以上规律,可以得到倒数第二轮编号x对应的编号位置,根据规律进一步可以得到倒数第三轮编号x对应的编号位置, 一直可以推导出第一轮编号x的对应编号位置,由第一轮编号x的对应编号位置+1得到的便是最后存活的人的初始编号。

由上总结,当房间共有n个人,报数k杀死时,令f(n, k)表示最后存活着的编号位置,则有递归公式:

  • n = 1: f(1, k) = 0;
  • n > 1: f(n, k) = (f(n-1, k) + k) % n;

有了递推公式以后,代码实现如下:

1
2
3
4
5
6
7
8
9
def josephus(n, k):
if n == 1:
return 0
else:
return (josephus(n - 1, k) + k) % n
n = 10
k = 3
print("最后存活者编号是:", josephus(n, k)+1) # 4

对思路二的优化

对递归思路的进一步优化,假设n非常大,而k又比较小,比如n=100, k=3, 被杀过程如下:

  • 第一轮: 有100个人,每次报k=3的被杀,总共杀死了 math.floor(100/3) = 33个人,剩余67个人
  • 第二轮: 有67个人,每次报k=3的被杀,总共杀死了 math.floor(67/3) = 22个人,剩余45个人
  • 第三轮: 有45个人,每次报k=3的被杀,总共杀死了 math.floor(45/3) = 15个人,剩余30个人
  • 第四轮: 有30个人,每次报k=3的被杀,总共杀死了 math.floor(30/3) = 10个人,剩余20个人
  • 第五轮: 有20个人,每次报k=3的被杀,总共杀死了 math.floor(20/3) = 6个人,剩余14个人
  • 第六轮: 有14个人,每次报k=3的被杀,总共杀死了 math.floor(14/3) = 4个人,剩余10个人
  • 第七轮: 有10个人,每次报k=3的被杀,总共杀死了 math.floor(10/3) = 3个人,剩余7个人
  • 第八轮: 有7个人,每次报k=3的被杀,总共杀死了 math.floor(7/3) = 2个人,剩余5个人
  • 第九轮: 有5个人,每次报k=3的被杀,总共杀死了 math.floor(5/3) = 1个人,剩余4个人
  • 第十轮: 此时,总人数n=4, 报的数k=3,再利用思路二中的递归方法求解最后剩余者编号

在上面杀人过程中,通过建立n/k的步长加快了杀人的速度,减少了算法时间。可以从下面这幅图中更加清晰的体会到:

约瑟夫问题递归思路求解过程优化

本来需要10轮的,现在只需要7轮,如果n=100,k=3的话优化效果会更明显。

根据以上分析,优化方法如下:

  • math.floor(n/k) == 1: 用思路二中方法求解
  • math.floor(n/k) > 1: n = n - math.floor(n/k)

实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import math
def josephus(n, k):
if n == 1:
return 0
else:
return (josephus(n - 1, k) + k) % n
def kill_people(n, k):
while math.floor(n/k) > 1:
# 建立一个步长为n/k的递归过程;
n = n - math.floor(n/k)
kill_people(n, k)
live_index = josephus(n, k)
return live_index+1
n = 10
k = 3
print("最后存活者编号是", kill_people(n,k))

思路三

使用数组存储房间中的每个人: arr = [ i for i in range(1, 10+1) ]
arr数组代表房间里的10个人:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
每次被杀的人的编号: kill_num = (kill_num + k - 1) % len(arr)。 其中的(k-1)对应数组的下标
有了被杀人的的编号后,将其pop出数组。
然后再次计算下一个被杀人的编号,直到数组中只剩一个人。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
def josephus(n, k):
arr = [ i for i in range(1, n+1) ]
kill_num = 0
while len(arr) != 1:
kill_num = (kill_num + k - 1) % len(arr)
print("杀死:" + str(arr.pop(kill_num)))
return arr[0]
n = 10
k = 3
print("最后存活者编号是:", josephus(n, k)) # 4

对思路三的优化

在思路三中需要构建一个数组,也可以不用数组来减少内存。使用动态规划来解:

1
2
3
4
5
6
7
8
9
def Josephus(n, k):
kill_num = 0
for i in range(1, n+1):
kill_num = (k + kill_num) % i
return kill_num + 1
n = 5
k = 2
print("最后存活者编号:", Josephus(n, k))

最后这个动态规划的方法来自:https://www.quora.com/What-is-the-best-solution-for-Josephus-problem-algorithm