约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从第s个人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解。
此类问题在很多地方也被加工成杀人游戏，猴子当大王问题什么的，其原型就是约瑟夫环。
分析：python中没有指针概念，所以很难形象的表示计算过程，但是高级语言也有高级语言的好处，使用一些函数调用同样可以达到目的。因为约瑟夫环的规则，所以在进行人员出列的时候，剩下的人员的排序是个问题：1、如果是静态的重排，那么就需要列尾最后一个人报完后从列头从新报数，是否可以将报完数的人排到列尾。2、如果不进行重新排序，是否可以通过计数来标记出列的人（或存活的人）。
算法设计：若有n个人，报到m的人出列，最后留下x人，那么算法结束的标志应该是人数<=x，我们假设n=20,m=3,x=5,那么
①对于第一种想法可以用以下算法：
a=[x for x in range(1,21)] #取1-20个数，要让他从1开始，方便与1-3报数相同b=[]#创建空列表来记出列的人for i in range(15*3): #每3次下一个人，最少要数15*3次才能数够15名下船人数if (i+1)%3==0:#range(45)是从0-44，前闭后开，+1后与报数的序数一致b.append(a[i-len(b)]) #把a里面出列的人加入到b列表中y=len(b)-1 #列表b里面每增加一个元素，a里面对应的人员就会自动往前面进一位后面前进的位数刚好是列表b的长度-1a.remove(a[i-y]) #同时册除列表a里面被点中的人else:a.append(a[i-len(b)]) #把没有被点中的人重新加入到列表a 的后面b.sort() #对b排序，更直观清晰print("被淘汰的人为:{}".format(b))c=[x for x in range(1,21)] #因为a列表已经之前改变表长,用c代替原来的afor i in b:c.remove(i)print("剩下的人为:{}".format(c))
输出结果为：
被淘汰的人为:[1, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15, 17, 18, 19]剩下的人为:[2, 8, 13, 16, 20]
这种算法思想就是创建一个足够长的列表来计数，长度至少为（n-x）*m，然后将没有点到的人不断的再加入到列表后面(用append)，将出列的人删掉(remove和pop都可以，pop会返回这个数，remove不返回)，最后用新的列表来记录出列的人和剩下的人。有些麻烦，但是很好理解。
②对于第二种想法可以用以下算法：
people={} #创建个字典，后面解释用处for i in range(1,21):#还是1-20个数，对应1-20个人people[i]=1#每个号码对应的初始值为1，这点就是创建字典的用处#通过字典的key:value，这样就可以对valu来标记，进而来记录谁出局。num=0 #报数置零i=1#报数人的位置count=0#记录淘汰的人数while i<=21:if i == 21: #当i循环到最后的时候，自动回到1的位置i=1elif count == 15:break#当淘汰人数到15个人时，退出循环else:if people[i] == 0: # 如果这个人已经被淘汰了，num不计数，此时跳过他，第i+1个人接着报数i+=1continueelse:num+=1 #如果这个人没有被淘汰还，那么num+1,此时进行进一步判断if num == 3:#如果num到3了，那么将他的value设置为0，并print淘汰信息，num归0，count加1people[i]=0num = 0print("{}号淘汰了".format(i))count+=1else:#若不为3，则进行下一个人报数i+=1continue
输出结果为：
3号淘汰了6号淘汰了9号淘汰了12号淘汰了15号淘汰了18号淘汰了1号淘汰了5号淘汰了10号淘汰了14号淘汰了19号淘汰了4号淘汰了11号淘汰了17号淘汰了7号淘汰了
这种算法就是通过字典的key:value，来记录每个key的value，根据value来判断是否淘汰，控制循环，可能没有第一种清晰，但是时间和空间复杂度上要比第一种好点
③、第三种算法，先上代码
people=list(range(1,21))while len(people)>5:i=1 #每次while循环时初始化iwhile i<3:people.append(people.pop(0))i+=1print('{}号淘汰了'.format(people.pop(0)))
结果为：
3号淘汰了6号淘汰了9号淘汰了12号淘汰了15号淘汰了18号淘汰了1号淘汰了5号淘汰了10号淘汰了14号淘汰了19号淘汰了4号淘汰了11号淘汰了17号淘汰了7号淘汰了
和第②种方法结果完全一样，这个算法是这样的：前面都相同，主要这句代码
while i<3:people.append(people.pop(0))i+=1
这句代码的意思是，如果i<3，也就是只要没报到3的人，用.append(.pop())函数，pop（）会返回这个元素的值，然后再用append接受并加到列表最后，完成动态的“环”。举个例子：
在python3中输入
>>> a=[1,2,3,4,5]>>> a.pop(0)
结果会返回a[0]的值，也就是1
1
此时，再用append函数接受这个值加到最后,输出列表a
>>> a.append(1)>>> a[2, 3, 4, 5, 1]
然后通过i的计数，完成删除
print('{}号淘汰了'.format(people.pop(0))) #这句当while为FALSE，即i=3时执行此句代码
第三种算法的代码无疑是最简洁，这也是python的一大特点，当然还有其他解法，比如递归调用等等，因为本人能力有限，水平不高，无法用递归来简单清楚的解答约瑟夫环这个问题。不足之处，还请大神多多指点，O(∩_∩)O哈哈~
如果觉得《python解决约瑟夫环（杀人游戏）》对你有帮助，请点赞、收藏，并留下你的观点哦！
