32 Josephus Problem 约瑟夫环

问题描述

这是经典的编程难题，尽管它起源于古代根本没有计算机的时代。 我们可以看到练习数学和逻辑有时可以挽救生命！

大约2000年前，发生了一场战争，在一场战斗中，被告被山洞中的攻击者封锁。

为了避免被俘虏，他们决定围成一个圈，杀死三分之一，直到只有一个人（应该自杀）留下，尽管他最终更愿意向敌人投降。 这个人被称为这个问题-您可以阅读Josephus的全文，并在Wikipedia文章中获得关于该问题的数学解释

您的任务是确定给定的人数N和恒定的插值K保持最后一名的位置-即安全位置。 例如，如果有10个将没次第三个人淘汰：

1st round: 1 2 (3) 4 5 (6) 7 8 (9) 10
2nd round:                            1 (2) 4 5 (7) 8 10
3rd round:                                                (1) 4 5 (8) 10
4th round:                                                               4 (5) 10
5th round:                                                                        4 (10)
           

代码

方法1

代码风格以后都要是做函数和应用的，在这里关键一行代码是

这其实是把答案解析出来了然后进行分析。

def  josephusproblem(num,k):
    link =[x+1 for x in range(num)]
    ind = 0
    for loop in range(num- 1) :
        ind = (ind - 1 + k)% len(link)
        del link[ind]
    print (link[0])
    
num,k=list(map(int,input().split()))
josephusproblem(num,k)
           

方法2

这里运用了deque双向队列，并对前面的k-1进行旋转

from  collections  import deque
def  josephusproblem(num,k):
    link =deque(x+1 for x in range(num))
    for loop in range(num- 1) :
        link.rotate(-k+1)
        link.popleft()
    print (link[0])    
num,k=list(map(int,input().split()))
josephusproblem(num,k)
           

对deque实验

from collections import deque
a=deque(range(1,6))
a.rotate(-3)
print(a)