用队列模拟打印任务&实现约瑟夫斯问题-python

妖狐艹你老母 2023-07-16 10:58 5阅读 0赞

> 《Python数据结构与算法分析》（第二版）

实现队列：用列表实现队列，假设列表的位置0处为队尾，则利用列表的insert操作实现入队，用列表的pop操作实现出队。

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)

**1.实现约瑟夫斯问题**  
约瑟夫斯当年和39各战友在山洞中对抗罗马军队。在即将失败时，他们决定自杀。他们围成一圈，从某个人开始，按顺时针方向杀掉第七个人。约瑟夫斯找到了自己应该站的位置，活到了最后。

from pyQueue import Queue
    
    
    def Josephus(namelist, num):#namelist是一个名字列表，num代表第几个位置的人出局
        simqueue = Queue()#创建一个队列
        for name in namelist:#把名字列表逐个导入队列
            simqueue.enqueue(name)
    
        while simqueue.size() > 1:#当还剩余人数大于1时，继续淘汰处于num位置上的人
            for i in range(num):#不在位置num处的人，先从队头出队，再从队尾入队
                simqueue.enqueue(simqueue.dequeue())
    
            simqueue.dequeue()#位置num处的人出局
    
        return simqueue.dequeue()#最后一个幸存者出队
    
    
    namelist = ['BILL', 'DAVID', 'SUSAN', 'JANE', 'KENT', 'BRAD']
    num = 7
    
    print(Josephus(namelist, num))

实现结果：  
![在这里插入图片描述][20200318170051760.PNG]

**2. 模拟打印任务：**  
一个实验室内：在任何给定的一个小时内，实验室里都约有10个学生。他们在这一个小时内最多打印2次，并且打印的页数从1到20不等。实验室内只有1台打印机且比较老旧，每分钟只能以低质量打印10页，或者提高质量打印5页。降低打印速度可能导致学生等待时间过长，这里计算学生平均需要等待多长时间才能拿到打印好的文章。

> 说明：
> 
> 1.  学生打印的文章可能有1-20页，如果各页数出现的概率相等，那么实际打印任务的时长可以通过1-20的一个随机数来模拟。
> 2.  如果实验室里有10个学生，并且在一个小时内，每个人都打印两次，那么平均每小时就有20个打印任务，相当于每180秒1个任务，故可以通过1-180的一个随机数来模拟每秒内产生打印任务的概率。如果随机数正好是180，那么久认为有一个打印任务被创建。

**主要模拟步骤**：  
（1）创建一个打印任务队列。每一个人物到来时都会有一个时间戳。一开始，队列是空的。  
（2）**针对每一秒(currentsecond)**，执行以下操作：

*  是否有新创建的打印任务？如果是，以currentsecond作为其时间戳并将该任务加入到队列中。
 *  如果打印机空闲，并且有正在等待执行的任务，执行以下操作：
 *  从队列中取出第一个任务并提交给打印机；
 *  用currentsecond减去该任务的时间戳，以此计算等待时间；
 *  将该任务的等待时间存入一个列表，以后备用；
 *  根据该任务的页数，计算执行时间
 *  打印机进行一秒的打印，同时从该任务的执行时间中减去一秒。
 *  如果打印任务执行完毕，或者说任务需要的时间减为0，则说明打印机回到空闲状态。

（3）当模拟完成之后，根据等待时间列表中的值计算平均等待时间。

**Python实现：**

*  创建3个类：Printer、Task、和 printQueue。他们分别模拟打印机、打印任务和队列，其中printQueue对象是队列抽象数据类型的实例。
 *  创建打印任务模拟程序simulation，布尔辅助函数newPrintTask判断是否有新创建的打印任务。

# !/user/bin env python
    # coding:utf-8
    from pyQueue import Queue
    import random
    
    
    class Printer:
        def __init__(self, ppm):
            self.pagerate = ppm#每分钟打印的页数
            self.currentTask = None
            self.timeRemaining = 0#完成任务需要的时间
    
        def tick(self):#进行减量计时
            if self.currentTask != None:
                self.timeRemaining = self.timeRemaining - 1
                if self.timeRemaining <= 0:#打印完成后，设置打印机为空闲状态
                    self.currentTask = None
    
        def busy(self):#判断打印机是否忙碌
            if self.currentTask != None:
                return True
            else:
                return False
    
        def startNext(self, newTask):#开始下一个打印任务
            self.currentTask = newTask
            self.timeRemaining = newTask.getPages() * 60 / self.pagerate
            #设置当前打印任务需要的时间
    
    
    class Task:
        def __init__(self, time):
            self.timeStamp = time#新创建任务的时间戳，currentsecond
            self.pages = random.randrange(1, 21)
    
        def getStamp(self):
            return self.timeStamp
    
        def getPages(self):
            return self.pages
    
        def waitTime(self, currenttime):#等待时间
            return currenttime - self.timeStamp
    
    
    def simulation(numSeconds, pagesPerMinute):
        labprinter = Printer(pagesPerMinute)
        printQueue = Queue()
        waitingtimes = []
    
        for currentsecond in range(numSeconds):#针对每一秒，都进行步骤(2)所列操作
            if newPrintTask():
                task = Task(currentsecond)
                printQueue.enqueue(task)
    
            if (not labprinter.busy()) and (not printQueue.isEmpty()):
                nextTask = printQueue.dequeue()
                waitingtimes.append(nextTask.waitTime(currentsecond))
                labprinter.startNext(nextTask)
    
            labprinter.tick()
    
        averageWait = sum(waitingtimes) / len(waitingtimes)
        print("Average Wait %6.2f secs %3d tasks remaining." \
              %(averageWait, printQueue.size()))
    
    
    def newPrintTask():
        num = random.randrange(1, 181)
        if num == 180:
            return True
        else:
            return False
    
    
    for i in range(10):#模拟60分钟(3600秒)内打印速度为每分钟5(10)页
                       #并进行10次这样的模拟(只是模拟60分钟，而不是真的需要60分钟）
        # simulation(3699, 5)
        simulation(3600, 10)

模拟结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70 1]

> 由于使用了随机数，每次模拟返回的结果都不同，但明显可以看出加快打印速度后，每小时能完成更多的打印任务。

[20200318170051760.PNG]: /images/20230528/661154f12f744848b19667f25cd23f30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70]: /images/20230528/d7b437c1b60b4063b25b9f9461478b27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70 1]: /images/20230528/3fd54a0d11594b11a09b689ec463c817.png