python - "Josephus-p‌r‌o‌b‌l‌e‌m"在 python 中使用列表

Question

我想知道是否有可能在 python 中使用列表来解决 Josepheus 问题。

简而言之，Josephus 问题就是在圆形排列中找到一个位置，如果使用事先已知的跳过参数处理执行，该位置将是安全的。

例如:给定一个循环排列，如[1,2,3,4,5,6,7]，skip参数为3，人将按照如下顺序执行3,6,2,7,5,1 和位置 4 是安全的。

一段时间以来，我一直在尝试使用列表来解决这个问题，但是索引位置对我来说很难处理。

 a=[x for x in range(1,11)]
 skip=2
 step=2
 while (len(a)!=1):
   value=a[step-1]
   a.remove(value)
   n=len(a)
   step=step+skip
   large=max(a)
   if step>=n:        
      diff=abs(large-value)
      step=diff%skip
   print a

更新 带有代码片段的问题，但我认为我的逻辑不正确。

Answer 1

很简单，您可以使用 list.pop(i) 循环删除每个受害者(并获取他的 ID)。然后，我们只需要担心包装索引，您只需将跳过的索引取模剩余囚犯的数量即可。

那么，题解就变成了

def josephus(ls, skip):
    skip -= 1 # pop automatically skips the dead guy
    idx = skip
    while len(ls) > 1:
        print(ls.pop(idx)) # kill prisoner at idx
        idx = (idx + skip) % len(ls)
    print('survivor: ', ls[0])

测试输出:

>>> josephus([1,2,3,4,5,6,7], 3)
3
6
2
7
5
1
survivor:  4