约瑟夫问题:是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。
从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;
依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后[1] 结果
+1即为原问题的解。
python源码:
class Queue:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def enqueue(self,item):
self.items.insert(0,item) def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items) def hot_potato(name_list,num):
sim_queue = Queue() for name in name_list:
sim_queue.enqueue(name) while sim_queue.size() > 1:
for i in range(num):
sim_queue.enqueue(sim_queue.dequeue()) sim_queue.dequeue() return sim_queue.dequeue()
输出结果:
who is last:
Susan