「約瑟夫問題」在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中使用列表

回答

相關問題