我想知道这是否是能够解决使用Python列表中的Josepheus问题。
简单来说约瑟夫问题是所有有关查找以圆形布置的位置，如果执行使用该事先已知的跳过参数处理出这将是安全的。
为例如：给定一个圆形布置如[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
更新了代码段的问题，但我不认为我的逻辑是正确的。
很简单，你可以使用list.pop(i)删除每一个受害者（并得到他的ID）在一个循环。 然后，我们就不必担心包裹指数，你可以通过采取跳过率MOD剩余囚犯人数只是做。
那么，问题的解决方案变得
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
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的数据结构。
它看起来更糟，但更容易理解，适合初学者
def last(n):
a=[x for x in range(1,n+1)]
man_with_sword = 1
print(a)
while len(a)!=1:
if man_with_sword == a[len(a)-2]: #man_with_sword before last in circle
killed = a[len(a)-1]
a.remove(killed)
man_with_sword=a[0]
elif man_with_sword==a[len(a)-1]: #man_with_sword last in circle
killed = a[0]
a.remove(killed)
man_with_sword=a[0]
else:
i=0
while i < (len(a)//2):
i=a.index(man_with_sword)
killed = a[a.index(man_with_sword)+1]
a.remove(killed)
#pass the sword
man_with_sword=a[i+1] # pass the sword to next ( we killed next)
print (a, man_with_sword) #show who survived and sword owner
i+=1
print (a, man_with_sword,'next circle') #show who survived and sword owner
我的解决方案使用的数学技巧我在网上找到的位置： 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
这是我解决你的问题：
# 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())
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)
