数据结构与算法（Python版）：用队列（Queue）处理约瑟夫问题
2021-01-26 19:14
标签：mda 出队 问题 div sel == nan 初始 elf 在古罗马时期，犹太人背叛了罗马人，落到困境，约瑟夫和同行的一共39个犹太人只能够自杀殉国，但是犹太教义规定不能自杀，因此只能够让别人将自己杀害。他们所有39个人坐成一圈，报数1—7，报到7则由身旁的人将自己杀死。结果约瑟夫灵机一动，给自己安排了一个位置，最后活了下来，那么约瑟夫给自己安排的是哪一个位置呢？ 在这个题目当中，我们如果使用队列，不仅可以处理任意人数坐成一圈，还可以将报数的值任意修改，最后都可以找到那一个不被杀死的人的位置。我们可以将所有人都放进一个大的队列里，每报一次数字，那么就把队列头部的人放到队列的尾部，直到报数报到一组数字的最后一个，比如1——7当中的7。这个时候就将队列头的这个人删除（也就是杀死），不断执行这个过程，直到整个队列当中的人数只有一个，则跳出循环返回最后活着的那个人的名字。 首先定义队列（Queue）类的结构： 使用队列类来初始化一个对象，sim_queue,然后编写刚才我们分析之后的程序： 输出： 得解，因此Ao li Gei!这个人不会被杀死。 数据结构与算法（Python版）：用队列（Queue）处理约瑟夫问题 标签：mda 出队 问题 div sel == nan 初始 elf 原文地址：https://www.cnblogs.com/geeksongs/p/12850835.htmlclass Queue():
def __init__(self):
# 初始化一个空的列表
self.__list=[]
# 往队列里插入元素
def enqueue(self,item):
self.__list.append(item)
# 弹出队列里的元素
def dequeue(self):
return self.__list.pop(0)# 弹出队列里最先进入的元素
# 判断队列是否为空
def is_empty(self):
return self.__list == []
# 计算队列的大小
def size(self):
return len(self.__list)
def hot_potato(namelist,num):
sim_queue = Queue()
for name in namelist:
sim_queue.enqueue(name) # 把拿到的名字全部都放到队列里
while sim_queue.size() > 1:
for i in range(num):
sim_queue.enqueue(sim_queue.dequeue())
# 每执行完一次，就将队列的头拿出来弹出，相当于土豆传递给这个人，然后这个人就死了
last_person=sim_queue.dequeue()
return last_person
print("开始执行约瑟夫问题")
print(hot_potato(["bob","NAni","Ao li Gei!","HeHe","Mike","Suvennia"],4))
开始执行约瑟夫问题
Ao li Gei!
文章标题：数据结构与算法（Python版）：用队列（Queue）处理约瑟夫问题
文章链接：http://soscw.com/index.php/essay/47406.html