我一直在尝试编写约瑟夫问题的程序,但是只有在某些情况下才有效,我不确定为什么。它的工作原理如下:
你有一个由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())
people = range(1, int(specifics[0])+1)
。Python 2.x 中内置的range
函数保证生成一个整数列表,因此将它们再映射为整数是多余的。 - Shashankfor person in sorted(survivors):
还可能在这里找到一个递归关系,它产生了一种有效的动态规划解决方案。最有效的解决方案可能使用数学公式 :) - Shashank