“约瑟夫问题”在Python中使用列表

我想知道是否有可能使用python中的列表解决Josepheus问题。“约瑟夫问题”在Python中使用列表

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

例如：给定一个圆形排列，如[1,2,3,4,5,6,7]和跳过参数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

更新与代码段的问题，但我不认为我的逻辑是正确的。

来源

2012-09-16 Krishna Sangeeth K S

很简单，您可以使用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

来源

2012-09-16 07:10:12 nneonneo

这种算法是惊人的！你能分享一下，你是怎么想到'idx =（idx + skip）％len（ls）'的？我知道它是有效的，但我不知道人们如何能够找到这种方式。谢谢！ –

@JayWong这是最好的方式来通过一个数组，并从头到尾打包 –

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数据结构。

来源

2017-03-11 06:26:02

这是我解决你的问题：

# simple queue implementation<ADT> 
class Queue: 
    def __init__(self): 
     self.q = [] 
    def enqueue(self,data): 
     self.q.insert(0,data) 
    def dequeue(self): 
     self.q.pop() 
    def sizeQ(self): 
     return len(self.q) 
    def printQ(self): 
     return self.q 


lists = ["Josephus","Mark","Gladiator","Coward"] 
to_die = 3 
Q = Queue() 
# inserting element into Q 
for i in lists: 
    Q.enqueue(i) 
# for size > 1 
while Q.sizeP() > 1: 
    for j in range(1,3): 
# every third element to be eliminated 
     Q.enqueue(Q.dequeue()) 
    Q.dequeue() 
print(Q.printQ())

来源

2018-02-11 03:29:06

约瑟夫问题还有另一种变化，如果计数开始Anti - Clockwise –

def Last_Person(n): 
    person = [x for x in range(1,n+1)] 
    x = 0 
    c = 1 
    while len(person) > 1: 
     if x == len(person) - 1: 
      print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[0]) 
      person.pop(0) 
      x = 0 
      c = c+1 
     elif x == len(person) - 2: 
      print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[x + 1]) 
      person.pop(x+1) 
      x = 0 
      c = c + 1 
     else: 
      print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[x + 1]) 
      person.pop(x + 1) 
      x = x + 1 
      c = c + 1 
    print("Person", person[x], "is the winner") 

Last_Person(50)

来源

2018-03-05 03:50:28

“约瑟夫问题”在Python中使用列表

回答

相关问题