"Josephus-p‌r‌o‌b‌l‌e‌m" sử dụng danh sách trong python

Question

Tôi muốn biết liệu có thể giải quyết vấn đề Josepheus bằng cách sử dụng danh sách trong python hay không.

Nói một cách đơn giản, vấn đề Josephus là tất cả về việc tìm kiếm một vị trí trong một sắp xếp tròn sẽ an toàn nếu thực thi được xử lý bằng cách sử dụng tham số bỏ qua được biết trước.

Ví dụ: được sắp xếp theo hình tròn như [1,2,3,4,5,6,7] và thông số bỏ qua là 3, mọi người sẽ được thực hiện theo thứ tự là 3,6,2,7,5,1 và vị trí 4 sẽ là an toàn.

Tôi đã cố gắng giải quyết danh sách này bằng cách sử dụng một thời gian, nhưng các vị trí chỉ mục trở nên phức tạp để tôi xử lý.

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 

Cập nhật câu hỏi với đoạn mã, nhưng tôi không nghĩ logic của tôi là đúng.

Answer 1

Rất đơn giản, bạn có thể sử dụng list.pop(i) để xóa từng nạn nhân (và nhận ID của mình) trong một vòng lặp. Sau đó, chúng tôi chỉ phải lo lắng về việc bao gồm các chỉ số, mà bạn có thể làm chỉ bằng cách lấy chỉ số bỏ qua mod số tù nhân còn lại.

Vì vậy, sau đó, các giải pháp câu hỏi trở thành

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] 

Kiểm tra đầu ra:

>>> josephus([1,2,3,4,5,6,7], 3) 
3 
6 
2 
7 
5 
1 
survivor: 4 

Answer 2

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 

Nếu bạn không muốn để tính toán chỉ số, bạn có thể sử dụng cấu trúc dữ liệu deque.

Answer 3

Đây là giải pháp của tôi cho câu hỏi của bạn:

# 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()) 

Answer 4

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)