我的循环出了什么问题？

Question

我一直在尝试编写约瑟夫问题的程序，但是只有在某些情况下才有效，我不确定为什么。它的工作原理如下：

你有一个由X个人组成的圆圈。每第N个人将被杀死，直到只剩下一个人为止。所以，比如说你有10个人（也就是X），你决定每隔3个人（即第N个人）杀一个，那么这个过程将会是这样的：

第1轮：1、2、(3死了)、4、5、(6死了)、7、8、(9死了)、10

第2轮：1、(2因为在连续的圆圈上所以死了)、3、5、(7死了)、8、10

第3轮：(1)、4、5、(8)、10

第4轮：4、(5)、10

第5轮：4、(10)

最后，我们只剩下第4个人。

我的程序可以很好地完成这个任务。然而，当我把X设为55，N设为17时，得到的答案是27，但实际上应该是第40个人。有谁能告诉我我的循环出了什么问题吗？

源代码：

def solveJosephus(specifics):
    people = [int(x) for x in range(1,int(specifics[0])+1)]
    killPosition = int(specifics[1])
    positionCounter = 0
    sorted = False

    while not sorted:
        if len(people) == 1:
            print(people[0]) # Pyschologically scarred Winner!
            sorted = True
        for person in people:
            positionCounter += 1
            if positionCounter == killPosition:
                print(person)
                people.remove(person)
                positionCounter = 1

solveJosephus(raw_input().split())

- Vale

---

应该是 people = range(1, int(specifics[0])+1)。Python 2.x 中内置的 range 函数保证生成一个整数列表，因此将它们再映射为整数是多余的。 - Shashank

此外，我认为可以通过迭代有序集合的副本并从中删除元素来实现更好的时间复杂度：http://code.activestate.com/recipes/576694/ 或者只需使用内置的Python set并遍历从set生成的排序列表，例如 for person in sorted(survivors): 还可能在这里找到一个递归关系，它产生了一种有效的动态规划解决方案。最有效的解决方案可能使用数学公式 :) - Shashank

Answer 1

问题在于您在迭代列表时删除了其中的人员。

发生的情况如下：

假设您有X = 5和N = 2。 您的列表为[1,2,3,4,5]。 您到达index = 1并杀死第二个人。 现在您的列表为[1,3,4,5]。 问题是，您的索引仍然等于1，但现在它指向第三个人。 当您再走两步（索引=3）时，您不会杀死第四个人，而是杀死第五个人。

- Loocid

Answer 2

我不确定为什么有时候你会得到正确或错误的答案，但如果我尝试在迭代列表时修改它，我总是遇到奇怪的问题。

for person in people:
    ...
    people.remove(person)

也许你可以遍历people.copy()，这样你就不会修改你正在遍历的同一个列表了。

- Eric Renouf

Answer 3

除了所有其他 答案（告诉您在迭代时制作列表副本），您代码的另一个问题是您将positionCounter重置为1在这一行：positionCounter = 1。它应该被重置为0。这是完整的可工作代码（迄今为止可行）：

def solveJosephus(specifics):
    people = [int(x) for x in range(1,int(specifics[0])+1)]
    killPosition = int(specifics[1])
    positionCounter = 0
    sorted = False

    while not sorted:
        if len(people) == 1:
            print(people[0]) # Pyschologically scarred Winner!
            sorted = True
        for person in people[:]: #Make copy of iterating list
            positionCounter += 1
            if positionCounter == killPosition:
                print(person)
                people.remove(person)
                positionCounter = 0 #Important! 0 != 1

solveJosephus(raw_input().split())

- jkd