前提条件:队列的实现:
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.item == []
def enqueue(self,item):
self.items.append(item)
def dequeue(self):
self.items.pop(0)
def size(self):
return len(self.items)
考虑下面的问题:
Bill David Susan Jane Kent Brad 六个人,按照这样的顺序,传递一个土豆并报数,当遇到某个数字时,这个人就要退出游戏,假定我们遇到的退出数字为7,请问在这个位置的条件下,谁能留到最后呢?(Bill从0开始报数)
可以用队列来解决这个问题,这几个人“排队”就类似于队列的一种组合。先来看第一次传土豆的顺序,土豆用P表示,把带土豆的那个人看作队首,如:
Bill(P) David Susan Jane Kent Brad David(P) Susan Jane Kent Brad Bill
发现在这里这几个人的排队方式类似于一个环状的结构,上次的队首会在下次变成队伍末尾的元素,所以我们不妨在处理的过程中把队首的元素弹出,再把弹出的元素添加到末尾,这是最关键的一步。
所以整体的分析如下:
首先,定义一个队列,让人按照顺序入队,其代码段如:
def hotPotato(namelist,num):
s = Queue()
i=1
for name in namelist:
s.enqueue(name)
然后,开始传土豆的模拟部分,只要队伍不为空,我们就可以把队伍中队首的元素弹出,从上面的叙述可以看出,从现在手里拿土豆的人的角度来看,这个人在队伍的末尾,添加到末尾去。
while s.size()>1:
for i in range(num):
s.enqueue(s.dequeue())
这个循环的过程类似于报数的过程,Bill报0,报完之后被扔到末尾去,接着David报1,Susan报2,即循环的i就是每个人报的数,我们在这里以题目中的7为例,i的取值有0,1,2,3,4,5,6七个,也就是说,循环停止后,整个队列的头部就是要退出游戏的人,因而在退出循环后,我们要请队首的人出队,其代码如:(注意要和前面的循环对齐)
s.dequeue()
接下来,循环一直运行,直到整个队伍里只剩下最后一个人,因此我们这个函数只需要返回最后一个人的名字就可以了,如:
return s.dequeue()
把上面的代码组合起来,就是我们整个的传土豆的函数。