现在有13个人围成一个环，从1开始报数，数到3的人离开，写出程序计算最后剩下的是谁。
使用while循环
def josephus1(num, k, m):
"""
约瑟夫环（约瑟夫问题）是一个数学的应用问题：
已知num个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。
从编号为k的人开始报数，数到m的那个人出列；
他的下一个人又从1开始报数，数到m的那个人又出列；
依此规律重复下去，直到圆桌周围的人全部出列。
:param num:总人数
:param k:开始的编号
:param m:数到m的出列
:return:
"""
alist = [x + 1 for x in range(num)]
print(alist) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
index, step = k-1, m # 从1号开始报数，数到3的那个人出列
while len(alist) > 1:
index = (index + step - 1) % len(alist) # 列表的索引
print('出去的数：', alist[index])
# del alist[index]
alist.pop(index)
return '最后的一个数：%s' % alist[0]
print(josephus1(13, 1, 3)) # 总共13个人，从第1个开始数，每数到3的出去
"""
出去的数： 3
出去的数： 6
出去的数： 9
出去的数： 12
出去的数： 2
出去的数： 7
出去的数： 11
出去的数： 4
出去的数： 10
出去的数： 5
出去的数： 1
出去的数： 8
最后的一个数：13
"""
使用for循环
def josephus2(num, k, m):
alist = list(range(1, num + 1))
index, step = k - 1, m # 从1号开始报数，数到3的那个人出列
for i in range(num-1):
index = (index + step - 1) % len(alist)
print('出去的数：', alist.pop(index))
return '最后的一个数：%s' % alist[0]
print(josephus2(13, 1, 3))
"""
出去的数： 3
出去的数： 6
出去的数： 9
出去的数： 12
出去的数： 2
出去的数： 7
出去的数： 11
出去的数： 4
出去的数： 10
出去的数： 5
出去的数： 1
出去的数： 8
最后的一个数：13
"""
使用递归
alist = list(range(1, 13+1))
def josephus3(alist, k=1, m=3):
"""
由于使用了递归，有一个隐患就是当传入的列表过大时，会造成
RecursionError: maximum recursion depth exceeded while calling a Python object
:param alist:传入的列表
:param k:
:param m:
:return:
"""
if len(alist) > 1:
index, step = k - 1, m # 从1号开始报数，索引为0，数到3的那个人出列
index = (index + step - 1) % len(alist)
print('出去的数： ', alist.pop(index))
return josephus3(alist, index + 1, m)
else:
return '最后的一个数：%s' % alist[0]
print(josephus3(alist, 1, 3))
"""
出去的数： 3
出去的数： 6
出去的数： 9
出去的数： 12
出去的数： 2
出去的数： 7
出去的数： 11
出去的数： 4
出去的数： 10
出去的数： 5
出去的数： 1
出去的数： 8
最后的一个数：13
"""
摒弃递归，每次步长不为k时候都把当前元素弹出并放到队列尾部，从而模拟循环链表结构。进一步优化，由于列表弹出第一个元素的复杂度较高，可以使用双端队列来进行优化：
from collections import deque
alist = list(range(1, 13+1))
def josephus4(alist, k=1, m=3):
"""
如果开始的位置不是1，则先进行队列变化，然后将3前面的数字append到队列末端，再pop掉3位置的数字
:param alist: 传入的列表
:param k:
:param m:
:return:
"""
dq = deque(alist)
tmp_k = k-1
while tmp_k:
dq.append(dq.popleft())
tmp_k -= 1
print('变换为新序列：', dq)
k = 1 # 变换后将从第1个开始
while len(dq) > 1: # 当队列长度大于1时，进行队列的pop操作
if k != m:
dq.append(dq.popleft())
k += 1
print(dq)
else:
print('从左端移除：', dq.popleft())
k = 1
return '最后的一个数：%s' % dq[0]
print(josephus4(alist, 1, 3))
"""
变换为新序列： deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13])
deque([2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1])
deque([3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2])
从左端移除： 3
deque([5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 4])
deque([6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 4, 5])
从左端移除： 6
deque([8, 9, 10, 11, 12, 13, 1, 2, 4, 5, 7])
deque([9, 10, 11, 12, 13, 1, 2, 4, 5, 7, 8])
从左端移除： 9
deque([11, 12, 13, 1, 2, 4, 5, 7, 8, 10])
deque([12, 13, 1, 2, 4, 5, 7, 8, 10, 11])
从左端移除： 12
deque([1, 2, 4, 5, 7, 8, 10, 11, 13])
deque([2, 4, 5, 7, 8, 10, 11, 13, 1])
从左端移除： 2
deque([5, 7, 8, 10, 11, 13, 1, 4])
deque([7, 8, 10, 11, 13, 1, 4, 5])
从左端移除： 7
deque([10, 11, 13, 1, 4, 5, 8])
deque([11, 13, 1, 4, 5, 8, 10])
从左端移除： 11
deque([1, 4, 5, 8, 10, 13])
deque([4, 5, 8, 10, 13, 1])
从左端移除： 4
deque([8, 10, 13, 1, 5])
deque([10, 13, 1, 5, 8])
从左端移除： 10
deque([1, 5, 8, 13])
deque([5, 8, 13, 1])
从左端移除： 5
deque([13, 1, 8])
deque([1, 8, 13])
从左端移除： 1
deque([13, 8])
deque([8, 13])
从左端移除： 8
最后的一个数：13
"""
网友评论