資源簡(jiǎn)介

(共35張PPT)
4.2基數(shù)排序
高中信息技術(shù)/教科版/選擇性必修1
目錄
1.創(chuàng)設(shè)情境，引入新課
2.體驗(yàn)探究，了解排隊(duì)取號(hào)
3.引導(dǎo)分析，建立數(shù)據(jù)結(jié)構(gòu)
4.設(shè)計(jì)算法，完成函數(shù)代碼
5.編程實(shí)現(xiàn)，模擬測(cè)試
6.課堂小結(jié)
1.創(chuàng)設(shè)情境，引入新課
這是什么設(shè)備？其主要功能是什么？主要應(yīng)用在哪些地方？
這是什么設(shè)備？其主要功能是什么？主要應(yīng)用在哪些地方？
本節(jié)圍繞“餐館排隊(duì)取號(hào)模擬系統(tǒng)”項(xiàng)目展開學(xué)習(xí)，通過(guò)項(xiàng)目活動(dòng)來(lái)了解餐館排隊(duì)取號(hào)模擬系統(tǒng)的基本思路，體驗(yàn)隊(duì)列在解決實(shí)際問(wèn)題中的作用。本節(jié)主要包含“模擬餐館排隊(duì)取號(hào)”和“編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng)”兩個(gè)任務(wù)。
2.體驗(yàn)探究，了解排隊(duì)取號(hào)
任務(wù)一模擬餐館排隊(duì)取號(hào) 活動(dòng)1體驗(yàn)餐館排隊(duì)取號(hào)
A012
你等候的是：2人桌
你前面等待人數(shù)：4人
過(guò)號(hào)作廢，請(qǐng)注意叫號(hào)。
取號(hào)時(shí)間：2018.6.8 12：08
小明和同學(xué)一起到餐館排隊(duì)就餐，拿到了如圖4.3.1所示的排號(hào)單。從排號(hào)單中可以看出，小明在“2人桌”中排在了
號(hào)，目前在此隊(duì)等候的共有 桌顧客。
在小明和同學(xué)等待就餐的過(guò)程中，沒(méi)有新顧客到來(lái)，“2人桌”叫號(hào)已經(jīng)叫到A010號(hào)，此時(shí)還有 桌顧客等候就餐。
圖4.3.1取號(hào)機(jī)和排號(hào)單
A012
4
2
餐館排隊(duì)取號(hào)包括取號(hào)和叫號(hào)兩個(gè)部分。
取號(hào)就是根據(jù)所選餐桌類型生成排隊(duì)號(hào)碼等信息將顧客入隊(duì)。
叫號(hào)就是根據(jù)空閑餐桌類型，將排在該餐桌類型隊(duì)列隊(duì)首的顧客出隊(duì)。
任務(wù)一模擬餐館排隊(duì)取號(hào) 活動(dòng)1體驗(yàn)餐館排隊(duì)取號(hào)
A012
你等候的是：2人桌
你前面等待人數(shù)：4人
過(guò)號(hào)作廢，請(qǐng)注意叫號(hào)。
取號(hào)時(shí)間：2018.6.8 12：08
小明和同學(xué)一起到餐館排隊(duì)就餐，拿到了如圖4.3.1所示的排號(hào)單。從排號(hào)單中可以看出，小明在“2人桌”中排在了
號(hào)，目前在此隊(duì)等候的共有 桌顧客。
在小明和同學(xué)等待就餐的過(guò)程中，沒(méi)有新顧客到來(lái)，“2人桌”叫號(hào)已經(jīng)叫到A010號(hào)，此時(shí)還有 桌顧客等候就餐。
圖4.3.1取號(hào)機(jī)和排號(hào)單
A012
4
2
任務(wù)一模擬餐館排隊(duì)取號(hào) 活動(dòng)2模擬排隊(duì)取號(hào)
假設(shè)餐館共有10張餐桌，“2人桌”5張，桌號(hào)1~5;“4人桌”3張，桌號(hào)6~8;“8人桌”2張，桌號(hào)9~10。為了區(qū)分不同的餐桌類型，排隊(duì)號(hào)碼的開頭用不同的字母表示?！?人桌”用A表示，“4人桌”用B表示，“8人桌”用C表示。
小明等兩人12:08來(lái)到餐館等待就餐，取到了A012號(hào)，排號(hào)單顯示前面有4組顧客等候，則表示“2人桌”等待隊(duì)列中有4組顧客，如圖4.3.2所示。
圖4.3.2 “A012”入隊(duì)
任務(wù)一模擬餐館排隊(duì)取號(hào) 活動(dòng)2模擬排隊(duì)取號(hào)
12:10時(shí)，系統(tǒng)叫號(hào)“A008”到5號(hào)桌就餐，表示空出一張“2人，排在“2人桌”隊(duì)首的顧客可以出隊(duì)就餐，如圖4.3.3所示。
圖4.3.3“A008”出隊(duì)
排在A008號(hào)的顧客排隊(duì)等候時(shí)間為 分鐘。
7
小梅等四人12:20來(lái)到餐館等待就餐，取到了“B008”號(hào)，當(dāng)前“4人桌”的排隊(duì)情況如圖4.3.4所示，請(qǐng)按照上面的思路將B008排進(jìn)隊(duì)列。
B008
12:20
隊(duì)首
原隊(duì)尾
新隊(duì)尾
分析以上模擬過(guò)程可以發(fā)現(xiàn)，餐館排隊(duì)取號(hào)入隊(duì)，總是排到不同餐桌類型的隊(duì)尾。叫號(hào)就餐，總是從不同餐桌類型的隊(duì)首開始。這個(gè)過(guò)程具有先進(jìn)先出的特點(diǎn)，可以使用隊(duì)列結(jié)構(gòu)作為實(shí)現(xiàn)排隊(duì)取號(hào)模擬系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)。
3.引導(dǎo)分析，建立數(shù)據(jù)結(jié)構(gòu)
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)1建立數(shù)據(jù)結(jié)構(gòu)
在排隊(duì)取號(hào)用餐的過(guò)程中，與顧客有關(guān)的信息包括顧客所選的餐桌類型、顧客的用餐時(shí)間、顧客取號(hào)時(shí)間等。為了方便處理這些信息和操作，定義顧客類Guest，其Python代碼如下。
01. class Guest: #定義顧客類
02.def __init__(self, tableType):
03.self.tableType=tableType #顧客所選餐桌類型
04.#隨機(jī)生成顧客用餐時(shí)間
05.self.stayTime=random.randrange(20，60)
06. #生成顧客取號(hào)信息
07.def takeTicket(self，number,order,timeTick)
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)1建立數(shù)據(jù)結(jié)構(gòu)
08.#根據(jù)餐桌類型、排隊(duì)號(hào)碼、等候人數(shù)生成排號(hào)單
09.self.ticket='%s%03d 前面還有%d位% (self.tableType.
10.number，order)
11.#餐桌類型和排隊(duì)號(hào)碼
12.self.tableTypeNum='%s%03d'% (self.tableType,number)
13.self.arriveTime=timeTick #顧客取號(hào)時(shí)間
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)1建立數(shù)據(jù)結(jié)構(gòu)
叫號(hào)過(guò)程中，需要根據(jù)餐桌類型和狀態(tài)，呼叫相應(yīng)餐桌隊(duì)列中的顧客到指定餐桌就餐。為了方便處理餐桌信息，定義餐桌類Table，其Python代碼如下。
14.class Table: #定義餐桌類
15.def __init__(self, id, type):
16.self.id=id #餐桌桌號(hào)
17.self.type=type #餐桌類型('A'，'B'，'C'，)
18.self.status='free’ #餐桌狀態(tài)(free，busy)
19.self.remain=0 #顧客占用時(shí)長(zhǎng)
20.def setBusy(self，remain): #設(shè)置餐桌狀態(tài)
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)1建立數(shù)據(jù)結(jié)構(gòu)
21.self.status='busy’#設(shè)置桌子為“在用”狀態(tài)
22.self.remain=remain #設(shè)置占用時(shí)長(zhǎng)
23.def tickRemain(self): #餐桌用餐狀態(tài)檢測(cè)
24.if self.remain>0: #判斷是否還有占用時(shí)長(zhǎng)
25.self.remain-=1 #占用時(shí)長(zhǎng)減少1
26.if self.remain==0: #判斷占用時(shí)長(zhǎng)是否為零
27.self.status='free #設(shè)置桌子為“空閑”狀態(tài)
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)1建立數(shù)據(jù)結(jié)構(gòu)
排隊(duì)取號(hào)模擬系統(tǒng)的核心是實(shí)現(xiàn)取號(hào)和叫號(hào)功能，為了方便實(shí)現(xiàn)排號(hào)和取號(hào)的操作，定義排號(hào)機(jī)類QueueSystem。排隊(duì)取號(hào)過(guò)程中，需要根據(jù)不同的就餐人數(shù)選擇在相應(yīng)的餐桌隊(duì)列中排隊(duì)，根據(jù)任務(wù)一活動(dòng)2的描述，需要建立三個(gè)隊(duì)列，分別用來(lái)存放A、B、C三種餐桌類型的排隊(duì)顧客Guest對(duì)象。為了方便處理，創(chuàng)建隊(duì)列字典guestOueues和排隊(duì)號(hào)碼字典guestCount，其Python代碼如下。
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)1建立數(shù)據(jù)結(jié)構(gòu)
28.class QueueSystem: #定義排號(hào)機(jī)類
29.def __init__(self): #排號(hào)機(jī)構(gòu)造函數(shù)
30.#顧客隊(duì)列
31.self.guestQueues={'A': Queue( )，'B': Queue()，'c': Queue()}
32.self.guestCount={'A':0 ,'B': 0,'C': 0} #排隊(duì)號(hào)碼
33.self.totalwaitTime=0 #總等待時(shí)間
34.self.totalGuest=0 #總就餐次數(shù)
4.設(shè)計(jì)算法，完成函數(shù)代碼
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)2設(shè)計(jì)算法
排號(hào)機(jī)取號(hào)過(guò)程的算法描述如下：
(1) 根據(jù)顧客所選餐桌類型，生成該餐桌類型的排隊(duì)號(hào)碼。
(2) 生成顧客取號(hào)信息。
(3) 顧客入隊(duì)。
(4)顯示取號(hào)信息。
根據(jù)上述算法，定義取號(hào)函數(shù)assignTicket(self,guest,timeTick),參數(shù)self表示取號(hào)機(jī)，參數(shù)guest表示取號(hào)的顧客，timeTick表示取號(hào)的時(shí)間。請(qǐng)補(bǔ)全下面的代碼。
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)2設(shè)計(jì)算法
35. def assignTicket(self， guest，timeTick): #取號(hào)函數(shù)
36.table=guest.tableType #顧客的餐桌類型
37.queue=self.guestQueues[table] #顧客所排的餐桌隊(duì)列
38.self.guestCount[table]+=1 #生成排隊(duì)號(hào)碼
39.guest.takeTicket(self.guestCount[table]， queue.size(),
40.timeTick) #顧客取號(hào)
41.queue.enQueue( )#顧客入隊(duì)
42.#顯示顧客取號(hào)信息
43.print(‘顧客取號(hào)’:，guest.ticket，‘取號(hào)時(shí)間’:,timeTick)
guest
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)2設(shè)計(jì)算法
叫號(hào)過(guò)程的算法描述如下。
(1) 可以用餐餐桌類型隊(duì)列中的顧客出隊(duì)。
(2) 設(shè)置就餐餐桌的狀態(tài)和用餐時(shí)間。
(3)累計(jì)用餐總?cè)藬?shù)和總等待時(shí)間。
(4)顯示叫號(hào)信息。
根據(jù)上述算法，定義叫號(hào)函數(shù)arrangeTable(self,table,timeTick),參數(shù)self表示取號(hào)機(jī)，參數(shù)table表示可以用餐的餐桌，timeTick表示叫號(hào)的時(shí)間。請(qǐng)補(bǔ)全下面的代碼。
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)2設(shè)計(jì)算法
44.def arrangeTable(self， table， timeTick): #叫號(hào)函數(shù)
45 .#判斷隊(duì)列是否為空
46.if not self.guestQueues[table.type].isEmpty():
47#顧客出隊(duì)
48.guest=self.guestQueues[table.type]. .
49.table.setBusy(guest.stayTime) #設(shè)置餐桌狀態(tài)為占用
50.self.totalGuest+=1 #累計(jì)用餐總次數(shù)
deQueue( )
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)2設(shè)計(jì)算法
51.#累計(jì)總等待時(shí)間
52.self.totalwaitTime+=timeTick-guest.arriveTime
53.#顯示叫號(hào)信息
54.print('叫號(hào):’，guest.tableTypeNum，"到桌號(hào)’:，table.id)
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)2設(shè)計(jì)算法
顯示模擬系統(tǒng)統(tǒng)計(jì)信息
定義函數(shù)showResult(self,totalTime)，參數(shù)self表示取號(hào)機(jī)，參數(shù)totalTime表示模擬的總時(shí)長(zhǎng)，代碼如下。
55. def showResult(self， totalTime): #顯示模擬信息函數(shù)
56.print('*'*40) #輸出一行*
57.print('本次模擬一共’，totalTime，‘分鐘’) #顯示模擬總時(shí)長(zhǎng)
58.#顯示模擬期間總用餐桌數(shù)58
59.print('共有’，self.totalGuest，只桌顧客用餐')
60.#顧客平均等待時(shí)間
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)2設(shè)計(jì)算法
61.print(每桌顧客平均等待時(shí)間為'， round(self.totalwaitTime
62./self.totalGuest)，‘分鐘')
63.print('模擬結(jié)束時(shí)各隊(duì)列情況如下:’)
64.for q in self.guestQueues: #顯示各隊(duì)列剩余排隊(duì)情況
65.print('桌型:’，9,'還有'，self.guestQueues[q].size()，‘桌
66.顧客在排隊(duì)')
67.print('*'*40) #輸出一行*
5.編程實(shí)現(xiàn)，模擬測(cè)試
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)3編程實(shí)現(xiàn)
活動(dòng)2已經(jīng)完成了排隊(duì)取號(hào)模擬系統(tǒng)基本功能的算法設(shè)計(jì)和代碼實(shí)現(xiàn)，接下來(lái)利用排隊(duì)取號(hào)系統(tǒng)模擬餐館就餐客流排隊(duì)情況。首先，我們確定模擬系統(tǒng)的時(shí)間流逝，是一個(gè)以分鐘為單位的整數(shù)增長(zhǎng)過(guò)程。然后，在每一分鐘內(nèi)，模擬下列事件：(1)用隨機(jī)數(shù)按照一定的概率來(lái)確定是否有顧客排隊(duì)取號(hào)就餐;
(2) 如果有顧客排隊(duì)取號(hào)，用隨機(jī)數(shù)按照一定概率決定就餐餐桌的類型，執(zhí)行取號(hào);
(3) 檢查餐桌狀態(tài)，如果有餐桌可以就餐，則執(zhí)行叫號(hào);4)顯示模擬統(tǒng)計(jì)信息。
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)3編程實(shí)現(xiàn)
排隊(duì)取號(hào)模擬系統(tǒng)的主程序代碼如下，請(qǐng)補(bǔ)全下面的代碼。
68.import random
69.#變量randomBox用于設(shè)定模擬來(lái)客的概率，20%概率2人桌，10%概率4人
70.桌，5%概率8人桌
71.randomBox=[None]*65+['A']*20+[B']*10+['C']*5
72.#餐桌設(shè)置，5張2人桌，3張4人桌，2張8人桌
73.tableSetting='AAAAABBBCC’
74.#生成餐桌對(duì)象列表
75. tableList=[Table(i+1, tableSetting[i]) for i in range
76.(len(tableSetting))]
77.qsys= #生成一個(gè)排號(hào)機(jī)對(duì)象
Queue System( )
78.totalTime=4 *60 #模擬時(shí)間長(zhǎng)度為4小時(shí)，最小單位為分鐘
79. for timeTick in range( )#按分鐘進(jìn)行迭代循環(huán)
80.dice=random.choice(randomBox) #以設(shè)定概率隨機(jī)模擬來(lái)客
81.if dice is not None: #判斷是否有顧客來(lái)
82.guest= #生成顧客對(duì)象
83.qsys.assignTicket(guest，timeTick) #顧客取號(hào)
84.for table in tableList:
85.table.tickRemain() #餐桌用餐狀態(tài)檢測(cè)
86.if table.status=='free':
87.qsys.arrangeTable(table,timeTick) #叫號(hào)入桌
88. qsys.showResult(totalTime) #顯示模擬統(tǒng)計(jì)信息
totalTime
dice
任務(wù)二 編程實(shí)現(xiàn)餐館排隊(duì)取號(hào)模擬系統(tǒng) 活動(dòng)3編程實(shí)現(xiàn)
將上述代碼輸入一個(gè)文件，執(zhí)行該程序，顯示的模擬系統(tǒng)統(tǒng)計(jì)信息如圖4.3.5所示。
圖4.35 顯示模擬系統(tǒng)統(tǒng)計(jì)信息
依據(jù)排隊(duì)取號(hào)模擬系統(tǒng)計(jì)算出顧客平均等待時(shí)間，可以通過(guò)修改餐桌的種類和數(shù)量tableSetting、顧客的構(gòu)成概率randomBox，來(lái)優(yōu)化餐桌配給，減少顧客等待時(shí)間，提高滿意度。
6.課堂小結(jié)
本節(jié)課我們主要學(xué)習(xí)了排隊(duì)取號(hào)模擬系統(tǒng)的基本功能、排隊(duì)區(qū)號(hào)模擬系統(tǒng)的基本算法思想及代碼實(shí)現(xiàn)的方法。
作業(yè)布置：請(qǐng)同學(xué)們認(rèn)真完成教材中的拓展練習(xí)哦！
下節(jié)課見！

展開更多......

收起↑