18-19 附录：队列拓展_双指针问题&附录：栈拓展_背包问题、单调栈 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

附录：队列拓展 双指针问题 小伟在玩纸牌接龙游戏。他将一副扑克牌去除大小王之后，打乱落成一堆，然后从牌堆顶开始摸牌。摸到的牌如果和之前的所有牌的大小不重复，就接在之前牌的后面组成“长龙”。如果摸到了重复牌就将前面的重复部分移除，始终保持“长龙”内没有重复牌。小伟设计了如下python程序，模拟接龙游戏过程，并输出“长龙”的最长长度。 请在划线处填入合适的代码。 import random a = [] for i in range(52): a.append(i%13+1) #生成原始排堆 random.shuffle(a) #用随机模拟洗牌过程 print("洗牌后的排堆:",a) que = [0]*52 head = tail = 0 f = [False]*14 j = 0 while j<len(a): if f[a[j]]==False: tail+=1 f[a[j]]=True if tail-head>maxn:maxn = tail-head;st = head;ed = tail-1 j+=1 else: while : f[a[head]] = False head += 1 print("最长“长龙”长度:",maxn,"起点",st,"终点",ed) 参考答案： ①maxn = 0 ②que[tail]=a[j] ③f[a[j]] 或 f[a[j]]==True 附录：栈拓展 1.背包问题 （22.08山水联盟）小赵同学在某游戏平台中获得虚拟的食物、装备、材料等物品，他们分别有不同价值，现游戏平台有兑换机制，可用多个不同物品兑换一个等值的物品（每个物品只能取一样），下图是小赵同学已经获得的物品。 序号 物品名称 数量 单价 0 经验书 3 1 1 忘尘丹 2 2 2 神仙醉 1 5 3 止血草 5 7 4 五雷符 1 9 5 仙山灵芝 5 10 6 梅花镖 1 15 7 青龙旗 1 20 如要换取游戏游戏中的物品“开天斧”，需要35个金币，有多种置换方式，为方便计算节省时间，小赵同学编写了如下程序，运行界面和代码如下，请在划线处填入合适的代码。 def exchange(t,pricelist): n = len(pricelist) stack = [] i = 0 num = 0 while : while t>0 and i<n: if t>=pricelist[i]: stack.append(i) i+=1 if t==0: print("取序号为",stack,"的物品") num+=1 i=stack.pop() t+=pricelist[i] if num==0: print("无方案") m = int(input("目标置换物品价值：")) price = [1,2,5,7,9,10,15,20] print("依次拿取物品序号方案：") exchange(m,price) 参考答案： ①stack or i<n ②t-=pricelist[i] ③i+=1 2.单调栈问题 小李学习完必修二后，在自己家里搭建了一个植物补光系统，每天记录光照强度并记录在数据库中。系统工作一段时间后，小李想知道近两周的最高光照强度的变化。小李的处理方式如下：从数据库中导出近两天的光照强度数据，将每天的最高光照强度存入数组a；创建数组b，b[i]存储对于第i天，下一个更高光照强度出出现在几天后，最后返回数组b。小李同学编写了如下程序，请在划线处填入合适的代码。 ''' 从数据库中获取光照强度数据，并将每天的最高光照强度存入数组a，代码略 a = [897,998,669,938,587,526,510,686,717,527,978,788,613,878] ''' n = len(a