资源简介

(共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
总结
对于蕴含队列结构特性的生活、学习实例，都可以采用队列来解决。
同学们，再见

展开更多......

收起↑