Josephus算法部分成功

Question

我的朋友告诉我关于Josephus problem，在那里你有41的人坐在圈子里。人号1有一把剑，杀了右边的人，然后把剑传给下一个人。这一直持续到只剩下一个人还活着。我用python想出了这个解决方案：

print('''There are n people in the circle. You give the knife to one of 
       them, he stabs person on the right and
       gives the knife to the next person. What will be the number of whoever
       will be left alive?''')

pplList = []
numOfPeople = int(input('How many people are there in the circle?'))


for i in range(1, (numOfPeople + 1)):
    pplList.append(i)
print(pplList)

while len(pplList) > 1:
    for i in pplList:
        if i % 2 == 0:
            del pplList[::i]
    print(f'The number of person which survived is {pplList[0]+1}')
    break

但它只适用于42用户。我应该做什么，或者我应该如何更改代码，以便它可以为100, 1000和圈子中的更多人工作？

我查过Josephus问题，看到了不同的解决方案，但我很好奇，经过一些小调整后，我的答案是否正确，或者我应该从头开始。

Answer 1

我发现了两个严重的bug。

1. 我保证del ppList[::i]不会做任何你希望它做的事情。
2. 当你绕着圆圈绕圈时，重要的是要知道你是杀死了列表中的最后一个人(列表中的第一个人又杀了)还是没有(列表中的第一个人死了)。

与你的断言相反，它适用于42，它不适用于更小的数字。第一个不起作用的是2。(它的答案是3而不是1。)

Answer 2

问题是，如果他没有被杀，你最终就不会考虑他。例如，如果有9个人，在杀死8之后，9有剑，但你只是从1开始，而不是在下一个循环中从9开始。正如已经有人提到的，它对较小的数字也不起作用。实际上，如果你仔细观察，你会在第一个循环中杀死奇数，而不是偶数。这是非常错误的。

您可以按如下所示更正代码

while len(pplList )>1:
    if len(pplList )%2 == 0:
        pplList  = pplList [::2] #omitting every second number
    elif len(pplList )%2 ==1:
        last = pplList [-1] #last one won't be killed
        pplList  = pplList [:-2:2]
        pplList .insert(0,last) # adding the last to the start

除了这个方法之外，还有其他非常有效的方法来解决这个问题。查看this link了解更多信息