“Josephus-p‌r‌o‌b‌l‌e‌m”使用python中的list

Question

我想知道在python中使用list是否可以解决Josepheus问题。

简而言之，约瑟夫斯问题就是在一个循环的排列中找到一个位置，如果使用事先已知的跳过参数来处理执行，这个位置是安全的。

例如：给定一个循环安排，如[1,2,3,4,5,6,7]，skip参数为3，则将按3,6,2,7,5,1的顺序执行人员，并且位置4是安全的。

我已经尝试使用list解决这个问题有一段时间了，但是索引位置对我来说变得很难处理。

 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

Answer 2

In [96]: def josephus(ls, skip):
    ...:     from collections import deque
    ...:     d = deque(ls)
    ...:     while len(d)>1:
    ...:         d.rotate(-skip)
    ...:         print(d.pop())
    ...:     print('survivor:' , d.pop())
    ...:     

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

如果不想计算索引，可以使用deque数据结构。

Answer 3

我的解决方案使用了我在网上找到的一个数学技巧：https://www.youtube.com/watch?v=uCsD3ZGzMgE 它使用二进制的方式来记录圆圈中的人数和幸存者所处的位置。结果相同，代码更短。

代码是这样的：

numar_persoane = int(input("How many people are in the circle?\n")) #here we manually insert the number of people in the circle

x='{0:08b}'.format(int(numar_persoane)) #here we convert to binary

m=list(x) #here we transform it into a list

for i in range(0,len(m)): #here we remove the first '1' and append to the same list

    m.remove('1')

    m.append('1')

    break

w=''.join(m) #here we make it a string again

print("The survivor sits in position",int(w, 2)) #int(w, 2) makes our string a decimal number