"Josephus-problem", используя список в Python
Я хотел знать, удастся ли решить проблему Джозефея с помощью списка в 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
Обновил вопрос с помощью фрагмента кода, но я не думаю, что моя логика верна.
5 ответов
Проще говоря, вы можете использовать list.pop(i) удалить каждую жертву (и получить его идентификатор) в цикле. Тогда нам просто нужно позаботиться об упаковке индексов, что вы можете сделать, просто взяв пропущенный индекс на число оставшихся заключенных.
Итак, решение вопроса становится
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 структура данных.
В моем решении используется математический трюк, который я нашел здесь в Интернете: 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
Это выглядит хуже, но легче для начинающих
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
Если вы ищете только конечный результат, вот простое решение.
def JosephusProblem(people):
binary = bin(people) # Converting to binary
winner = binary[3:]+binary[2] # as the output looks loke '0b101001'. removing 0b and adding the 1 to the end
print('The winner is',int(winner,2)) #converting the binary back to decimal
Если вы ищете математику, лежащую в основе этого кода, посмотрите это видео:Проблема Иосифа Флавия (youTube)
Общее количество людей n и число k, которое указывает, что k-1 человек пропускается, а k-й человек убит в круге.
def josephus(n, k):
if (n == 1):
return 1
else:
return (josephus(n - 1, k) + k-1) % n + 1
n = 14
k = 2
print("The chosen place is ", josephus(n, k))
Это мое решение вашего вопроса:
# 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)