資源簡介

(共14張PPT)
隊列的應用（第八課時）
冊 別：選擇性必修1
學 科：高中信息技術（浙教版）
隊列的應用
小藝是一家健身房管理人員，她負責記錄、分析健身器材的使用情況。她以數字的形式記錄了某客戶每天使用時間最長的器材種類，如“3，1，1，2，2，1，3，1，2，2，3”，1代表跑步機，2代表動感單車，3代表握力器等。針對該客戶的數字記錄，小藝想知道，一段時間內該客戶最喜愛用的2種器材，以及最長的連續天數。要求符合條件的答案中，連續的天數中不能出現第3種器材。如有多種符合條件的答案，輸出最開始出現的。
隊列的應用
任務一：對于某客戶的記錄“3，1，1，2，2，1，3，1，2，2，3”，請以表格的形式，統計2種器材的連續段，并記錄時間長度，找出最長時間段及器材種類。
連續2種器材序號
器材種類
長度
3，1，1，2，2，1，3，1，2，2，3
抽象與建模：
連續2種器材序號 3,1,1 1,1,2,2,1 1,3,1 1,2,2 2,2,3
器材種類 3，1 1，2 1，3 1，2 2，3
長度 3 5 3 3 3
3，1，1，2，2，1，3，1，2，2，3
抽象與建模：
連續2種器材序號 3,1,1 1,1,2,2,1 1,3,1 1,2,2 2,2,3
器材種類 3，1 1，2 1，3 1，2 2，3
長度 3 5 3 3 3
任務二：請設計數據結構與算法，計算出最長連續時間段及器材種類。
3，1，1，2，2，1，3，1，2，2，3
抽象與建模：
連續2種器材序號 3,1,1 1,1,2,2,1 1,3,1 1,2,2 2,2,3
器材種類 3，1 1，2 1，3 1，2 2，3
長度 3 5 3 3 3
任務二：請設計數據結構與算法，計算出最長連續時間段及器材種類。
3，1，1，2，2，1，3，1，2，2，3
算法設計：
由得到各種方案的過程可知，從左往右處理輸入數據時，表格中右端的數據，在不斷進入，左端的數據在不斷的出。當只有2種數字時，得到一種方案。由此，可以用隊列結構來處理該問題。
器材種類 3 1 1 2 2 1 3 1 2 2 3
① 3
3 1
3 1 1
② 1 1 2
1 1 2 2
1 1 2 2 1
③ 1 3
1 3 1
④ 1 2
1 2 2
⑤ 2 2 3
算法設計：
3，1，1，2，2，1，3，1，2，2，3
3
3 1
3 1 1
1 1 2
1.隊列que,頭指針變量head,尾指針變量tail；隊列中的兩種器材種類x,y；種類1的長度num1，種類2的長度num2；
2.從左往右處理輸入數據，先把同一種類的器材壓進隊列，種類記錄x，長度為num1;再把第一個y壓進隊列，長度num2=1。
3.再逐步處理輸入數據i，如果與x或y一樣，直接入隊；不一樣時，則把隊首元素出隊，直至num1=0或num2=0，使得隊列中只剩下一個種類。
4.再把數據i壓入隊列，當num1=0時，則當成新的x,num1=1; 否則當成新的y,num2=0。
算法設計：
1.隊列queue,頭指針變量head,尾指針變量tail；隊列中的兩種器材種類x,y；種類1的長度num1，種類2的長度num2；
2.從左往右處理輸入數據，先把同一種類的器材壓進隊列，種類記錄x，長度為num1;再把第一個y壓進隊列，長度num2=1。
3.再逐步處理輸入數據i，如果與x或y一樣，直接入隊；不一樣時，則把隊首元素出隊，直至num1=0或num2=0，使得隊列中只剩下一個種類。
4.再把數據i壓入隊列，當num1=0時，則當成新的x,num1=1; 否則當成新的y,num2=0。
任務三：根據算法設計，請用Pytho語言實現該任務。
程序實現：
1.輸入數據，新建隊列，頭尾指針變量初始化。
a=list(map(int,input().split()))
n=len(a)
que=[0]*(n+1)
head=0;tail=0;xm1="";xm2=""
3，1，1，2，2，1，3，1，2，2，3
程序實現：
2.把所有第一種類種的器材x和第一個y類的器材壓入隊列
que[tail]=a[0];tail+=1
i=1
while a[i]==que[tail-1]:
que[tail]=a[i]
i+=1
tail+=1
max1=tail
x=que[head];y=a[i]
que[tail]=y;tail+=1
num1=tail-1;num2=1
3，1，1，2，2，1，3，1，2，2，3
程序實現：
3.再逐步處理剩余的器材
while ii+=1
que[tail]=a[i];tail+=1
if a[i]==x or a[i]==y:
if max1max1=tail+head
xm1=x;xm2=y
if a[i]==x:
num1+=1
else:
num2+=1
else:
while num1>0 and num2>0:
if que[head]==x:
num1-=1
else:
num2-=1
head+=1
if num1==0:
x=a[i]
num1=1
else:
y=a[i]
num2=1
print("最喜歡的項目為：",xm1,"和",xm2,"持續時長：",max1,"天")
3，1，1，2，2，1，3，1，2，2，3
總結
對于蘊含隊列結構特性的生活、學習實例，都可以采用隊列來解決。
同學們，再見

展開更多......

收起↑