数据结构与算法(Python版)十二:队列的应用(热土豆)
热土豆问题(约瑟夫问题)“击鼓传花”的土豆版本传烫手的热土豆, 鼓声停的时候, 手里有土豆的小孩就要出列。如果去掉鼓, 改为传过固定人数, 就成了“现代版”的约瑟夫问题传说犹太人反叛罗马人,落到困境,约瑟夫和39人决定殉难,坐成一圈儿,报数1~7,报到7的人由旁边杀死,结果约瑟夫给自己安排了个位置,最后活了下来……用队列来实现热土豆问题的算法, 参加游戏的人名列表, 以及传土豆次数num, 算法返
·
热土豆问题(约瑟夫问题)
“击鼓传花”的土豆版本
传烫手的热土豆, 鼓声停的时候, 手里有土豆的小孩就要出列。
如果去掉鼓, 改为传过固定人数, 就成了“现代版”的约瑟夫问题
传说犹太人反叛罗马人,落到困境,约瑟夫和39人决定殉难,坐成一圈儿,报数1~7,报到7的人由旁边杀死,结果约瑟夫给自己安排了个位置,最后活了下来……
用队列来实现热土豆问题的算法, 参加游戏的人名列表, 以及传土豆次数num, 算法返回最后剩下的人名

模拟程序采用队列来存放所有参加游戏的人名,按照传递土豆方向从队首排到队尾
游戏时,队首始终是持有土豆的人
模拟游戏开始, 只需要将队首的人出队, 随即再到队尾入队, 算是土豆的一次传递
传递了num次后,将队首的人移除,不再入队如此反复,直到队列中剩余1人
def hotPotato(namelist, num):
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name)
while simqueue.size() > 1:
for i in range(num):
simqueue.enqueue(simqueue.dequeue())
simqueue.dequeue()
return simqueue.dequeue()
print(hotPotato(["Bill", "David", "Susan", "Jane", "Kent", "Brad"], 7))
魔乐社区(Modelers.cn) 是一个中立、公益的人工智能社区,提供人工智能工具、模型、数据的托管、展示与应用协同服务,为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作,由全产业链共同建设、共同运营、共同享有,推动国产AI生态繁荣发展。
更多推荐



所有评论(0)