高效作业10 第10课 队列2——队列应用-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固PPT课件（浙教版2019）

高效作业10 [第10课　队列2——队列应用] 1 2 3 4 5 6 7 8 9 10  【A级　新教材落实与巩固】 1．报数游戏。已知班上有n 名学生(用编号1，2，3，…，n 分别表示)，学生按照编号由小到大顺时针围成一个圆圈，从编号为1 的学生开始顺时针报数，报到m 的同学出列；下一名同学又从1 开始报数，报数为m 的同学继续出列；以此规律重复下去，直到剩下最后一位同学为止。 (1)当n＝12，m＝3 时，最后留下的同学的编号是______。 (2)下列代码通过构造一个循环单向链表模拟报数的过程， 逐一删除报数为m 的节点，直到剩下一个节点为止。请在横线处填入合适的代码。 n＝int(input(”n＝”)) 10 m＝int(input(”m＝”)) lst＝[] for i in range(n－1)： lst.append([i＋1，i＋1]) lst.append(①_________ ) #将尾节点的指针指向头节点，构成循环单向链表 p＝len(lst)－1 while n>1： for i in range(1，m): #从1～(m－1)依次报数 [n，0] p＝lst[p][1] out＝lst[p][1] ②______________________ n＝n－1 print(”最后留下的同学的编号是： ”，lst[p][0]) (3)下列代码通过构造一个循环队列，模拟报数的过程，将报数为m 的元素进行出队操作(报数非m 的元素重新入队)，直到剩下一个元素为止。请在横线处填入合适的代码。 n＝int(input(”n＝”)) lst[p][1]＝lst[out][1] m＝int(input(”m＝”)) q＝[0]*n head＝0 tail＝0 for i in range(1，n＋1): #构造循环队列 q[tail]＝i ③____________________ c＝0 while (head＋1)%n！＝tail： tail＝(tail＋1)%n c＝c＋1 if c＝＝m： head＝(head＋1)%n c＝0 else： ④___________________ tail＝(tail＋1)%n head＝(head＋1)%n print(”最后留下的同学的编号是： ”，q[head]) q[tail]＝q[head] 【解析】 (1)依次出队伍顺序为：3，6，9，12，4，8，1，7，2，11，5，最后剩10。 (2)①构建循环链表，将尾节点的指针指向头节点，答案为[n，0]。②达到m需要删除out节点，p是前一节点，答案为lst[p][1]＝lst[out][1]。 (3)③循环队列入队，答案为tail＝(tail＋1)%n。④如果计数c与m不相等，则重新入队，答案为q[tail]＝q[head]。 1 2 3 4 5 6 7 8 9 10 2．物流公司通常按照货物到达的先后顺序生成配送单，快递员按照配送单的先后顺序依次完成送货任务。通过分析物流公司生成配送单的过程，小明编写Python代码简单模拟了物流配送管理过程，根据动作列表act_list输入的值，运行代码，程序运行界面如下图所示。 动作列表：['入队'，'出队'，'出队'，'入队'，'入队'，'出队'，'入队'，'入队'，'出队'，'出队'，'入队'，'入队'] No.1入队 No.1出队 队列空了，等待新单 No.2入队 No.3入队 No.2出队 No.4入队 No.5入队 No.3出队 No.4出队 No.6入队 队列满了，程序结束 队首货物编号：No.5 队列中待配送货物数量：2 实现上述功能的Python程序如下，请在横线处填入合适的代码。 act_list＝ [＂入队＂，＂出队＂，＂出队＂，＂入队＂，＂入队＂，＂出队＂，＂入队＂，＂入队＂，＂出队＂，＂出队＂，＂入队＂，＂入队＂] print(＂动作列表：＂，act_list) n＝6 q＝[＂＂]*n　#创建总长度为6的空队列 head，tail＝0，0　#初始化队首指针和队尾指针 num＝1　#配送单序号 for act in act_list： if act＝＝＂入队＂： if tail＝＝n： print(＂队列满了，　程序结束＂) break q[tail]＝＂No.＂＋str(num)　#新的配送单入队 print(q[tail]，＂入队＂) ①____________ tail＋＝1 num＋＝1 else： if ②________________： print(＂队列空了，　等待新单＂) else： print(q[head]，＂出队＂)　#配送单出队 　　　 head＋＝1 print(＂队首货物编号：　＂，q[head]) print(＂队列中待配送货物数量：　＂，③_____________) head＝＝tail tail－head 【解析】 填空①处完成入队操作，从队尾进行，队尾指针加1；填空②处队列空的状态，表示head＝＝tail；填空③处求队列的元素个数，即tail－head。 1 2 3 4 5 6 7 8 9 10 3．2023·台州中学检测为了让全班同学参加文艺汇演，小王设计了一个节目：先让k 名同学同时出现在舞台上开始表演，当某一名同学率先完成了其表演部分，马上离开舞台，第k＋1 名同学会立即出现在舞台上并开始表演；当第2 名同学离开舞台时，第k＋2 名同学也随即出现在舞台……以此类推，直到所有同学上台，当最后一名同学完成他舞台上的表演，节目结束。 由于表演时长有限，小王希望在表演限定时长tmax 内，确定最少有k 名同学在舞台上同时表演。他根据上述要求编写Python 程序，读取n 名同学的表演时长(秒)，通过不断增加同时表演的人数k，找到第一个表演时长小于等于tmax 的k 值并输出。 (1)若有6 名同学参加表演，他们的表演顺序及时长(秒)分别为“20，40，15，25，10，30”，同时在舞台表演的人数为3，则全部同学完成表演所需的时长为______秒。 (2)在计算表演时长的过程中，为了快速获取舞台上最先完成表演的时间，小王采用Python中现成的优先队列类PriorityQueue，该类常用的方法如下表所示。 类及方法 说明 样例 Priority Queue 声明一个优先队列，默认最小值优先 que＝PriorityQueue () put() 向优先队列中加入元素 que.put(50) get() 返回队列中的最值元素(默认为最小值)，并移除该元素 que.get() 60 实现上述功能的Python 程序如下，请在横线处填入合适的代码。 from queue import PriorityQueue def compute(x，n)： q＝PriorityQueue() for i in range(x)：　 #将前x 名表演同学的时长加入队列q q．put(d[i]) c＝0　#用于存储上一名同学离开舞台的结束时间 i＝x ①________ t＝0 while i<n： y＝q.get() t＋＝y－c　#累加该同学比上一名同学多用的表演时间 c＝y q．put(②___________ ) i＋＝1 #将舞台上剩余同学多用的时间累加到变量t 中，代码略。 return t d[i]＋c #读取全班n 名同学的表演时长，按表演顺序依次存在数组d[0]到d[n－1]中，代码略 tmax＝int(input(”请输入限定表演时长：　(秒)　”)) k＝1 while k<＝n： if ③__________________________： break else： k＋＝1 compute(k，n)<＝tmax if k>n： print(”不存在在限定时间内表演的方案！”) else： print(”需要同时表演的同学最少为：”，k，”名”) 【解析】 (1)6 名同学的演出顺序和每个位置结束表演的时间如下表。最后一名同学结束的时间是60，故答案为60。 (2)①一开始x 名学生是一起上台的，可以看到循环中结束时间t 没有初始值，因此t 的初始值为0，填t＝0。 ②优先队列保证了当前出队的元素是最小的，即y 代表了当前场上的同学最早结束表演的时间，此时第i 名同学接着该同学上台表演，对应 演出顺序 表演位1 表演位2 表演位 3 前3名同学上台表演 20 40 15 位置3表演完后4号上台 20 40 15＋25＝40 位置1表演完后5号上台 20＋10＝30 40 40 位置1表演完后6号上台 30＋30＝60 40 40 表演位结束时间为d[i]＋y，重新入队，如上表所示。故填：d[i]＋y 或d[i]＋c。 ③函数compute(k，n)的返回值就是总数n 个人，舞台上最多有k 名同学同时表演的结束时间，若其小于等于tmax 说明此时的k 已经满足要求，可以退出循环。故填：compute(k，n)<＝tmax。 1 2 3 4 5 6 7 8 9 10 4． 校学生会要从两个候选人A 和B 中选举一个会长，每个候选人都有自己的支持方。现在以一个基于轮为过程的投票来进行选举，在每一轮选举中，当前成员可以禁止另一位成员的选举权，即让另一位成员在这一轮和随后的几轮中都丧失选举权。在选举过程中，一旦有选举权的成员都来自一个阵营，则该阵营胜利。 字母A 和B 分别代表两位候选人，输入一个字符串代表每个成员的阵营，例如输入“ABB”，则输出结果为B，即候选人B 为会长。 说明：第一轮中，第一个成员(A)可以让第二个成员(B)失去选举权，因为第二个成员(B)的选举权被禁止，所以他会被跳过，第三个成员(B) 可以让第一个成员(A)失去选举权，因此在第二轮只剩下第三个成员(B)拥有选举权，则输出结果为B，即候选人B 为会长。 (1)若输入“ABABB”，则会长为______。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 s＝input(”请输入投票字符串：　”) queA＝[””]*100；queB＝[””]*100 headA＝headB＝0 tailA＝tailB＝0 n＝len(s) A for i in range(n)： if①_____________： queA[tailA]＝i tailA＋＝1 else： queB[tailB]＝i tailB＋＝1 while ②____________________________________： if queA[headA]<queB[headB]： s[i]＝＝”A” headA！＝tailA and headB！＝tailB queA[tailA]＝queA[headA]＋n tailA＋＝1 else： queB[tailB]＝queB[headB]＋n tailB＋＝1 headA＋＝1；headB＋＝1 if ③_________________： print(”B”) else： print(”A”) headA＝＝tailA 【解析】 题干中“基于轮”的选举方式，很容易让人联想到对数据的反复遍历。但是引入队列结构后，便将反复的遍历、下标跳跃，变成了单一的先行方向递增。 (1)“ABABB”序列看起来B 的长度更长，但是在实际选举中，元素A 在元素B 之前被枚举到，可以优先禁言下一个B 元素，而B 元素后面没有A 元素(序列第2 项B 会在一开始被A 禁言)，所以无法在选举时禁言A 元素。故答案选A。 (2)程序填空部分引入了两个队列queA 和queB，初始化时分别用于存储A 元素和B 元素在序列中的位置。即queA[headA]表示“该轮中，当前最 靠前的A 元素在序列中的位置”，同理que[headB]表示“该轮中，当前最靠前的B 元素在序列中的位置”。所以在第①空初始化队列时，若序列第i 项的s[i]＝＝'A'则初始化queA，否则初始化queB。第②空是对具体选举过程的模拟，对于两个队列A 和B 中最靠前的两个人，比较他们在序列中的位置，更靠前的元素可以优先禁言另一个元素，即“更靠前的元素进入下一轮”，如“queA[tailA]＝queA[headA]”，而另一个元素不进入下一轮，在headB＋＝1 之后出队相当于在之后的选举中被禁言。题干要求未禁言的成员来自同一方即可结束。所以本题中选举结束的条件为两个队列中某一个队列位空，即第②空的逻辑表达式为“两个队列均不 为空”，答案为：headA！＝tailA and headB！＝tailB。第③空是对获胜方的判断，从队列的角度理解，如果队列A 空则B 获胜，反之A 获胜。即答案为：headA＝＝tailA。 1 2 3 4 5 6 7 8 9 10 5． 某银行网点有5 个窗口，银行最少要保持3 个窗口营业，另外2 个窗口初始为备用状态。客户按批次进入大厅，每个客户的业务办理时间为1 个单位，银行每过1 个时间单位就允许下一批客户进入。对于进入银行的客户，如果某窗口正空闲，则可上前办理业务，反之，若所有窗口均有客户，他便会排在最短的队伍后面。当平均每个营业窗口前的队伍人数大于等于7 人时(队伍包括正在办理业务的客户在内)，将备用窗口中一个或两个改为营业窗口，当所有窗口平均客户少于7人时，将立即停用一个营业窗口转为备用，窗口平均人数若继续减少至以上情况，可再停止一个营业窗口，但最多只能有两个窗口为备用状态。现模拟该银行 排队程序，输出10 个人各自的等待时间单位，运行界面如图所示： 输出格式描述： (客户编号：等待的时间) (1)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 mins＝3#常用窗口3 个 maxs＝5#最多可开设5 个窗口 lims＝7#正常服务时每个窗口平均等待的最多人数 请输入共有多少批客户： 2 输入每一批的人数4，6 (1：0) (2：0) (3：0) (4：1) (5：0) (6：0) (7：1) (8：1) (9：1) (10：2) tm＝int(input('请输入共有多少批客户：　')) ps＝list(map(int，input('输入每一批的人数').split('，'))) sw＝mins if len(ps)！＝tm： print('输入有误！') pid，cnt＝0，0 head，tail＝0，0 qe＝[[0，0]]*1000 #创建等待队列 def updatetime(s)： for j in range(len(s))： s[j][1]＋＝1 for i in range(tm)： for j in range(sw): #将轮到的人进行出队 if ①_______________： print(f'({qe[head][0]}：{qe[head][1]})'，end＝' ') head＋＝1 cnt－＝1 head！＝tail #人数减少后，检查人数和窗口数是否符合要求并按照要求减少窗口， 代码略 if head！＝tail： ②_____________________________ #更新等待队列里每个人的等 待时间 for j in range(ps[i])： pid＋＝1 qe[tail]＝[pid，0] tail＋＝1 updatetime(qe[head：tail]) cnt＋＝1 while ③ ___________________________________________________________： 　　　sw＋＝1 while cnt>0： #最后一批人进入银行后，程序只需要处理等待队列剩余人员到出队 和窗口的减少，直至人数为0，代码略 (2)共有3 批客户，分别为22 人，23 人，21 人，则输出的结果中，第4 个人等待_____个时间单位。 cnt/sw> lims and sw<maxs 或 cnt/sw>7 and sw<5或其他等价答案 0 【解析】 (1)通过①下面代码head＋1推测出队操作，出队操作的条件是非空队列，判断非空队列的代码为 head！＝tail。根据注释说明，队伍非空时进行所有等候人员的等候时间的更新。本程序的执行过程为先出队，刚开始等候队列没有人，所以出队和更新时间都没有执行，第三部分进队发生，然后进入下一次外循环，此时重复上面步骤，先出队(第一批来的人中有3 人确定不需要排队，所以出队时等候时间为0，再执行等候时间更新时，针对的就是没有及时出队的人。)。更新时间采用自定义函数updatetime()，结合updatetime()函数内容，应只更新有效队列的候时，所以代入的参数q应为qe[head：tail]。通过sw＋1可得窗口增加，③ 则是跟窗口增加的条件有关的，即每个窗口平均等待人员大于等于7人，且窗口数还没有达到最大个数5，才可以继续增加窗口数。 (2)因为输入窗口数为3，而第一个时间周期就在22人时，单个窗口平均等待人数已经超过7个，则随即增加第4个窗口，第4个人刚好在本周期，所以在这个周期里，1，2，3，4第4个人刚好不需要等候。 1 2 3 4 5 6 7 8 9 10 6．2023·丽水中学检测某信号传播系统有如下特点：源信号具有一定的传播强度，可向与其直接连接的基站进行信息传播；同时接收到信号的基站也可向其连接点进行传播。信号的传播强度用指数q 表示，在向外多轮传播的过程中会进行衰减，每传播一轮会衰减1 个量级，q 值为0 时将不再有传播性。若有基站同时接收到多个上一轮基站的信息传播，则选择传播强度指数值大的信号。 编写Python 程序，随机产生基站间的关系矩阵并输出；输入源信号所在基站号与初始传播强度值，最后输出信号传播完成后各基站的信号强度。注：没有接收到信号的基站信号强度赋值为－1。 (1)信号传播系统中共有8 个基站，依次编号为A～H，它们之间的连接关系如图1所示。两者之间没有连接关系的用0 表示，相互之间有连接关系的用1 表示；自身与自身之间也用1表示。若编号为B 的基站具有源信号，其传播强度为2，则下列基站会接受到信号的是__________(多选，填字母)。 A． 基站A　　　　 B． 基站D C． 基站E D．基站G ACD 各基站间连接情况示意图 图1   A B C D E F G H A 1 0 1 0 0 0 1 0 B 0 1 1 0 1 0 0 1 C 1 1 1 0 0 1 1 0 D 0 0 0 1 0 0 1 0 E 0 1 0 0 1 0 0 0 F 0 0 1 0 0 1 0 0 G 1 0 1 1 0 0 1 0 H 0 1 0 0 0 0 0 1 (2)实现上述功能的Python 程序如下，程序运行部分界面如图2所示。请在横线处填入合适的代码。 #随机产生基站间的关系矩阵并输出，代码略 图2 #各基站间关系存储在列表link 中 def spread(n，web，num，q)： 请输入源信号基站编号，用字母A～H表示：　C 请输入初始传播强度指数：　2 [1，1，2，0，0，1，1，0] grade＝[－1]*n #设置各基站的传播强度初始值为－1 grade[num]＝q #设置各基站的传播强度指数 a＝[－1]*n head，tail＝0，0 a[tail]＝num #源信号基站加入队列 tail＋＝1 while ①_________________________________________： i＝a[head] head＝②____________ head！＝tail 或head<tail 或其他等价答案 head＋1 if grade[i]<＝0： continue for j in range(n)： if web[i][j]＝＝1: #基站间若有连接，则i 可传播至j if j not in a： grade[j]＝③______________ a[tail]＝④_____ tail＋＝1 return grade grade[i]－1 j n＝8 link＝[[1，2]，[2，0]，[0，6]，[1，7]，[2，6]，[3，6]，[4，1]，[5，2]] # link 中[1，2]表示基站B 与基站C 连接，其他类同 bs＝{'A'：0，'B'：1，'C'：2，'D'：3，'E'：4，'F'：5，'G'：6，'H'：7} web＝[[0]*n for i in range(n)] for i，j in link： web[i][j]＝web[j][i]＝1 #表示编号为i 和j 的两个基站连接 num＝input(”请输入源信号基站编号，用字母A～H 表示：　”) num＝bs[num] q＝int(input(”请输入初始传播强度指数：　”)) grade＝spread(n，web，num，q) print(grade) 【解析】 本题采用广搜算法求最短路径(最大传播指数)。先把源信号加入队列，然后根据队列的基本操作，按照基站连接程度依次将接收信号基站入队。 (1)基站第一轮接收信号时，其传播强度指数最高，故其最大传播强度值即为入队时设置的grade[j]的值。列表link 存储各基站间关系，二维数组web 表示邻接矩阵，若web[i][j]＝1，则说明顶点i 和j 之间连接。自定义 函数spread(n，web，num，q)用来计算各基站信号的传播强度值，其中n 表示基站个数(n＝8)，web 是表示连接关系的邻接矩阵，num 和q 分别表示可传播信号的基站编号和传播强度指数。 (2)程序先初始化各基站的传播强度指数为－1，再设置源信号基站num 的传播强度值为q，并将其加入队列a。之后只要队列不为空，就先将队首元素(记为基站i)出列，若基站i 具有传播强度，则将与其连接的基站j 入列。判断队列是否为空的代码为head！＝tail或head<tail，此即第①空答案。队首元素出列后，队首指针head 要向后移一位，即head＝head＋1，故第②空答案为head＋1。 语句for j in range(n)遍历所有的基站编号，如果基站j 与可传播基站i 连接触，且j 不在队列中，说明该基站j 是首次接收到信号，此时设置其传播强度指数grade[j]＝grade[i]－1，即为最大传播强度值，故第③空答案为grade[i]－1。将基站j 加入队列的代码为a[tail]＝j; tail＋＝1，故第④空答案为j。 1 2 3 4 5 6 7 8 9 10 【B级　素养形成与评价】 7．现有一个m×n的迷宫矩阵maze(如图1)，矩阵中有空格子(用1表示，可通行)和墙(用0表示，不可通行)，在迷宫中通行的每一步移动操作，可以往上、下、左、右任一方向移动一个格子(不能进入墙所在的格子)。 目标是找到离entry(入口)最近的出口，并规划入口到出口的行走路径(出口的含义是maze 边界上的空格子，entry格子不算出口)。如果不存在这样的路径，请返回－1；如果有，则展示entry到出口的行走路径。程序正常执行后，运行结果如图2所示。 图1　　　　　　　　　　图2 寻找最近出口位置的思路与算法： 预设：0为墙　1为空格子　2为已探索 在广度优先搜索的过程中，在队列中保存[cx，cy，d]三元素列表，其中 (cx，cy)为当前的行列坐标，d为当前坐标相对入口的距离(即需要移动的步数)。 当遍历至(cx，cy)时，枚举它上下左右的相邻坐标(nx，ny)。此时可能有三种情况： ①(nx，ny)不属于迷宫坐标或为墙，此时无需进行任何操作； ②(nx，ny)为迷宫的出口(在迷宫边界且不为墙)，此时应返回nx，ny，d＋1，即该出口的坐标以及相对入口的距离作为答案； ③(nx，ny)为空格子且不为出口，此时应将新坐标设置为已探索，并将其对应的三元素列表[nx，ny，d＋1]加入队列。 最终，如果不存在到达出口的路径，返回－1作为答案。 (1)若迷宫数据为maze＝[[0，0，0，0，0]，[1，1，1，1，0]，[0，1，0，1，1]，[0，1，1，1，0]，[0，0，0，0，0]]，则最少移动步数为_____。 (2)请在横线处填入合适的代码。 import queue BLOCKED，OPENED，PASSED＝0，1，2 def valid(maze，pos): if (0<＝pos[0]<m and 0<＝pos[1]<n and ① __________________________________________________________)： 5 maze[pos[0]][pos[1]]＝＝OPENED 或 maze[pos[0]][pos[1]]＝＝1 　　　return True else: return False def findExit(maze, entry): dx＝[－1，1，0，0] dy＝[0，0，－1，1] q＝queue.Queue(maxsize＝100) #建立队列 q．put([entry[0], entry[1], 0]) #将入口加入队列并标记 maze[entry[0]][entry[1]]＝PASSED while q．qsize()>0: cx，cy，d＝q.get() #弹出队列中队首数据 for k in range(4): ②____________________________________________________ ___________________________ if valid(maze，(nx，ny)): if nx＝＝0 or nx＝＝m－1 or ny＝＝0 or ny＝＝n－1： 　　　 return nx，ny，d＋1 nx，ny＝cx＋dx[k]，cy＋dy[k]或 nx＝cx＋dx[k]；ny＝ cy＋dy[k] (必须用分号隔开) ③___________________________________________ q．put([nx，ny，d＋1]) return －1，－1，－1 maze＝[[0，0，0，0，0，0，0，0，1，0], [1，1，1，0，1，1，1，0，1，0], [0，1，1，0，1，1，1，0，1，1], [0，1，1，1，1，0，0，1，1，0], [0，1，0，0，0，1，1，1，1，0], [0，1，1，1，0，1，1，1，1，0], maze[nx][ny]＝PASSED 或 maze[nx][ny]＝2 [0，1，0，1，1，1，0，1，1，0], [0，1，0，0，0，1，0，0，0，0], [0，0，1，1，1，1，1，1，1，1], [0，0，0，1，0，0，0，0，0，0]] m，n＝len(maze), len(maze[0]) #迷宫的行数，列数 entry＝[1，0] #预设的迷宫入口 exit_pos_x，exit_pos_y，steps＝findExit(maze，entry) if steps＝＝－1: print(f”从入口{entry}进入迷宫后，　无法找到出口”) else: exit_pos＝[exit_pos_x，exit_pos_y] print('入口：　'，entry，'最近出口位置：　'，exit_pos，'最少移动 步数：　'，steps) #绘制路径代码略 【解析】 (1)若迷宫数据为maze＝[[0，0，0，0，0]，[1，1，1，1，0]，[0，1，0，1，1]，[0，1，1，1，0]，[0，0，0，0，0]]，则最少移动步数为5，如图所示。 (2)①valid()函数的功能是判断迷宫中指定的位置是否可走，一个位置可走的判断条件是其在迷宫中且该位置是空格子(不是墙)。参数pos 是一个包含行和列的元组，pos[0]表示行，pos[1]表示列。故该空的答案为：maze[pos[0]][pos[1]]＝＝OPENED 或maze[pos[0]][pos[1]]＝＝1。②findExit() 函数是广搜算法的核心函数，从入口entry 开始搜索，每次取出队首元素开始从4 个方向扩展，扩展时需要在原来位置上加上行与列 的增量值，行与列的增量分别存放在dx 和dy 列表中。从队首取出来的cx，cy，d，分别表示当前的位置[cx，cy]和走到该位置的最少移动步数d，从4 个方向进行扩展时，需要在当前位置[cx，cy]的基础上增加增量dx[k]和dy[k]，从而走到相应方向上的新位置。故该空的答案是：nx，ny＝cx＋dx[k], cy＋dy[k]。③空是用于标记刚扩展出的新位置[nx，ny]已走过，广搜算法中扩展过的位置一定要打上已扩展标记，否则互相扩展队列将永远不可能为空，从而导致程序死循环。故该空的答案为：maze[nx][ny]＝PASSED或 maze[nx][ny]＝2。 1 2 3 4 5 6 7 8 9 10 8．2023·柯桥中学检测魔术师预先将一副牌中的13张黑桃(A为1，J为11，Q为12，K 为13)排好后叠在一起，牌面朝下。他将最上面的那张牌翻过来，正好是黑桃A。将黑桃A放在桌子上，然后按顺序从上到下数手上的余牌：第二次数第1、2张牌，将数到的第一张牌放在这叠牌的下面，将第二张牌翻过来，正好是黑桃2，将它放在桌子上；第三次数第1、2、3张牌，将前面两张依次放在这叠牌的下面，再翻第三张牌，正好是黑桃3，放在桌子上。这样依次进行，将13张牌全翻出来，最后桌子上牌的顺序是A，2，3，…，K。魔术师手中的牌原始顺序是怎样的？ 小王和小李对问题进行了分析与算法设计，写了Python函数way()正确解答了问题，请回答下列问题。 (1)原来牌的顺序中，黑桃3 放在自上向下第_____ (填阿拉伯数字)个位置。 (2)请在横线处填入合适的代码。 def way()： a＝[i for i in range(1，14)] b＝[0]*13 #0代表牌面未定 head＝0；tail＝0 for i in range(1，14)： 6 cnt＝1 while cnt<i： a[tail]＝①__________ head＝(head＋1)%13 tail＝(tail＋1)%13 ②____________________________ ③______________________________________ head＝(head＋1)%13 return b print(way()) a[head] cnt＋＝1 或 cnt＝cnt＋1 b[a[head]－1]＝cnt 或 b[a[head]－1]＝i 【解析】 本题中解题要点：数组a用于存储13个顺序位置；数组b用于存储输出结果；函数中的for循环变量i为牌面值：因数组b初始为0，随着for循环进行，应该逐个把相应的牌面值i填到数组b相应的位置，实现时会有类似于b[a[…]…]＝i这种框架的语句。 (1)由表可知答案。 (2)①此循环目的是，队列前 i－1个位置，不需要出列，放到队尾(head和tail同步进行调整)，供以后继续数，故此处填a[tail]＝a[head]。 ②此处语句实现计数，控制while循环执行 i－1 次；填cnt＋＝1。 牌面值 黑桃A   黑桃2     黑桃3                 1 1 2 1 2 3               牌的 位置 1 2 3 4 5 6 7 8 9 10 11 12 13 ③在上面的while循环把队列前i－1个值放到队尾之后，第i个值(当前队首a[head]位置)就是放置牌面为i的这张牌的位置，故此处填写b[a[head]－1]＝i或b[a[head]－1]＝cnt。此处比较容易写成b[a[head]]＝i，是因为没有考虑到数组a的位置值和数组b的下标对应位置有1的差值。下一行语句head＝(head＋1)%13，则实现了队首元素出队的操作。 1 2 3 4 5 6 7 8 9 10 9． 小林在玩一种纸牌游戏——纸牌钓鱼。他对牌做了如下处理： (1)取两副纸牌，去除大小王，剩余共104张，其中▲表示黑桃，○表示红心，★表示梅花，◇表示方块，将牌按顺序叠好，成为原始牌叠； (2)对原始牌叠进行洗牌：进行104次洗牌，每次将面上的第一张牌取出，随机插在牌叠中，形成洗牌牌叠； (3)摸牌：从洗牌牌叠中从上向下连续摸牌，使得摸到的牌里没有重复的牌(同花色、同点数视为重复的牌)，这样连接的牌数量最多时，即为最长无重复牌叠。 现设计Python程序来模拟这个游戏：先显示原始牌叠，洗牌后再显示洗牌牌叠，摸牌后显示最长无重复牌叠的张数、起点及终点，并显示最长无重复牌叠的信息。运行结果如图所示。 (1)实现上述功能的Python程序如下，请在横线处填入合适的代码。 from random import randint def dayin(head，tail): #打印牌叠 pt＝head；k＝0 while ①_____________： print(str(pai[pt][0])＋'－'＋str(pai[pt][1])，end＝'||') pt＝pai[pt][1]；k＝k＋1 if k＝＝13: print()；k＝0 print(' '，'*'*105) pt！＝tail dic＝{0：'▲'，1：'○'，2：'★'，3：'◇'，4：'A'，5：'2'，6：'3'，7：'4'，8：'5'，9：'6'，10：'7'，11：'8'，12：'9'，13：'10'，14：'J'，15：'Q'，16：'K'} pai＝[]；head＝－1；k＝0 while k<104： pai.append([②__________________________，head]) head＝len(pai)－1；k＝k＋1 print('原始的牌叠') dayin(head，－1) #打印原始牌叠 dic[k%4]＋dic[k%13＋4] k＝0 while k<＝103： x＝randint(0，103) i＝0；pt＝head while i<x： pt＝pai[pt][1] i＋＝1 if pt！＝head： nhead＝pai[head][1] ③__________________________ pai[pt][1]＝head head＝nhead k＋＝1 print('洗牌后的牌叠') dayin(head，－1) #打印洗牌牌叠 f＝{} for i in range(4)： for j in range(4，17)： pai[head][1]＝pai[pt][1] f[dic[i]＋dic[j]]＝False L＝ans＝0；i＝j＝head while j！＝－1： m＝pai[j][0] if not f[m]： f[m]＝True；L＝L＋1 if L>ans: ans＝L；pt＝j；qt＝i j＝pai[j][1] else： while ④______________： f[pai[i][0]]＝False L＝L－1 i＝pai[i][1] print('最长无重复牌叠%d张'%ans，'起点'，qt，'终点'，pt) (2)程序中加框处代码有误，请改正：_______________。 f[pai[j][0]] qt，pai[pt][1] 【解析】 (1)①本处自定义函数实现打印牌叠，从后面的自定义函数使用参数可知(如：dayin(head，－1) #打印洗牌牌叠) head 为打印链表的起始位置，tail为尾节点的指向值，故pt＝tail时退出循环，故答案为：pt！＝tail。②处实现创建链表，head表示该节点指向下一节点的下标，当前节点由[花色＋牌符，指向]组成，四种花色依次出现，故dic[k%4]，13种牌符依次出现，故第k张牌符为k%13，因字典对应的牌符值从“4” 开始，故dic[k%13＋4]。综上所述，答案为：dic[k%4]＋dic[k%13＋4]。③处实现洗牌。将head位置的牌放到随机数x位置，若x＝0，则牌叠不动。现将head位置的牌链接到pt与pai[pt][1]之间，故第一步：记录head 位置的指向(即新的head位置)；第二步：将原head位置节点指向pt节点的下一节点；第三步：pt节点的下一节点指向head节点。故答案为：pai[head][1]＝pai[pt][1]。④处先将不同花色的牌符标记为False。本处用双指针实现遍历，j指针去找最长的无重复牌叠；i指针将刚才已遍历过的pai[j][0]标记值改为False，并将i节点排除出无重复牌叠，当前无重复牌叠pai[i][1]起始。 故答案为：f[pai[j][0]]＝＝true。 (2)本处调用自定义函数实现打印牌叠，从自定义函数使用参数看(如：dayin(head，－1) #打印洗牌牌叠) head为打印链表起始位置，tail为尾节点的指向值， 故本处答案应该是： qt，pai[pt][1]。 1 2 3 4 5 6 7 8 9 10 10．2023·义乌中学检测某餐厅餐桌系统设置如下表： 有客人来就餐时，其叫号系统会自动生成一个号码，并根据人数安排餐桌型号；当对应餐桌型号有空桌时，按餐桌编号(由小到大)即时分配餐桌安排客人就餐；当对应餐桌型号没有空桌时，客人按先后顺序排队。系统程序部分运行界面如下： 餐桌型号 2人小桌 4人方桌 6人大方桌 12人大圆桌 餐桌数量 8 15 10 4 平均就餐 时间/分钟 25 45 60 80 (1)定义如下gettype()函数，功能为输入客人人数，返回对应桌型，请在横线处填入合适的代码。 def gettype(num)： type＝－1 for i in range(len(size))： 11号客人，给您安排的是4人桌，前面还有0人在等位。 11号客人请用餐－－>4人桌2号 12 号客人，给您安排的是2人桌，前面还有1人在等位。 13号客人，给您安排的是2人桌，前面还有2人在等位。 if num<＝size[i]： type＝i _________ return type (2)定义如下checktable()函数，功能为输入桌型，返回对应桌型空桌的编号，返回值类型为列表，请在横线处填入合适的代码。 def checktable(n)： ans＝[] for i in range(nums[n])： break if ____________________： 　 ans.append(i) return ans (3)解决上述问题的主程序如下，请在横线处填入合适的代码。 size＝[2，4，6，12] #每种桌型最大就餐人数 nums＝[8，15，10，4] #每种桌型的餐桌数量 times＝[25，45，60，80] #每种桌型平均就餐时间 flags＝[[True]*nums[i] for i in range(4)] #标记每张桌子的初始状态 s_time＝10*60*60 #开始营业时间——10 点整，转化为秒 flags[n][i]＝＝True e_time＝14*60*60 #结束营业时间——14 点整，转化为秒 maxn＝50 #假设队列已经足够深 qc＝[[0]*maxn for i in range(4)] #循环队列 now_time＝s_time id＝0 head，tail＝[0]*4，[0]*4 while now_time<e_time： number＝getinfo() #调用函数getinfo()，获取客人人数 if number>0： id＋＝1 type＝gettype(number) #根据就餐人数确定餐桌类型 if type！＝－1： qc[type][tail[type]]＝id tail[type]＝(tail[type]＋1)%maxn qc_len＝①_____________________________________ print(id，”号客人，　给您安排的是”，size[type]，”人桌，　 前面还有”，qc_len－1，”人在等位。”) else： (tail[type]－head[type]＋maxn)%maxn print(id，”号客人，　非常抱歉，　没有适合您的桌型！　”) for i in range(4)： tables＝checktable(i) i f ②____________________________________________________ _________： 　　　 flags[i][tables[0]]＝False #入座第一个空桌 print(qc[i][head[i]]，”号客人请用餐－－>”，size[i]，”人 桌”，tables[0]，”号”) head[i]＝(head[i]＋1)%maxn now_time＋＝1 #更新每张餐桌的就餐情况，代码略 len(tables)>0 and head[i]！＝tail[i]或tables and head[i]！ ＝tail[i] 【解析】 (1)计算并返回num 人对应的桌型，参考题干中4 类桌型与主程序中的size 列表初始化可知，返回值type 满足size[type－1] < num <＝size[type]，即按顺序遍历size 列表的过程中，第一次满足num<＝size[i]时，type＝i 为返回值，此时直接退出循环即可。答案break。 (2)计算对应桌型的空桌编号列表，这与第(3)问中的②有关联。由于返回的是列表，所以对每一个空桌都需要记录(ans.append(i))，而是否为空桌由flag 列表标记。观察初始值，flag 初始化时均为True(空桌)，所以此处检查类型编号为n 的nums[n]张桌子中的空桌的状态是正解。所以答案为flag[n][i]＝＝True。 (3)考查队列操作，用二维列表qc 模拟4 个循环队列，head 和tail 列表标记4 个队列的队首和队尾。当处于营业时间时(while now_time<e_time)，若有新客入店，则先根据客人人数计算餐桌类型type，并将客人id 插入到qc[type]的末尾。从输出等待时间的代码中可以看到，变量qc_len是id 被插入后的队列长度，即此时qc[type]中有效元素的个数。根据循环队列长度公式：(队尾－队首)%maxn，因此①答案为(tail[type]－head[type])%maxn。②处的循环时对此刻队列的更新，若桌型i 有空桌则安排就座。第(2)问中的checktable()函数返回空桌列表，即列表长度不为0 表示有空桌，此外，桌型i 的队列中有客人等待时才需要安排入座，所以②处的答案为len(tables)>0 and head[i]！＝teal[i]。 感谢聆听，再见！ dayin() $$