资源简介

(共35张PPT)
4.2基数排序
高中信息技术/教科版/选择性必修1
目录
1.创设情境，引入新课
2.体验探究，了解排队取号
3.引导分析，建立数据结构
4.设计算法，完成函数代码
5.编程实现，模拟测试
6.课堂小结
1.创设情境，引入新课
这是什么设备？其主要功能是什么？主要应用在哪些地方？
这是什么设备？其主要功能是什么？主要应用在哪些地方？
本节围绕“餐馆排队取号模拟系统”项目展开学习，通过项目活动来了解餐馆排队取号模拟系统的基本思路，体验队列在解决实际问题中的作用。本节主要包含“模拟餐馆排队取号”和“编程实现餐馆排队取号模拟系统”两个任务。
2.体验探究，了解排队取号
任务一模拟餐馆排队取号 活动1体验餐馆排队取号
A012
你等候的是：2人桌
你前面等待人数：4人
过号作废，请注意叫号。
取号时间：2018.6.8 12：08
小明和同学一起到餐馆排队就餐，拿到了如图4.3.1所示的排号单。从排号单中可以看出，小明在“2人桌”中排在了
号，目前在此队等候的共有 桌顾客。
在小明和同学等待就餐的过程中，没有新顾客到来，“2人桌”叫号已经叫到A010号，此时还有 桌顾客等候就餐。
图4.3.1取号机和排号单
A012
4
2
餐馆排队取号包括取号和叫号两个部分。
取号就是根据所选餐桌类型生成排队号码等信息将顾客入队。
叫号就是根据空闲餐桌类型，将排在该餐桌类型队列队首的顾客出队。
任务一模拟餐馆排队取号 活动1体验餐馆排队取号
A012
你等候的是：2人桌
你前面等待人数：4人
过号作废，请注意叫号。
取号时间：2018.6.8 12：08
小明和同学一起到餐馆排队就餐，拿到了如图4.3.1所示的排号单。从排号单中可以看出，小明在“2人桌”中排在了
号，目前在此队等候的共有 桌顾客。
在小明和同学等待就餐的过程中，没有新顾客到来，“2人桌”叫号已经叫到A010号，此时还有 桌顾客等候就餐。
图4.3.1取号机和排号单
A012
4
2
任务一模拟餐馆排队取号 活动2模拟排队取号
假设餐馆共有10张餐桌，“2人桌”5张，桌号1~5;“4人桌”3张，桌号6~8;“8人桌”2张，桌号9~10。为了区分不同的餐桌类型，排队号码的开头用不同的字母表示。“2人桌”用A表示，“4人桌”用B表示，“8人桌”用C表示。
小明等两人12:08来到餐馆等待就餐，取到了A012号，排号单显示前面有4组顾客等候，则表示“2人桌”等待队列中有4组顾客，如图4.3.2所示。
图4.3.2 “A012”入队
任务一模拟餐馆排队取号 活动2模拟排队取号
12:10时，系统叫号“A008”到5号桌就餐，表示空出一张“2人，排在“2人桌”队首的顾客可以出队就餐，如图4.3.3所示。
图4.3.3“A008”出队
排在A008号的顾客排队等候时间为 分钟。
7
小梅等四人12:20来到餐馆等待就餐，取到了“B008”号，当前“4人桌”的排队情况如图4.3.4所示，请按照上面的思路将B008排进队列。
B008
12:20
队首
原队尾
新队尾
分析以上模拟过程可以发现，餐馆排队取号入队，总是排到不同餐桌类型的队尾。叫号就餐，总是从不同餐桌类型的队首开始。这个过程具有先进先出的特点，可以使用队列结构作为实现排队取号模拟系统的数据结构。
3.引导分析，建立数据结构
任务二 编程实现餐馆排队取号模拟系统 活动1建立数据结构
在排队取号用餐的过程中，与顾客有关的信息包括顾客所选的餐桌类型、顾客的用餐时间、顾客取号时间等。为了方便处理这些信息和操作，定义顾客类Guest，其Python代码如下。
01. class Guest: #定义顾客类
02.def __init__(self, tableType):
03.self.tableType=tableType #顾客所选餐桌类型
04.#随机生成顾客用餐时间
05.self.stayTime=random.randrange(20，60)
06. #生成顾客取号信息
07.def takeTicket(self，number,order,timeTick)
任务二 编程实现餐馆排队取号模拟系统 活动1建立数据结构
08.#根据餐桌类型、排队号码、等候人数生成排号单
09.self.ticket='%s%03d 前面还有%d位% (self.tableType.
10.number，order)
11.#餐桌类型和排队号码
12.self.tableTypeNum='%s%03d'% (self.tableType,number)
13.self.arriveTime=timeTick #顾客取号时间
任务二 编程实现餐馆排队取号模拟系统 活动1建立数据结构
叫号过程中，需要根据餐桌类型和状态，呼叫相应餐桌队列中的顾客到指定餐桌就餐。为了方便处理餐桌信息，定义餐桌类Table，其Python代码如下。
14.class Table: #定义餐桌类
15.def __init__(self, id, type):
16.self.id=id #餐桌桌号
17.self.type=type #餐桌类型('A'，'B'，'C'，)
18.self.status='free’ #餐桌状态(free，busy)
19.self.remain=0 #顾客占用时长
20.def setBusy(self，remain): #设置餐桌状态
任务二 编程实现餐馆排队取号模拟系统 活动1建立数据结构
21.self.status='busy’#设置桌子为“在用”状态
22.self.remain=remain #设置占用时长
23.def tickRemain(self): #餐桌用餐状态检测
24.if self.remain>0: #判断是否还有占用时长
25.self.remain-=1 #占用时长减少1
26.if self.remain==0: #判断占用时长是否为零
27.self.status='free #设置桌子为“空闲”状态
任务二 编程实现餐馆排队取号模拟系统 活动1建立数据结构
排队取号模拟系统的核心是实现取号和叫号功能，为了方便实现排号和取号的操作，定义排号机类QueueSystem。排队取号过程中，需要根据不同的就餐人数选择在相应的餐桌队列中排队，根据任务一活动2的描述，需要建立三个队列，分别用来存放A、B、C三种餐桌类型的排队顾客Guest对象。为了方便处理，创建队列字典guestOueues和排队号码字典guestCount，其Python代码如下。
任务二 编程实现餐馆排队取号模拟系统 活动1建立数据结构
28.class QueueSystem: #定义排号机类
29.def __init__(self): #排号机构造函数
30.#顾客队列
31.self.guestQueues={'A': Queue( )，'B': Queue()，'c': Queue()}
32.self.guestCount={'A':0 ,'B': 0,'C': 0} #排队号码
33.self.totalwaitTime=0 #总等待时间
34.self.totalGuest=0 #总就餐次数
4.设计算法，完成函数代码
任务二 编程实现餐馆排队取号模拟系统 活动2设计算法
排号机取号过程的算法描述如下：
(1) 根据顾客所选餐桌类型，生成该餐桌类型的排队号码。
(2) 生成顾客取号信息。
(3) 顾客入队。
(4)显示取号信息。
根据上述算法，定义取号函数assignTicket(self,guest,timeTick),参数self表示取号机，参数guest表示取号的顾客，timeTick表示取号的时间。请补全下面的代码。
任务二 编程实现餐馆排队取号模拟系统 活动2设计算法
35. def assignTicket(self， guest，timeTick): #取号函数
36.table=guest.tableType #顾客的餐桌类型
37.queue=self.guestQueues[table] #顾客所排的餐桌队列
38.self.guestCount[table]+=1 #生成排队号码
39.guest.takeTicket(self.guestCount[table]， queue.size(),
40.timeTick) #顾客取号
41.queue.enQueue( )#顾客入队
42.#显示顾客取号信息
43.print(‘顾客取号’:，guest.ticket，‘取号时间’:,timeTick)
guest
任务二 编程实现餐馆排队取号模拟系统 活动2设计算法
叫号过程的算法描述如下。
(1) 可以用餐餐桌类型队列中的顾客出队。
(2) 设置就餐餐桌的状态和用餐时间。
(3)累计用餐总人数和总等待时间。
(4)显示叫号信息。
根据上述算法，定义叫号函数arrangeTable(self,table,timeTick),参数self表示取号机，参数table表示可以用餐的餐桌，timeTick表示叫号的时间。请补全下面的代码。
任务二 编程实现餐馆排队取号模拟系统 活动2设计算法
44.def arrangeTable(self， table， timeTick): #叫号函数
45 .#判断队列是否为空
46.if not self.guestQueues[table.type].isEmpty():
47#顾客出队
48.guest=self.guestQueues[table.type]. .
49.table.setBusy(guest.stayTime) #设置餐桌状态为占用
50.self.totalGuest+=1 #累计用餐总次数
deQueue( )
任务二 编程实现餐馆排队取号模拟系统 活动2设计算法
51.#累计总等待时间
52.self.totalwaitTime+=timeTick-guest.arriveTime
53.#显示叫号信息
54.print('叫号:’，guest.tableTypeNum，"到桌号’:，table.id)
任务二 编程实现餐馆排队取号模拟系统 活动2设计算法
显示模拟系统统计信息
定义函数showResult(self,totalTime)，参数self表示取号机，参数totalTime表示模拟的总时长，代码如下。
55. def showResult(self， totalTime): #显示模拟信息函数
56.print('*'*40) #输出一行*
57.print('本次模拟一共’，totalTime，‘分钟’) #显示模拟总时长
58.#显示模拟期间总用餐桌数58
59.print('共有’，self.totalGuest，只桌顾客用餐')
60.#顾客平均等待时间
任务二 编程实现餐馆排队取号模拟系统 活动2设计算法
61.print(每桌顾客平均等待时间为'， round(self.totalwaitTime
62./self.totalGuest)，‘分钟')
63.print('模拟结束时各队列情况如下:’)
64.for q in self.guestQueues: #显示各队列剩余排队情况
65.print('桌型:’，9,'还有'，self.guestQueues[q].size()，‘桌
66.顾客在排队')
67.print('*'*40) #输出一行*
5.编程实现，模拟测试
任务二 编程实现餐馆排队取号模拟系统 活动3编程实现
活动2已经完成了排队取号模拟系统基本功能的算法设计和代码实现，接下来利用排队取号系统模拟餐馆就餐客流排队情况。首先，我们确定模拟系统的时间流逝，是一个以分钟为单位的整数增长过程。然后，在每一分钟内，模拟下列事件：(1)用随机数按照一定的概率来确定是否有顾客排队取号就餐;
(2) 如果有顾客排队取号，用随机数按照一定概率决定就餐餐桌的类型，执行取号;
(3) 检查餐桌状态，如果有餐桌可以就餐，则执行叫号;4)显示模拟统计信息。
任务二 编程实现餐馆排队取号模拟系统 活动3编程实现
排队取号模拟系统的主程序代码如下，请补全下面的代码。
68.import random
69.#变量randomBox用于设定模拟来客的概率，20%概率2人桌，10%概率4人
70.桌，5%概率8人桌
71.randomBox=[None]*65+['A']*20+[B']*10+['C']*5
72.#餐桌设置，5张2人桌，3张4人桌，2张8人桌
73.tableSetting='AAAAABBBCC’
74.#生成餐桌对象列表
75. tableList=[Table(i+1, tableSetting[i]) for i in range
76.(len(tableSetting))]
77.qsys= #生成一个排号机对象
Queue System( )
78.totalTime=4 *60 #模拟时间长度为4小时，最小单位为分钟
79. for timeTick in range( )#按分钟进行迭代循环
80.dice=random.choice(randomBox) #以设定概率随机模拟来客
81.if dice is not None: #判断是否有顾客来
82.guest= #生成顾客对象
83.qsys.assignTicket(guest，timeTick) #顾客取号
84.for table in tableList:
85.table.tickRemain() #餐桌用餐状态检测
86.if table.status=='free':
87.qsys.arrangeTable(table,timeTick) #叫号入桌
88. qsys.showResult(totalTime) #显示模拟统计信息
totalTime
dice
任务二 编程实现餐馆排队取号模拟系统 活动3编程实现
将上述代码输入一个文件，执行该程序，显示的模拟系统统计信息如图4.3.5所示。
图4.35 显示模拟系统统计信息
依据排队取号模拟系统计算出顾客平均等待时间，可以通过修改餐桌的种类和数量tableSetting、顾客的构成概率randomBox，来优化餐桌配给，减少顾客等待时间，提高满意度。
6.课堂小结
本节课我们主要学习了排队取号模拟系统的基本功能、排队区号模拟系统的基本算法思想及代码实现的方法。
作业布置：请同学们认真完成教材中的拓展练习哦！
下节课见！

展开更多......

收起↑