(
课件网) 队列的应用（第八课时） 册 别：选择性必修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 i
