Python|约瑟夫环算法
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。
问题描述
问题描述：N个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈。（模拟此过程，输出出圈的人的序号）
解决方案
这道题涉及到的算法叫做“约瑟夫算法”，我们需要将列表内所有人类似排列成一个“圈”来解决，需要将前一次删除后剩下的元素的索引不变，但是位置向前提。无限循环这个“圈”，直到删除到只剩一个。
这道题的关键在于如何将每个数的索引数字固定，在删除前一个数字后，后面的数字都应该在排序中加一。所以我们一开始需要创建一个列表，从1开始到含有位数的数字，代表每个数字的索引列表。
代码示例：
def Josephus_problem(num,gap):
location_list = [a for a in range(1,num+1)]
if num == 1 :
return
else:
index = 0
for i in range(num-1):
index = (index + gap )%len(location_list) - 1
print("本次出局的人为：",location_list[index])
del location_list[index]
if index == 0:
index = 0
print( "最后剩下的为：",location_list[0])
Josephus_problem(5,3)结语
这道题的解决方法有很多种，这里主要介绍一下这种算法。还有重点为推导出(index + gap )%len(location_list)这个公式。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-01-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读