Fork me on GitHub

学点算法之队列的学习及应用

发表于 | 分类于 
这是崔斯特的第三十四篇原创文章

从约瑟夫问题开始说起 (๑• . •๑)

约瑟夫问题

约瑟夫问题

有 n 个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过 k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

问题是，给定了n和k，一开始要站在什么地方才能避免被处决？

这个问题是以弗拉维奥·约瑟夫命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

队列是什么

这道题有多种解法，这里先不说别的，要引出今天的主角——队列。队列的定义很好理解：

队列是项的有序结合，其中添加新项的一端称为队尾，移除项的一端称为队首。当一个元素从队尾进入队列时，一直向队首移动，直到它成为下一个需要移除的元素为止。

队列抽象数据类型由以下结构和操作定义。如上所述，队列被构造为在队尾添加项的有序集合，并且从队首移除。队列保持 FIFO 排序属性。 队列操作如下。

  • Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。
  • enqueue(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
  • dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。
  • isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。
  • size() 返回队列中的项数。它不需要参数，并返回一个整数。

队列的Python算法实现

为了实现队列抽象数据类型创建一个新类

pythonds/basic/queue.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(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)

想明白了其实就是对 list 的简单操作

如何活到最后

那我们回到上面的问题，如果是你，你要如何选择并活到最后呢？

我们的程序将输入名称列表和一个称为 num 常量用于报数。它将返回以 num 为单位重复报数后剩余的最后一个人的姓名。

假设第一个人是a。从他开始计数，a将先出列再入队列，把他放在队列的最后。经过 num 次的出队入队后，前面的人将被永久移除队列。并且另一个周期开始，继续此过程，直到只剩下一个名字（队列的大小为 1）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from pythonds.basic.queue import Queue
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(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], 7))
# output: f

其他解法

比较简单的做法是用循环单链表模拟整个过程，时间复杂度是O(n*m)。如果只是想求得最后剩下的人，则可以用数学推导的方式得出公式。先看看模拟过程的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# -*- coding: utf-8 -*- 
class Node(object):
	def __init__(self, value):
		self.value = value 
		self.next = None
def create_linkList(n):
	head = Node(1)
	pre = head
	for i in range(2, n+1):
		newNode = Node(i)
		pre.next= newNode
		pre = newNode
	pre.next = head
	return head
n = 5 #总的个数
m = 2 #数的数目
if m == 1: #如果是1的话，特殊处理，直接输出
	print(n)  
else:
	head = create_linkList(n)
	pre = None
	cur = head
	while cur.next != cur: #终止条件是节点的下一个节点指向本身
		for i in range(m-1):
			pre =  cur
			cur = cur.next
		print(cur.value)
		pre.next = cur.next
		cur.next = None
		cur = pre.next
	print(cur.value)

作业

假设实验室里有一台打印机供学生共性。当学生向共享打印机发送打印任务时，任务被放置在队列中以便以先来先服务的方式被处理。如何才能通过python程序模拟的方式得到每次提交任务的平均等待时间呢？（平均等待时间不包括打印本身的时间，仅指在队列中排队的时间。）
我们假定：

  • 学生们每次打印的页数在1到20页之间。
  • 打印机平均每小时会收到20个打印请求，即平均每180秒1个请求。
  • 每秒新增任务的可能性相等，即任务的产生为独立同分布
  • 打印机的打印速度恒定。

挖坑，要一起来填吗？