"Josephus-p‌r‌o‌b‌l‌e‌m"在python中使用列表 [英] "Josephus-p‌r‌o‌b‌l‌e‌m" using list in python

问题描述

我想知道是否有可能使用python中的list解决约瑟夫问题.

I wanted to know if it will be possible to solve the Josepheus problem using list in python.

简单地说，约瑟夫斯的问题全在于寻找圆形排列的位置，如果使用事先已知的跳过参数处理执行，这将是安全的.

In simple terms Josephus problem is all about finding a position in a circular arrangement which would be safe if executions were handled out using a skip parameter which is known beforehand.

例如:给定诸如[1,2,3,4,5,6,7]的圆形排列，并且跳过参数3，将按3,6,2,7,5,1的顺序执行人员，并且位置4将是安全的.

For eg : given a circular arrangement such as [1,2,3,4,5,6,7] and a skip parameter of 3, the people will be executed in the order as 3,6,2,7,5,1 and position 4 would be the safe.

一段时间以来，我一直在尝试使用列表解决此问题，但是索引位置让我很难处理.

I have been trying to solve this using list for some time now, but the index positions becomes tricky for me to handle.

 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

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

Updated the question with code snippet, but i don't think my logic is correct.

推荐答案

很简单，您可以使用list.pop(i)循环删除每个受害者(并获取其ID).然后，我们只需要担心包装索引，就可以通过跳过跳过的索引获取剩余囚犯的数量来做到这一点.

Quite simply, you can use list.pop(i) to delete each victim (and get his ID) in a loop. Then, we just have to worry about wrapping the indices, which you can do just by taking the skipped index mod the number of remaining prisoners.

那么问题解决方案就变成了

So then, the question solution becomes

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

这篇关于"Josephus-p‌r‌o‌b‌l‌e‌m"在python中使用列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！