0

我的朋友告诉我约瑟夫斯问题，你有很多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圈子中的更多人？

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

4

2 回答 2

1

我看到两个严重的错误。

  1. 我保证它del ppList[::i]不会像你希望的那样做。
  2. 当您绕圈时，重要的是要知道您是杀死列表中的最后一个人（列表中的第一个再次杀死）还是没有杀死（列表中的第一个人死亡）。

与您声称它最多可以工作 42 的断言相反，它不适用于许多较小的数字。它不起作用的第一个是 2。（它给出 3 作为答案而不是 1。）

于 2018-07-23T17:37:50.027 回答
0

问题是如果他没有被杀，你最终不会考虑这个人。例如，如果有 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

除了这种方法之外，还有非常有效的方法可以解决这个问题。检查此链接以了解更多信息

于 2019-09-21T13:22:34.193 回答