资源简介

专题13　简单算法程序实现
学习目标　1. 基于生活中的问题设计情境，掌握分析问题、抽象建模、设计算法、编写程序的过程；
2.掌握利用算法解决问题的思维能力构建.
抽象和建模是用程序实现算法前的重要步骤，抽象找出影响问题的主要因素，明确已知什么和求什么。建模是描述主要因素之间的关系，一是明确方法，往往采用遍历列表的方法；二是明确步骤，往往是求符合条件的和、个数、最值和平均值。枚举算法简称枚举法，也称为列举法、穷举法，是暴力策略的具体体现，又称为蛮力法，在遍历过程中求值与条件进行比对的过程。枚举法的基本思想是：逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。
(2023年6月浙江省选考)某仓库有一排连续相邻的货位，编号依次为0～n－1，用于放置A、B两种类型的箱子，A型箱子占2个相邻货位，B型箱子占1个货位。编写程序，根据已完成的放置或搬离操作，输出空货位数及还可以放置A型箱子的最多数量(不移动已放置的箱子)。请回答下列问题：
箱子类型 操作类型 货位编号
B 放置 5
A 放置 2，3
B 放置 0
A 放置 7，8
A 搬离 2，3
(1)若n为10，开始时货位全空，经过如图所示的放置或搬离操作后，不移动已放置箱子的情况下，还可放置A型箱子的最多数量为________个。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
#读取货位总数存入n，代码略。
cnt1＝n
lst＝[0]*n　#货位状态，0表示对应的货位为空
while True：
　　#读取本次已描述数据：箱子类型、操作类型、货位编号起始值存入t，d和s，代码略
　　if t＝＝″A″：
　 w＝2
　　①________：
　 w＝1
　　else：　#不是″A″或″B″时退出循环
　 break
　　if d＝＝″P″：　#d为P时表示放置，否则表示搬离
　 ②________
　 else：
　 cnt1＋＝w
　 lst[s]＝1－lst[s]
　 if t＝＝″A″：
　 lst[s＋1]＝1－lst[s＋1]
　 i，cnt2＝0，0
　 while i< n－1：
　 if lst[i]＝＝0 and lst[i＋1]＝＝ 0：
　　　　 ③________
　　　　　cnt2＋＝ 1
　 i＋＝1
　　print(″当前空货位数″，cnt1，″，还可放置A型箱子的最多数量：″，cnt2)
重难点1　单元素遍历
遍历是按照一定的规则和次序访问数据元素中的所有节点，使得每个节点都被访问一次且仅被访问一次。相同类型的数据往往保存在数组中，数组的特点是按照索引位置依次存放数据，若只有一个数组，可以通过按值访问的方法，对所有数据进行求和、计数、求平均值和求最大值或最小值等操作。若多个数组，他们拥有相同的索引，可以通过索引位置依次访问数据。
例题 根据某场馆一天中每位参观者的进馆和出馆时间，可统计该场馆当天人流量的分布情况。每个人进、出馆的时间用一个长度为11的字符串表示，例如“08：05－08：45”表示进馆时间为8点5分，出馆时间为8点45分。现要求统计当天馆内人数超过指定人数的总时长。
(1)8点01分到8点08分的进出馆人数如表所示：
分钟 01 02 03 04 05 06 07 08
进馆 人数 5 0 4 2 1 3 1 2
出馆 人数 0 1 1 1 6 3 2 2
馆内大于4人的时长为________分钟。
(2)每个参观者进入场馆和出馆时间保存在“参观记录.txt”文件中，编写Python程序，请将程序补充完整。
a＝[]
f＝open(″参观记录.txt″，encoding＝″utf－8″)
for i in f：
　 t＝i.find(″－″)
　 a.append(i[：t]＋″in″)
　 a.append(①________＋″out″)
#对列表a按时间进行升序排列，代码略。
sp ＝int(input(″请输入指定人数″))
t ＝ －1 ; cnt ＝ 0 ; sum ＝ 0
for i in a：
　 mts ＝int(i[：2])*60＋int(i[3：5])
　 if i[5：]＝＝″in″：
　 cnt＋＝1
　 else：
　 ②________
　 if cnt>sp：
　 if t＝＝－1：
　　　 t＝mts
　 elif t>－1：
　 ③________
　 t＝－1
print(″超过指定人数的总时长：″ ＋ str(sum) ＋″分钟″)
变式 每个人进、出馆的时间用一个长度为11的字符串表示，例如“08：05－08：45”表示进馆时间为8点05分，出馆时间为8点45分。现要求统计当天馆内人数超过指定人数的总时长，当天在馆人数最多时刻及在馆人数。
(1)8点01分到8点08分的进出馆人数如表所示：
分钟 01 02 03 04 05 06 07 08
进馆人数 5 0 4 2 1 3 1 2
出馆人数 0 1 1 1 6 3 2 2
在馆人数最多时刻为________。
(2)每个参观者进入场馆和出馆时间保存在“参观记录.txt”文件中，编写Python程序，请将程序补充完整。
rs＝[0]*540　#存储早上8点至下午5点每分钟的在馆人数
f＝open(″参观记录.txt″，encoding＝″utf－8″)
n＝0
for sj in f ：
　 m1＝int(sj[：2])*60＋int(sj[3：5])－480　#将入馆时间转换为上午8点以后的分钟数
　 m2＝int(sj[6：8])*60＋int(sj[9：11])－480
　 rs[m1]＋＝1
　 ①________
sp ＝int(input(″请输入指定人数：″))
totrs＝imax＝sumrs＝0
itime＝″″
for i in range(540)：
　 ②________
　 if totrs>sp：
　　　③________
　 if totrs>imax：
　　　imax＝totrs
　　　itime＝str(i∥60＋8)＋″：″＋str(i%60)
print(″超过指定人数的总时长：″ ＋ str(sumrs) ＋″分钟″)
print(″在馆人数最多时刻为：″ ＋ itime ＋″，共″ ＋ str(imax) ＋″人″)
重难点2　连续多个元素遍历
在一个序列中遍历元素可以分为两种情况，一是对单个元素进行遍历，如对字符串进行加密、压缩算法。二是要找出序列中一个连续的子序列，如找一个依次相连的子串，找一个连续递增或递减的子序列。在第二种情况中，将涉及该元素与他前面或后面元素的关系，因此需与他们依次进行比较，比较总次数比元素的个数少1个。
例题 现有一个文档“压缩前.txt”中保存了大量的小写字母和数字，小明发现文档中有很多字母或数字是连续的，就想设计一个算法将字符串中连续的字母或数字进行压缩，如连续字符“abcd”可压缩为“a－d”，不连续的字符维持原状，例如，字符串“abcde1255hij”可压缩为“a－e1－255h－j”，并将压缩后的结果输出保存到“压缩后.txt”中。
该算法的部分Python代码如下：
def writedata(data)：
#将数据 data 输入到″压缩后.txt″中，代码略
fp＝open(″压缩前.txt″)
lines＝fp.readlines()
fp.close()
for line in lines:
　 flag＝False
　 ans＝″″
　 for i in range(len(line)－1)：
　 if ：
　　　 ans＋＝line[i]＋″－″
　　　 flag＝True
　 elif ord(line[i＋1])！＝ord(line[i])＋1：
　　　 ①________
　　　 flag＝False
　 ans＋＝line[i＋1]
　 ②________
(1)执行程序后，当输入字符串s 的值为″efg1234345hijk″时， 压缩后的字符串为________。
(2)请在划线处填入合适的代码。
(3)程序中加框处代码有误，请改正。
变式 老年机因其较大的按键，很适合老年人使用，但其中英文字母的输入方式比较麻烦，导致很多老年人不太会用。如图是一款老年机的键盘，其字母的输入方式如下：
(1)若要输入英文字母“A”，则2键按1下；若要输入“B”，则2键按两下；其他英文字母的输入方式同理。
(2)若连续输入的英文字母在同一数字键中，则在输入下一个英文字母前，需先按下1键以表示确定；若连续输入的英文字母不在同一数字键中，则不需要按1键，直接按所要输入英文字母对应的数字键即可。
(3)若要输入空格，则按0键。
王老师依据该手机的字母输入规则，设计了一个 Python 程序。实现输入按键被点击的顺序，显示手机中输入的英文内容的功能。程序运行界面如图所示：
>>> 输入按键编号顺序：7999844666166 输出的内容是：PYTHON >>>
实现该功能的程序代码如下：
keyboard＝{″0″：″″，″2″：″ABC″，″3″：″DEF″，″4″：″GHI″，″5″：″JKL″，″6″：″MNO″，″7″：″PQRS″，″8″：″TUV″，″9″：″WXYZ″}
yw＝input(″输入按键编号顺序：″)
①________
i＝k＝1
result＝″″
while i　 if yw[i]＝＝key：
k＝k＋1
　　else：
if yw[i]＝＝″1″：
　　　 ②________
result＋＝keyboard[key][k－1]
key＝yw[i]
③________
　　 i＝i＋1
result＋＝keyboard[key][k－1]
print(″输出的内容是：″，result)
请回答下列问题：
(1)若按键点击的顺序是“616661666166”，则手机中输入的英文是________。
(2)要实现程序的功能，请完善划线处的代码。
重难点3　双重遍历
当一个集合或两个集合中元素进行组合时，往往需要对这些集体遍历多次。可能发生的情景有：①对一个过程重复多次，如在二维表中，重复读取一行数据，并对一行数据进行分解处理，即一个集合有多个元素，每个元素有多个数据项。还有读取一个多行的文本文件，处理每行数据，对一个DataFrame对象进行遍历，查询数据项的过程等等；②在一个集合中，找出两个数据的组合，如统计一个数据的排名，各种排序算法，冒泡、插入排序等，还可以是一个连续段的开始位置和结束位置。③在两个集合中各取一个元素进行组合，把每一种组合遍历一次。
例题 挖金矿游戏。在一个8行8列的矩阵中，矿工位于第1行第1列的格子，n个金矿随机分布在第1行下面的各个格子中，每个金矿的横坐标依次保存x数组，纵坐标保存在y数组。矿工收集金矿方法：先确定每行最左边和最右边金矿的坐标，对于同一行的金矿，矿工先移动到最左边金矿正上方，再执行向下x步的指令进行挖矿，接着从该行左边第2个金矿开始一直挖到最右边。该行完成后，再依次挖下方各行的金矿。
如图a所示的金矿(图中黑色方块)分布图，按右侧所示的指令，可以收集全部金矿。
(1)现有4*4的金矿分布图如图b所示，矿工在左上角位置，写出矿工按规则获得所有金矿的指令(指令之间用逗号或空格隔开)_____________________________。
(2)编写程序，按顺序输出指令，使矿工按照规则得到所有金矿，将空白处填写完整。
x＝[2，2，5，5，5，8]　#各金矿行号，从小到大升序排列
y＝[1，2，4，5，8，6]　#各金矿列号，同一行金矿，列号从小到大升序排列
n＝len(x)　#金矿数量
px＝py＝1　#矿工初始位置行号和列号
i＝0
while i　 beg＝i
　　while i　 i＋＝1
　　if y[beg]　 print(″左″＋str(py－y[beg]))
　　elif y[beg]>py：
　 print(″右″＋str(①________))
　　　 print(″下″＋str(x[beg]－px))
　　　 print(″挖矿″)
　　　 for k in range(②________)：
　 print(″右″＋str(y[k]－y[k－1]))
　 print(″挖矿″)
px＝x[beg]
③________
i＋＝1
变式 某物品柜有5层，每层有10个格子，每个格子只能放一个物品。输入一组物品的高度值(按降序排列)，将这些物品放在同一层的连续格子中。第一步：查找存放物品的格子。从第1层开始查找，若该层物品柜连续空格数量小于物品数量，则查找下一层。查找5层后还是不能找到连续存放位置，输出“不能连续存放”。若在某一层中找到符合要求的连续空格子，则进行第二步：将物品按中间高两端低的原则存放物品。先将高度最高的物品存放在连续空格的中间位置(若空格数量为偶数，则放在中间靠左位置)，接着依次将物品按先右后左的顺序依次存放。如输入物品高度为8，5，2，1，则依次放在第1排的第5，6，4，7的位置。第一排各个格子存放物品高度如图所示，其中0表示未存放物品。
0 0 0 2 8 5 1 0 0 0
(1)输入第1组物品高度依次为8，5，2，第2组依次为9，6，3，1，则高度为3的物品存放在第1排第________(填数字)个格子中。
(2)实现该功能的Python程序段如下，将空白处填写完整。
#将已经存放的物品高度存储在数组a中，如：
[[0，9，6，2，8，5，1，0，0，0]，[0，0，1，7，10，9，2，0，0，0]，……]，代码略。
s＝input(″输入一组降序的物品高度，用逗号分开：″)
wp＝list(map(int，s.split(″，″)))　#输入的数字转换成列表
flag＝False；i＝0
while i <5 and not flag：
　 beg＝0
　　for j in range(10)：
　　　 if a[i][j]＝＝0：　#物品柜格子为0表示没有存放物品
　　　 if j－beg＋1>＝len(wp)：
　　　　　　 hang＝i；end＝j；flag＝True
　　　 else：
　　　 if flag：
　　　　　　 break
　　　 ①________
　　　i＋＝1
if flag：
　　　②________
　　　a[hang][wz]＝wp[0]
　　　i＝1
　　　while i　　　 if ③________：
　　　 wz－＝i
　 else：
　　　 wz＋＝i
　　　 a[hang][wz]＝wp[i]
　　　 i＋＝1
else：
　　print(″不能连续存放″)
#输出物品柜的存放情况，代码略
重难点1　单元素遍历
1.某智能货架有一排货位，货位号从 0 开始编号，每个货位等宽。货架上可放置不同宽度(占 1～3 个货位)的箱子，箱子从左往右连续相邻摆放。每次放置箱子时，只能在货架上最后一个箱子的右侧放置新箱子。可以搬离中间的某个箱子，但该箱右侧所有箱子被自动左移。编写程序，模拟搬离或放置操作，操作结束后，输出当前货架上所有箱子的起始位置。
请回答下列问题：
(1)若货架有5个箱子，状态如图所示，搬离第2个箱子后，当前货架上最后一个箱子的起始位置是________。
(2)实现上述功能的部分 Python 程序如下，请在划线处填入合适的代码。
#共有n 个箱子供操作，代码略
lst＝[－1]*n
st＝m＝0
while True：
　　'''操作序列如[″P1″，″M0″，……. ，″E″]，依次读取序列元素，存入变量op，″P1″表示放置宽度为 1 的箱子，″M0″表示搬离第 1 个箱子，代码略'''
　　if op[0] ＝＝″P″：
　 w ＝ int(op[1：])　#表示箱子的宽度为w
　 lst[m]＝st
　　　 st＝st＋w
　 ①________
　　elif op[0]＝＝″M″：
　 i ＝ int(op[1：])　#表示第 i＋1 个箱子将被搬离
　 if lst[i＋1] ！＝ －1：　#计算移动的距离
　　　 dis＝②________
　 else：
　　　 dis＝st－lst[i]
　 while lst[i＋1]！＝ －1:
　　　 lst[i]＝lst[i＋1]－dis
　　　 i＝i＋1
　 lst[i] ＝ －1
　 st＝③________
　 m ＝m － 1
　 else：
　 break
#输出当前货架上所有箱子的起始位置，代码略
2.实现第1题程序功能的程序代码还可以如下：
#共有n个箱子供操作，代码略
lst＝[－1]*n
wd＝[0]*n
st＝m＝0
while True：
　　'''操作序列如[″P1″，″M0″，……. ，″E″]，依次读取序列元素，存入变量op，″P1″表示放置宽度为 1 的箱子，″M0″表示搬离第 1 个箱子，代码略'''
　　if op[0] ＝＝″P″：
　 w ＝ int(op[1：])　#表示箱子的宽度为 w
　 lst[m]＝st
　 ①________
　 st＝st＋w
　 m＋＝1
　　elif op[0]＝＝″M″：
　 i ＝ int(op[1：])　#表示第 i＋1 个箱子将被搬离
　 t＝wd[i]
　 while ：
　　　 ②________
　　　 wd[i]＝ wd[i＋1]
　　　 i＝i＋1
　 ③________
　 st＝st－t
　 m ＝m － 1
　　else：
　 break
#输出当前货架上所有箱子的起始位置，代码略
(1)将程序空白处填写完整。
(2)实现加框处功能的语句还可以是________。
3.在一条宽度为L的直线小河中，一只青蛙想沿着直线从河的左侧跳到右侧。小河中有n片位置互不相同的荷叶，青蛙必须跳到荷叶上过河，否则会掉入水中。开始时青蛙站在河的左侧(坐标为0)，接着不停地向右侧跳跃，每次跳跃的距离不超过W，当青蛙跳到或跳过河的右侧(坐标为L)时，青蛙完成过河。根据小河的长度，青蛙每次跳跃的最大长度和荷叶位置，求至少需要增加的荷叶数。
hl＝32　#小河的长度
w＝4　#青蛙每次跳跃的最大长度
a＝[0，2，9，11，17，24，30]
a.append(hl)　#起点为a[0]，终点为河长hl，把该位置加入数组a中
p＝1　#第1片荷叶的初始索引位置
d＝tot＝0　#d表示青蛙的位置
while d　　if　①______________：
　　　 d＝ a[p]
　　　 ②______________
　　else:
　　　 tot＋＝1
　　　 ③______________
print(″至少需要增加的荷叶数为：″ ＋ str(tot))
4.某平台新上架影片推荐度的计算方式为：由5位专业评审与5位大众评审给影片评分，评分区间为[1，10]，将专业评审均分的60%与大众评审均分的40%进行求和并取整，根据得分确定等级(分值与等级的关系如图a所示)。评委打分情况如图b所示，“A”表示专业评审，“B”表示大众评审，“A4－10”表示第4位专业评审给出10分。
分值 等级
1－2 ★
3－4 ★★
5－6 ★★★
7－8 ★★★★
9－10 ★★★★★
图a
图b
请回答下列问题：
(1)若专业评审均分为6，大众评审均分为7，则该影片等级为________(填数字)颗星。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
f＝open(″dc.txt″，encoding＝″utf－8″)
line＝f.readline()　#读取第一行，保存在字符串line中
pro，pub＝0，0
while line：　#当line非空
　　①________
　　t＝int(line[3：])
　　if x＝＝″A″：
　 pro＋＝t
　　：
　 ②________
　　line＝f.readline()　#继续读取一行
score＝int(pro/5*0.6＋pub/5*0.4)
grade＝③________
print(″推荐度为：″，″★″*grade)
(3)若“dc.txt”文件中无异常数据，写出与加框处代码功能相同的语句________。
(注：只需写出一条语句，多于一条的以第1条语句为准)
5.某小区停车场停车使用车位锁，其中私家车车位，车主可将感应器插在私家车的USB电源接口上，感应器在30～50米内发出高频信号(如图a)，当私家车靠近，车位锁自动降下解锁，车离开(20秒后)车位锁自动升起上锁。其余为收费车位，可扫描二维码控制车位锁并收费(如图b)。
收费车位计费规则如下：停车时长不到半小时按2元计费；半小时及以上则按每小时5元计费；超过整小时部分，不足半小时的时长不计费，半小时及以上则按一小时计费。该停车场当日的停车记录存储在“parking.txt”文件中，文件内容如图c所示，每一行共有4项数据，用逗号分隔，每项数据分别为进(出)场时间、车牌号、进出场状态(0表示进场，1表示出场)、车位状态(0表示私家车位，1表示收费车位)。小林编写了Python程序，从该文本文件中读取所有数据，并计算该停车场当日的总收入。请完成下列问题：
图a　私家车位
图b　收费车位
图c
(1)私家车控制车位锁需要安装感应器，据题意，此感应器属于________(单选，填字母：A.距离传感器 / B.无源电子标签 / C.有源电子标签 / D.红外传感器)。
(2)程序代码如下所示，加框处代码有错误，请改正。
(3)请将划线处代码补充完整。
def calT(Tin，Tout)：
　 t1 ＝ int(Tin[11：13])*60 ＋ int(Tin[14：16])
　 t2 ＝ int(Tout[11：13])*60 ＋ int(Tout[14：16])
　 return t2－t1
f ＝ open('parking.txt'，'r')
line ＝ f.readline()
dic ＝ {}
price ＝ 5; total ＝ 0
while line：　#当 line 非空(从文件读取到了数据)
　　car ＝ line.strip().split('，')
　　if car[2]＝＝'0' and car[3]＝＝'1':
　 dic[car[1]] ＝ car[0]
　　：
　 T ＝①________
　 if T < 30：
　　　 fee ＝ 2
　 else：
　　　 fee ＝②________
　 total ＝ total ＋ fee
　　line ＝ f.readline()
f.close()
print(″本日停车费总收入为：″， total)
重难点2　连续多个元素遍历
1.随机生成一个仅由大写字母″X″″Y″″Z″组成长度为 n 的字符串，消除该字符串连续3个及以上的相同字符。例如，字符串″XZZYYYYZYZ″，第一步：消除字符4个″Y″，得到新字符串″XZZZYZ″；第二步：消除3个字符″Z″，得到新字符串″XYZ″。实现上述功能的Python程序如下，请回答下列问题：
(1)如有字符串“XYYYXXZZY”，则消除后，字符串为：________。
(2)请在程序划线处①②③④填入合适的代码，实现程序功能。
import random
def left(s，x)：　#查找与s[x]连续相同的最左边位置
　 while ①________________________：
　 x＝x－1
　 return x
def right(s，x): 　#查找与s[x]连续相同的最右边位置
　 while __②________________________ ：
　　　 x＋＝1
　 return x
n＝int(input(″请输入字符串的长度：″))
s＝″″
for i in range(n)：　#随机生成一个长度为n 的字符串
　 m＝random.randint(0, 2)　#
　 ③________________________
print(″生成的字符串为：″，s)
i＝0
while i　　L＝left(s，i)
　　R＝right(s，i)
　　if　④______________________ ：
　 s＝s[：L]＋s[R＋1：]
　 ⑤__________________
　 else：
　 i＋＝1
print(″最后的字符串为：″，s)
2.某酒店的房间编号为1到1000，对于空余的房间的记录，采用连续空房间的起始房间编号和连续空房间数量进行记录，例如：有空房间1、2、3、6、7、9号时，记录的方法为：(1，3)，(6，2)，(9，1)，共3条记录。当有人退房时，一般出现4种情况：
·若退出房间号为4时，属于“上靠”情况，则第1条记录修改为(1，4)；
·若退出房间号为5时，属于“下靠”情况，则第1条记录修改为(5，3)；
·若退出房间号为8时，属于“上下靠”情况，则第2条、第3条记录合并，修改为(6，4)；
·若退出房间号为12时，属于“不靠”情况，则新增1条记录为(12，1)。
请回答下列问题：
(1)当已有的空房间记录为(3，5)，(9，5)，(16，3)，(30，2)，当退出房间号为8时，空房间记录修改为________。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
″″″
读入已有的空房间记录，个数为n，这些记录已按房间起始号升序排好，每条记录的房间起始号存入数组room，对应的连续空房间的个数存入数组num，下标均为0到n－1
″″″
x＝int(input(″请输入退出房间号：″))
pos＝0
while　①________：
　 pos＋＝1
if pos>0 and pos<＝n－1 and room[pos－1]＋num[pos－1]＝＝x and x＋1＝＝room[pos]：
　 ②________
　 for i in range(pos，n－1)：
num[i]＝num[i＋1]
room[i]＝room[i＋1]
　 n－＝1
elif pos>0 and room[pos－1]＋num[pos－1]＝＝x:
　 num[pos－1]＋＝1
elif ③________：
　 room[pos]＝x
　 num[pos]＋＝1
else：
　 for i in range(n－1，pos－1，－1):
　 room[i＋1]＝room[i]
　 num[i＋1]＝num[i]
　 room[pos]＝x
　 num[pos]＝1
　 ④________
for i in range(n)：
　 print(room[i]，″″，num[i])
3.对某二值图像(颜色编号只有0、1)按如下规则对其进行数据压缩：
(1)记录原数据第1个位置的颜色编号；
(2)从左往右依次扫描颜色编号，统计并记录连续出现的相同颜色编号个数：
例如：图像的颜色编号压缩结果为“0，9，8，3”(用逗号分隔)
请回答下列问题：
(1)若某二值图像按此规则压缩的结果为“1，1，3，5，6”，则该图像的颜色数据中有________个1。
(2)定义如下jys(s)函数，参数s存储压缩结果，为字符串类型，如“0, 9, 8, 3”。函数功能是实现数据解压缩，函数以字符串类型返回原数据。请在划线处填入合适的代码。
def jys (s)：
　 d ＝ {″1″：″0″，″0″：″1″}
　 ①________
　 ns ＝″″；p ＝ s[0] ; i ＝ 2
　 while i < n：
num＝0
while ②________：
　　　　　 num ＝ num*10 ＋ int(s[i])
　　　　　 i ＋＝ 1
i ＋＝ 1
for j in range (num) ：
　　　　 ③________
p ＝ d[p]
　　return ns
4.非空字符串s由互不相同的n个英文小写字母按升序排列而成，可将其中连续的多个字母缩写(如“abcd”缩写为“a～d”，“ab”写作“a～b”)。例如字符串“abcghijkmnopqsvwxyz”可缩写为“a～cg－km～qsv～z”。对于s，每当输入一个小写字母c时，若c已存在于s中，则视为从s中删掉此字母；否则将c插入到s中，并保持字母升序，输出更新s后对应的缩写字符串。请回答下列问题：
(1)如图所示，初始时字符串为“abcghijkmnopqsvwxyz”，依次输入“d”、“z”、“o”，在当前状态下，更新字符串缩写为________。
原字符串缩写为：a～cg－km－qsv～2 →请输入一个小写字母：d 更新字符串缩写为：a～dg－km～qgv～z →请输入一个小写字母：2 更新字符串缩写为：a－dg－km～qsv～y →请输入一个小写字母：o 更新字符串缩写为：
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
def compress(s)：
　 s＋＝″～″
　 news ＝″″
　 cl＝s[0]
　 n＝len(s)
　 cnt＝1
　 for i in range(1，n)：
　 if　ord(s[i])＝＝ord(s[i－1])＋1：
　　　　 cnt＋＝1
　 else：
　　　　 if cnt ＝＝1：
　　　　 news＋＝cl
　　　　 else：
　　　　 news＋＝cl＋″～″＋s[i－1]
　　　　 ①________
　　　　 cnt＝1
　 return news
#每当输入一个字母后，更新字符串并输出相应的缩写字符串
s＝″abcghijkmnopqsvwxyz″
print(″原字符串缩写为：″，compress(s))
while True：
　 n＝len(s)
　　c＝input(″请输入一个小写字母：″)　#输入一个小写字母
　　pos ＝0
　　while ②__________：
　　　 pos ＋＝1
　　if pos＝＝n：
　　　 s＋＝c
　　elif c！＝s[pos]：
　　　 ③________
　　else：
　　　 s＝s[：pos]＋s[pos＋1：]
print(″更新字符串缩写为：″，compress(s))
5.某商场对所有商品按价格升序排序，按相同价格划分成一段的方式，将数据分割成若干段，对每段数据进行压缩，最后存储为一个数字序列，压缩规则如下：
①使用两个整数x，y对一段连续相同的价格数据进行压缩。其中x为当前段表示的商品的价格较前一段商品的价格的增值(若为第1段，则x为第1段的价格数据)，y表示当前段的数据个数(其中0≤x，y≤1000，且均为正整数)。
②将各段价格数据压缩的结果通过“，”连接。
例如，各商品价格为“1，1，3，3，3，5，8，9，9，9，9，10”，先将连续相同的各段数据进行压缩，然后连接各段压缩的结果，如图所示。
(1)已知升序的商品价格数据为“2，2，2，5，5，7，7，7，7，”，则压缩结果为________。
(2)根据上述压缩算法，设计一个对应的解压缩程序，用于求解压缩前的价格数据，其Python代码如下，请在划线处填入合适的代码。
s＝input()　#输入待解压的字符串
a＝[0]*1000　#用于存储各商品的价格
f＝False；tmp＝0；k＝1
for i in range(len(s))：
　 if ″0″<＝s[i]<＝″9″：
　 ①________
　 else：
　 if f＝＝False：
　　　 a[k]＝a[k－1]＋tmp
　　　 k＋＝1
　 else：
　　　 for j in range(tmp－1):
　　　　 ②________
　　　　 k＋＝1
　 f＝ ③________
　 tmp＝0
print(a[1：k])
(3)现有m元资金，希望从商场中购买两个商品，请根据上题中求解的商品价格(升序)，统计使用现有资金能购买两个商品的方案数，实现上述功能的Python代码如下。
m＝int(input())　#输入现有的资金数量
ans＝0
i＝1; j＝k－1
while i　 if a[i]＋a[j]>m:
　 j－＝1
　 else：
　 ________
　 i＋＝1
print(ans)
划线处应填入的代码是________。
(4)执行以上程序后，若解压后存入列表a中的价格数据为[0，22，22，24，55，76，77]，输入m＝100后输出的结果为11，则上述代码中的“else”分支执行了________次。
重难点3　双重遍历
1.数据在网络传输中，带宽是宝贵的资源，通过压缩传输的字符串，可以减少数据量，从而加快传输速度，节省带宽资源。现有一种字符压缩方法描述如下：对于连续的若干个相同的子串“X”会压缩为“[DX]”的形式(D是一个整数且1≤D≤99)，如字符串“ABABABAB”就压缩为“[4AB]”或者“[2[2AB]]”，类似于后面这种压缩之后再压缩的称为二重压缩。如果是“[2[2[2AB]]]”则是三重的。现给出一串压缩后的结果，并对其进行解压缩。
思路：先找出每个左括号的位置，然后从后往前枚举，找出每一个括号内要解压的子串以及要解压的次数，将子串解压后得到一个新串，重复操作，得到最终的解压缩结果。
例如：[2[2[2AB]]]→[2[2ABAB]]→[2ABABABAB]→ABABABABABABABAB。
(1)已知采用上述压缩方法得到的压缩结果是“[2Z[2DB]]”，则解压缩结果为________。
(2)根据上述描述，小明利用 Python 设计了一个解压缩程序，请在划线处填入合适的代码。
start ＝ []
s＝input(″请输入压缩结果：″)
for i in range(len(s))：
　 if s[i]＝＝″[″：
　 start.append(i)
for i in range(len(start)－1，－1，－1):
　 num＝0；temp＝″″
　 ①________
　 while j　　　if ″0″<＝s[j]<＝″9″：
　　　 num＝num*10＋int(s[j])
　　　else：
　　　 ②________
　　　j＋＝1
　 ans＝ num*temp
　 s＝s[：start[i]]＋③________　#重新构造字符串
print(″解压结果为：″＋s)
2.有m个人结伴旅行(m<＝9，每人用整数1～m编号)。期间既有全员参与的集体活动，也有自主参与的小团队活动。每项活动的消费由参与人平均分摊，其中一人先行垫付并记录。记录内容包括该项活动的人均消费金额(元)、参与人。每项活动的参与人用字符串表示，垫付人排在第1位。如″25134″表示2、5、1、3、4号参与该项活动，其中2号是垫付人。旅行活动结束依据所有活动的消费记录进行结算。要求输出转账明细。(编号小的付款人优先转账给编号小收款人)
(1)若有4个人参加3项活动，每项活动的参与人分别是“31”，“124”，“23”，每项活动的平均消费金额分别为50元，100元，300元， 则3号人员应还款项为________元。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
a＝['315', '523', '25134', '345', '41', '13524', '513', '451', '153']
x＝[50, 60, 30, 120, 75, 35, 95, 55, 30]
n＝len(a)
m＝5
#读取所有消费记录，显示在屏幕中，如图1所示，代码略
#计算每个人员的应还款额、输出转账明细
b＝[0 for i in range(m＋1)]　#保存应还款数据
for i in range(n)：　#根据消费记录计算应还款
　 p＝int(a[i][0])
　 b[p]－＝(len(a[i])－1)*x[i]
　 for j in range(1，len(a[i]))：
　 p＝int(a[i][j])
　 ①________________
print('人员 应还款项')
c＝0
for i in range(1，m＋1)：　#统计需要还款人的人数c
　 print(f' {i}{b[i]}')
　 if b[i]>0：
　 ②____________
print(“转账人 接收人 金额”)
i＝j＝1　#根据应还款数据计算转账明细
while c>0：
　 while b[i]<＝0：　#找第一个大于0的
　 i＋＝1
　 while b[j]>＝0：　#找第一个小于0的
　 j＋＝1
　 ③____________________
　 if w>0：
　 v＝b[i]－w
　 else：
　 v＝b[i]
　 c－＝1
　 b[i]－＝v
　 b[j]＋＝v
　 print(i，“→”，j , v)
3.编排试场。每个试场有30个座位，试场号、座位号和班内序号均从1开始。对n个班级的学生编排试场，要求连续分配座位的两个学生不属于同一个班级。
分配方法：按班级人数降序排列，每次编排第1个班级的学生，完成一个学生考号的编排后，先将第1和第2个班级互换，再从第2个班级开始排序，当班级人数小于等于后面班级人数时，依次交换。如1班至3班的人数为36，35，35，第1试场座位号1的学生为1班学生，交换并排序后的班级依次为2，3，1，每班人数均为35人，座位号为2的学生是第1个班级(2班)。
(1)若1班至4班的人数分别38，36，36，36，则第1试场座位号为5的班级是________。
(2)实现上述功能的部分 Python 程序如下，请在划线下填入合适的代码。
num＝[42，43，44，41，40，41，38]　#每个班级的人数
bj＝[3, 2, 1, 4, 6, 5, 7]　#每个班级的班号
n＝len(num)　#总共班级数量
bnxh＝[1 for i in range(n)]　#每个班级的班内序号
zwh＝sch＝1
scbp＝[]
while num[0]！＝0：
　 #准考证号格式为“入学年份(4位)＋班号(2位)＋班内序号(2位)”
　 s1＝″0″＋str(bj[0])；s2＝″0″＋str(bnxh[bj[0]－1])
　 s＝″2021″＋s1[－2：]＋s2[－2：]
　 scbp.append([sch，zwh，s]) #完成一个学生的编排，格式为：试场号，座位号，准考证号
　 ①________
　 zwh＋＝1
　 bnxh[bj[0]－1]＋＝1
　 if zwh＝＝31：
　 ②________
　 zwh＝1　
　 num[0]，num[1]＝num[1]，num[0]
　 bj[0]，bj[1]＝bj[1]，bj[0]
　 j＝1
　 while ③________：
　 num[j]，num[j＋1]＝num[j＋1]，num[j]
　 bj[j]，bj[j＋1]＝bj[j＋1]，bj[j]
　 j＋＝1
#输出编排的试场信息，代码略。
重难点1　单元素遍历
1.猜数游戏。游戏规则如下：设定一个秘密数，每猜错一次会得到格式为“iAjB”的提示，其中“iA”表示数字猜对且位置也猜对的数有i个，“jB”表示数字猜对但位置没猜对的数有j个。例如秘密数为“2507”时，若猜测数为“1702”，则提示是“1A2B”。
(1)现已知秘密数为“37692”，猜测数为“79612”，则提示是________。
(2)上述功能的部分Python程序如下，请在划线处填入合适的代码。
#将设定的秘密数存放于变量s中
while True：
　 g＝input()
　　if g ＝＝ s:
　 print(″猜对了″)；break
　　i＝A＝B＝0
　　cnt1, cnt2 ＝ [0] * 10, [0] * 10
　　while i　 if　①________ ：
　　　 A＋＝1
　 else：
　　　 cnt1[int(s[i])]＋＝1
　　　 ②________
　 i＋＝1
　for j in range(10)：
　 m＝ min(cnt1[j]，cnt2[j])
　 ③________
　print(″提示：″，str(A)＋″A″＋str(B)＋″B″)
2.机器人移动路线管理。机器人在一平面内按照程序预置数据来完成移动操作(如图a所示)，规则如下：①只能水平或垂直方向移动，方向取值：上：U、下：D、左：L、右：R，不能走斜线；每次移动1－5单位距离；②从起点出发，经过若干步后，尽可能返回到起点，如不能自动返回，则计算剩余移动次数。请完成划线处代码。
图a
图b
(1)解决上述问题的主程序如下：
bp＝startpos()　#输入起点坐标
dirt＝[]　#移动方向
step ＝[]　#移动距离
readdata()　#从data.csv文件中读取移动数据
pos＝[bp]　#从起点开始存储所有经过点的x、y坐标
for i in range(0，len(dirt))：　#利用预置数据移动
　 tmp ＝ move(pos[i]，dirt[i]，step[i])
　 pos.append(tmp)
　 print(″经过的位置点如下所示：″，″n″， pos)
if tmp＝＝________：　#判断能否返回起点
　 print(″可以直接返回起点位置！″)
else：
　　print(″不能直接返回起点位置！″，end＝″″)
　　stpx＝gettimes(pos[0][0], pos[－1][0])
　　stpy＝gettimes(pos[0][1], pos[－1][1])
　　print(″至少需要移动″＋str(stpx＋stpy)＋″次才能返回起点位置！″)
(2)编写函数startpos()，功能为输入起点坐标，返回坐标的值，返回值类型为列表。代码如下：
def startpos()：
　 x＝int(input('输入起点的x坐标：'))
　 y＝int(input('输入起点的y坐标：'))
　 return ________
(3)编写readdata()函数，功能为从csv文件中读取预置的移动数据。代码如下：
def readdata()：
　 import csv
　 f＝open(″data.csv″ ，″r″， encoding＝″utf－8″)
　 f_csv ＝ csv.reader(f)
　 title ＝ next(f_csv)　#读取标题行
　 for line in f_csv：
　 dirt.append(line[0])
　 step.append(__________)
　 f.close()
(4)编写位置移动函数move()，实现计算移动到的新位置。代码如下：
def move(pos, dr, lg)：　#位置移动
　 new_pos ＝[0，0]
　 if dr ＝＝″U″：
　 x＝0；y ＝1
　 elif dr＝＝″D″：
　 x＝0；y＝－1
　 elif dr ＝＝″L″：
　 x＝－1；y ＝0
　 elif dr＝＝″R″：
　 x＝1；y＝0
　new_pos[0]＝pos[0]＋x*lg
　________________
　return new_pos
(5)编写函数gettimes()，计算剩余移动次数。代码如下：
def gettimes(p1, p2)：
　 p＝abs(p1 － p2)∥5
　 if abs(p1－p2)%5！＝0：
　 ________
　 return p
3.抢红包游戏：微信抢红包游戏成为一代人的经典回忆，游戏将总金额为n的“红包”随机分配给m个玩家，红包的分配需同时满足以下规则：①所有人抢到的金额总和跟总金额n相等；②每个人至少抢到1分钱；③每个人抢到的金额随机；④每个人抢到金额大小的概率平等。
满足以上规则的最简单算法可描述为：假设总金额为n元，为使问题简单化，将总金额乘以100，此时的单位为分，使得问题在整数范围内解决。假设分发给m个人，则只需在[1，100*(n－1)]长度的范围内随机生成m－1个不重复的点，这些点将长为100*n的线段划分为m个段，每一段长度即可表示红包金额，再将每一段长度数据除以100换算为单位元输出。程序运行的结果如图所示。
输入红包金额：100 输入红包数量：5 红包金额：54.4，11.59，28.09，4.09，1.84 手气最佳：54.4
实现上述功能的Python程序如下，请在划线处填入合适的代码。
import random
n＝int(input(″输入红包金额：″))*100
m＝int(input(″输入红包数量：″))
if m>n：
　 print(″游戏无法继续，结束！″)
else：
　 f＝[False]*(n＋1)
　 for i in range(①________)：
　 t＝random.randint(1, n－1)
　 while f[t]：
　　　 t＝random.randint(1, n－1)
　 f[t]＝True
　 ②________
　 p＝0
　 amax＝0
　 s＝″″
　 for i in range(1，n＋1)：
　 if f[i]：
　　　　③________
　　　　s＋＝str(red/100)＋″，″
　　　　if red>amax：
　　　　 amax＝red
　　　　p＝i
print(″红包金额：″＋s[：－1])
print(″手气最佳：″ ＋ str(amax / 100))
4.有n名同学参加春游，已知现有公用经费total元，同时每位同学又随身携带一些现金，用数组cash存储。春游地点有不同类型自行车若干辆供游客租用，每种类型的自行车按租金从高到低存储在数组info中。info[i]表示某类型自行车信息，包含租金和数量。其中，info[i][0]表示该类型自行车租金，info[i][1]表示该类型自行车数量。
每位同学优先使用自己携带的现金租车，现金不够时可使用公用经费补足费用。为方便财务管理，规定每位同学只能为自己租用自行车，且不会相互借钱。请编写程序计算这n个同学是否能够全部租到自行车。
(1)若人数n＝5，total＝80，cash＝[21，15，10，8，5]，info＝[[60，1]，[50，2]，[35，2]，[25，3]]，判断这5个同学是否都能租到自行车________(单选，填字母：A.是/B.否)。
(2)完善程序，将①②处代码补充完整。
(3)将加框处代码换成i＝＝m，是否影响判断结果的准确性？________(单选，填字母：A.影响/B.不影响)
#total存储公用经费，info存储每种自行车的租金及库存，代码略
#读取n个同学现金数量，存储在数组cash中，并将cash降序排序，代码略
bike＝[]　#bike存储每辆自行车的租金
n＝len(cash)
for i in range(len(info))：
　 for j in range(info[i][1])：
　 bike.append(info[i][0])
m＝len(bike)
i＝①________
j＝0
while i＝0：
　 if bike[i]>cash[j]：
　 ②________
　 i＋＝1; j＋＝1
if ：
　　print(″能够满足全部同学租用自行车″)
else：
　　print(″资金不足， 无法满足″)
5.输入一个1－99999之间正整数金额，转换成相应的大写人民币形式，处理的方式：
1)人民币大写形式分″零壹贰叁肆伍陆柒捌玖″共10个数字和″拾佰仟万″4个单位。
2)从左向右向后处理每一位数字，同时读取该位数后面的一个数字。对当前数字分0和非0两个情况进行处理，若当前位为0，不加″拾佰仟万″等单位，如102转换为壹佰零贰元。
3)最后一位数单独处理，若为0，直接在转换后的字符串后加上“元”，否则加上对应的大写数字和文字“元”。
实现该功能的程序代码如下，请将划线处填写完整。
sn＝″零壹贰叁肆伍陆柒捌玖拾佰仟万″
s＝input(″输入一个大于0但小于10万的正整数：″)
ans＝″″
for i in ①________：
　 t1＝int(s[i])
　 t2＝int(s[i＋1])
　 if t1 ！＝0：
　 jedx＝sn[len(s)－2＋10－i]
　 ans＋＝sn[t1]＋ jedx
　 ②________：
　 ans＋＝sn[0]
③________
if t1！＝0：
　 ans＋＝sn[t1]
print(″转换的大写形式为：″＋ans＋″元″)
重难点2　连续多个元素遍历
1.现有一个由n位大写字母组成的密码串，将其分成m段长度相同的子密码串，已知n是m的倍数。小明编写了一个Python程序，输入密码串和正确的子密码串，检查这m段子密码串的正确情况。若子密码串与正确的子密码串不完全相同，则该子密码串错误，需指出错误字符在该子密码串中的位置。例如，密码串为“ABCDEFGABBDKFGABCDEFKABCDGFG”，正确的子密码串为“ABCDEFG”，则检查结果如图a所示，程序运行界面如图b所示。
图a
图b
(1)密码串为“ACDEFACDEEABDEFACDFF”，正确的子密码串为“ACDEF”，则有________段子密码串错误。(填：阿拉伯数字)
(2)实现上述功能的Python程序如下，请在程序划线处填入合适的代码。
pwst＝input(″请输入密码串：″)
pwsubst＝input(″请输入正确的子密码串：″)
n＝len(pwst)
p＝len(pwsubst)
m＝n∥p
errinfo＝[″″]*m
cnt＝0
for i in range(m):
　 j＝0
　 ①________
　 flagp＝0；info＝″″
　 while ②________：
if pwst[k]！＝pwsubst[j]:
　　　 flagp＋＝1
　　　 info＝info＋″″＋str(j＋1)
j＋＝1
k＋＝1
if flagp>0：
③________＝″第″＋str(i＋1)＋″段错误！错误位置：″＋info
cnt＋＝1
print(″共有″，cnt，″段错误″)
for i in range(cnt):
　 print(errinfo[i])
2.在仅包含星号*和小写字母的字符串中，可以对星号进行消除。若字符串中含有除星号和小写字母以外的其他字符，则输出无法消除；否则按如下规则进行消除：
①从左向右依次消除一个星号，直至消除所有的星号。
②一次消除时，需要同时消去星号及星号前的一个字母，若星号前无字母，则仅消除该星号。
如对字符串″pyt**ho*n″的消除过程为：
第1次消除″t*″，字符串变为″py*ho*n″第2次消除″y*″，字符串变为″pho*n″，第3次消除″o*″，字符串变为″phn″，消除完成，结果字符串为″phn″。
(1)对字符串″*fightin**g*″消除后的结果为________。
(2)编写程序实现上述消除，代码如下，请完成划线处的代码。
s＝input(″请输入一个字符串：″)
i＝0; flag＝True
while ①________：
　 if s[i]＝＝″*″：
　　　if i＝＝0：
　　　 s＝s[1：]
　　　 i－＝1
　　　else：
　　　 s＝②________
　　　 i－＝2
　 elif ③________：
　　　flag＝False
　 ④________
if flag：
　 print(″消除*后为：″，s)
else：
　 print(″含有其他字符，无法消除″)
3.如果连续数字之间的差严格地在正数和负数之间交替，则该序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。对于不是摆动序列的序列，可删除其中的部分元素，剩余元素顺序不变，从而得到符合要求的摆动子序列。
例如，[1，7，4，9，2]是一个5个数字的摆动序列，因为差值[6，－3，5，－7]为正负交替出现，如图a所示。但是[2，5，8，2，5]和[2，5，3，3，6]不是摆动序列，其中[2，5，8，2，5]的前两个差值都为正数，如图b所示，而[2，5，3，3，6]的倒数第二个差值为0，如图c所示。图b中②－⑤为递增，⑤－⑧不为递减，因此②－⑤－⑧中需要删除一个数，此外图c中⑤－③为递减，③－③不为递增，因此⑤－③－③中需要删除一个元素。摆动子序列的长度均为4。
编写程序，随机生成n个元素的序列，输出该序列中删除元素后最长摆动子序列的长度。
　　　 图a　　　　图b　　　　　图c
(1)若序列为[3，6，4，4，2，5，7]，则该序列删除元素后的最长摆动子序列的长度为________。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
import random
n＝int(input())
a＝[]
for i in range(①________):
　 a.append(random.randint(1，10))
print(a)　#输出随机生成的 n 个元素的序列
pre＝0
②________
for i in range(0，n－1):
　 cur＝a[i＋1]－a[i]
　 if pre<＝0 and cur>0 or ③________：
　 cnt＋＝1
　 pre＝cur
print(cnt)
4.某公路由于长期没有维修，路上出现了很多个坑。为了尽快填补好这些坑，交通管理部门决定对m处地段采取交通管制。将该公路看成一条直线，坑就是直线上的坐标点，坑所在的路段需要封控管制。例如某管制路段2～4，需封控2、3、4路段。交管部门为了减少管制路段的长度，希望将这n个坑分成m段(一段可以只有一个坑)，使得这m段公路的总长度最小。请你根据n个坑的位置(位置已按照从小到大进行排序)，计算管制路段最小的总长度。代码运行效果如图所示。
路段数量：4 坑的坐标依次为：3，4，6，8，14，15，16，17，21，25，26，27，30，31，40，41，42，43 维修管制的路段依次为： 3～8 14～17 21～31 40～43 管制总长度为25
请回答下列问题：
(1)上图所示的例子中，若将路段数量修改为5，则管制路段总长度为________。
(2)实现上述功能的Python程序如下，请在划线处填入合适的代码。
m ＝ int(input(″路段数量：″))
s ＝ input(″坑的坐标依次为：″).split('，')
n ＝ len(s)
for i in range(n):
　 s[i] ＝ int(s[i])
flag ＝ [False] * (n－1)
for i in range(1, m)：
　 k ＝ －1
　 for j in range(n－1)：
　 if ①________：
　　　 if k ＝＝ －1 or s[j＋1]－s[j] > s[k＋1]－s[k]:
　　　　　 k ＝ j
flag[k] ＝ True
print(″维修管制的路段依次为：″)
dis, t ＝ 0, 0
for i in range(n－1):
　 if flag[i]：
　 print(s[t]，″～″，s[i])
　 dis ＋＝ s[i]－s[t]＋1
　 ②________
print(s[t]，″～″，s[n－1])
dis ＝③________
print(″管制总长度为″，dis)
5.小明编写一个 Python 程序，实现找到字符串 s1 和 s2 中相同的最长子串s，并定位子串在字符串 s2 中出现的位置，运行结果如图所示。
s1：Python s2：thanks tnanks thanks 最长共同子串：　th 子串出现位置： 0/7/14/
(1)如输入s1和s2分别为“hello”和“hi”(不含引号)，输出最长共同子串是________。
(2)定义longstr函数，功能是找到字符串s1和s2中相同的最长子串，请在划线处填入合适的代码。
def longstr(s1, s2)：
　 m ＝ [[0] * (1 ＋ len(s2)) for i in range(1 ＋ len(s1))]
　 t, h ＝ 0, 0
　 for i in range(1, 1 ＋ len(s1))：
　 for j in range(1, 1 ＋ len(s2))：
　　　　 if　①________：
　　　　 m[i][j] ＝ m[i － 1][j － 1] ＋ 1
　　　　 if m[i][j] > t：
　　　　　　 t ＝ m[i][j]
　　　　　　 ②__________
　　　　else：
　　　　 m[i][j] ＝ 0
　　return s1[h － t：h]
(3)定义pos函数，功能是定位子串在字符串s2中出现的位置，请在划线处填入合适的代码。
def pos(st，s2)：
　 print(″子串出现位置：″)
　 start ＝ 0
　 if len(st) > 0：
　 while True：
　　　　 start ＝ s2.find(st, start)　#返回字符串s2中子串st出现的首字符索引，从索引start开始找，若找不到，则输出－1
　　　　 if start ＝＝ －1:
　　　　 break
　　　　 print(start, end＝″/″)
　　　　 ______________
(4)主程序，请在划线处填入合适的代码。
s1 ＝ input(″s1：″)
s2 ＝ input(″s2：″)
s ＝　____________
print(″最长共同子串：″， s)
pos(s，s2)
重难点3　双重遍历
1.每个人有智商qa和体力qb值，从n个申请人中挑选2人组队参加某挑战赛。条件一是2人的智商qa值都必须大于指定参数h；条件二是2人的体力qa值之差(较大值减较小值)小于h。在满足上述两个条件的所有2人组合中，挑选体力qb值之和最大的一个组合，若有多个相同最大的组合一并输出。(qa、qb和h的值均为正整数)
(1)实现上述功能的Python程序如下，请在划线处填入合适的代码。
(2)程序中加框处代码有误，请改正。
#读入qa和qb的值，依次保存在列表中，代码略
h＝int(input(″请输入参数h：″))
imax＝0；s＝[]; n＝len(qa)
for i in range(n－1)：
　 if ①________：
　 continue
　 for j in range(②________)：
　 if ③________：
　　　 if　qb[i]＋qb[j]>imax：
　　　　　 imax＝qb[i]＋qb[j]
　　　　　 s＝[qa[i]，qb[i]，qa[j]，qb[j]]
　　　 ：
　　　　　 s.append([qa[i]，qb[i]，qa[j]，qb[j]])
#输出最佳组合，代码略。
2.现代诗的连排格式为各句以“/”分开，例如余光中先生的《乡愁》的部分内容为：″小时候/乡愁是一枚小小的邮票/我在这头/母亲在那头/长大后/乡愁是一张窄窄的船票/我在这头/新娘在那头″，现以右起竖式形式打印这部分内容，如图所示。请回答下列问题：
(1)若按照右起竖式对“ABC/CBDA”进行打印，打印内容的第三行为________。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
#读取连排格式的现代诗内容，存入poem，代码略
s ＝ []; t ＝″″
poem ＋＝″/″
for c in poem：
　 if c ！＝″/″：
　 ①________
　 else：
　 s.append(t)　#列表s末尾追加一个元素
　 t ＝″″
maxlen ＝ 0
②________
for i in range(n)：
　 if len(s[i]) > maxlen：
　 maxlen ＝ len(s[i])
for i in range(maxlen)：
　 t ＝″″
　 for j in range(n)：
　 if　③________ ：
　　　 t ＝ s[j][i] ＋ t
　 else：
　　　 t ＝″″ ＋ t
　 print(t)
3.有n列砖组成的一面砖墙，每列砖由数量不等的砖块组成，每块砖的长宽高都为1。小明为了美化这面墙，需要在这面墙中找到一块面积最大的矩形用于涂鸦。如图a所示，有6列高度依次为2、1、5、6、2、3组成的砖墙，图b和图c是其中的两种方案。编写Python程序，找出面积最大的矩形，并输出其位置和面积。
(1)结合图 a，这面墙中可用于涂鸦的最大的矩形面积为________
(2)实现上述功能的Python代码如下，请在划线处填上合适的代码。
#数组num中依次存放各列砖墙的高度，代码略
maxs ＝ 0
n ＝ len(num)
for i in range(n):
　 minh＝num[i]
　 for j in ①________：
　 if minh > num[j]：
　　　 minh ＝ num[j]
　 ②________
　 if　s>maxs：
　　　　 ③________
　　　　 start ＝ i＋1
　　　　 end ＝ j＋1
print(″起止砖列编号为：″，start, end，″，最大面积为：″，maxs)
4.某影平台上架新影片时，需要先确定该影片的类型，如喜剧片、动作片、爱情片。确定某影片的类型，可根据已有的样本数据(如图a所示)进行分类。
某分类算法如下：计算该影片与样本中各影片分镜头的相似度，相似度可用距离公式来表示，例如“美人鱼”各分镜头数据如图b所示，其与“宝贝当家”影片的距离为。用该方法计算出“美人鱼”与样本中所有影片的距离，选取前k个最近距离的影片，统计出现频次最多的影片类型，即为该影片的类型。
电影名称 搞笑镜头 拥抱镜头 打斗镜头 影片类型
宝贝当家 45 2 9 喜剧片
唐人街探案 23 3 17 喜剧片
我的特 工爷爷 6 4 21 动作片
…… …… …… …… ……
泰坦尼克号 9 39 8 爱情片
罗马假日 9 38 2 爱情片
新步步惊心 8 34 17 爱情片
图a
电影名称 搞笑镜头 拥抱镜头 打斗镜头 影片类型
美人鱼 19 18 5 ？
图b
距离最近的前5部影片为： 唐人街探案19.62，罗马假日 22.56，新步步惊心 22.83, 泰坦尼克号 23.45，我的特工爷爷 24.92
图c
请回答下列问题：
(1)与《美人鱼》距离最近的前5部影片如图c所示，则该影片属于________(单选，填字母：A.喜剧片 /B.动作片 /C.爱情片)。
(2)定义如下mvmin(result，flag)函数，参数result列表存储距离，flag列表存储标记。若result＝[43，33，18，25，65]，flag＝[False，False，True，True，False]，则函数的返回值为________。
def mvmin(result，flag)：
　 mv＝10000　#假定result列表元素值不超过10000
　 for i in range(len(result))：
　 if mv>result[i] and flag[i]＝＝False：
　　　 mv＝result[i]
　　　 pos＝i
　 return pos
(3)实现电影分类的部分Python程序如下，请在划线处填入合适的代码。
'''
读取样本影片的镜头数据，存储在data中，每个元素包含5个数据项，分别对应电影名称、搞笑镜头、打斗镜头、拥抱镜头、影片类型。
如data＝[[″宝贝当家″，45，2，9，″喜剧片″]，……]，代码略。
'''
x＝[″美人鱼″，19，18，5]
dic＝{″喜剧片″：0，″动作片″：0，″爱情片″：0}
k＝5
result＝[0]*len(data)
for i in range(len(data))：
　 d＝0
　 for j in range(1，4)：
　 tmp＝①________
　 d＋＝tmp**2
　 result[i]＝round(d**0.5，2)　#结果保留2位小数
flag＝[False]*len(result)
print(″距离最近的前″，k，″部影片为：″)
while k>0：
　 p＝mvmin(result，flag)
　　flag[p]＝True
　　②________
　　print(data[p][0]，result[p]，end＝″，″)
　　③________
#统计前k个最近距离的影片中出现频次最多的类型，并输出该影片类型，代码略
5.某校图书馆提供 3 类自习室，A 类最多容纳 2 人，B 类最多容纳 4 人，C 类最多容纳 8 人，以 1 小时为单位进行预约，每人每天只能预约一次，每次预约仅限个人，规定预约时间结束之前必须离开。图书馆每天 6 点开馆，22 点闭馆。编写程序，输入某自习室号牌，根据已预约情况，输出该自习室还能被预约的时间段。例：读取“A102”已预约情况[[6，11], [15，18], [8，12], [15，22]]，其中“A102”表示为 A 类 102 号自习室，[6，11]表示某个人预约 6：00 开始，11：00 前必须离开，时间占用如图所示，则该自习室还能预约的时间段为[[6，8]，[11，15]，[18，22]]。请回答下列问题：
)
(1)若“B101”的已预约情况为[[6，11]，[8，12]，[8，11]，[6，12]]，则该自习室还能预约的时间段是________。(时间段格式参照题中样例)
(2)实现上述功能的部分Python代码如下，请在划线处填入合适的代码。
r ＝ input(″输入自习室号牌：″)
#根据自习室号牌 r，获取该自习室可容纳的人数上限和预约情况分别存入 ceil 和 time 中，代码略
#如 time ＝ [[6，11]，[15，18]，[8，12]，[15，22]]
bucket ＝ [0]*24　#记录该自习室每个时刻被预约的人数
for period in time：
　 for i in range(period[0]，①________):
　 bucket[i]＋＝ 1
ans ＝ []; rec ＝ []
for i in range(6，22)：
　 if bucket[i]　 rec.append(i)
　 if len(rec)＝＝0：
　 print(″该自习室目前没有可预约时段″)
　 else：
　 left，right ＝0，0
　 i＝1
　 while i　　　 if rec[i]＝＝rec[i－1]＋1：
　　　　　 ②________
　　　 else：
　　　　　　 ans.append([rec[left]，rec[right]＋1])
　　　　　　 left，right＝i，i
　　　 ③________
ans.append([rec[left], rec[right]＋1])
print(r，″可预约的时间：″， ans)
6.上城小学将在本学期开展趣味运动会，一(10)班的班主任邀请你为他们设计一个Python程序，用于挑选参加集体项目的选手。挑选规则为：当班级有足够候选人员时，进行随机挑选，并输出人员名单；若无足够人员时，提示“无足够候选人员参加比赛！”，并规定每个学生最多参加一个集体项目。程序要求用户按照规范输入比赛项目及相关人员要求，例如输入“投篮：8，2”即篮球项目要求男生8人，女生2人。该程序的运行效果如图所示：
请输入比赛项目及相关人员要求：跳绳：5，5， 赶猪：15，15；投篮：8，2 跳绳项目： 男：艾震宇　蔡温淼　叶埕奇　王子硕 女：王晓清　黄鑫橼　陈佳妮　陈昱彤　陈奕臻 赶猪项目： 无足够侯选人员参加比赛！ 投篮项目： 男：陈展骢　李俊翰　张子俊　刘泓成　胡海伟　王子涵　叶赛特　伍越 女：贾熙　钱梓涵
(1)实现挑选集体项目选手的Python代码如下，程序中用到的列表函数与方法如表所示，请在划线处填入合适代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop(i) 将列表w末尾下标为i的元素赋值给x，并将其从w中删除
(2)程序加框处代码有误，请改正。
from random import shuffle
def disp(inf)：
　 #将输入的字符串整理为指定格式，当输入字符串为″跳绳：10，10；投篮：8，2″，则将其调整为{″跳绳″： [10, 10]，″投篮″： [8, 2]}并返回。
def player(x，n): #输出列表前n个元素，并删除这些元素，返回删除后的新列表
　 for i in range(n):
　 ①________
　 print(xm，end＝″″)
　 return x
c＝[[″陈浩琦″，″男″]，[″王慧敏″，″女″], [″王子涵″，″男″], …]　#班级学生名单
ctemp＝[[]，[]]　#根据学生性别分别存储男生和女生名单
for ②________ in c:
　 if p[1]＝＝″男″：
　 ctemp[0].append(p[0])　#append()函数的功能为在列表末尾插入新元素
　 else：
　 ctemp[1].append(p[0])
inf＝input(″请输入比赛项目及相关人员要求：″)
s＝[″男″，″女″]
sj＝disp(inf)
for t in sj：　#变量遍历字典中的每个键
　 if sj[t][0]<＝len(ctemp[0]) and sj[t][1]<＝len(ctemp[1]):
　 print(t＋″项目：″)
　 for i in ③________：
　　　　 print(s[i]，end＝″：″)
　　　　 shuffle(ctemp[i])　#shuffle用于将序列的所有元素进行随机排序
　　　　
　　　　 print()
　　　 else：
　 print(t＋″项目：\\n无足够候选人员参加比赛！″)
7.某校举行趣味运动赛，共有n个比赛项目，每班派n位学生参加，每位同学分别参加一个项目。某班有n位选手报名参加比赛，现需要依据他们平时练习中各个项目的平均得分，找出最佳参赛组合，查找规则为各项目得分总和最大，例如：图a所示的数据中，最佳参赛组合是“唐昌新：跳绳，胡鹏：飞镖，杨胜超：颠球，陈伟：套圈”。完成下划线的代码。
图a
最佳参赛组合： 唐昌新　跳绳 胡鹏　 飞镖 杨胜超 　颠球 陈伟　 套圈
图b
def check(s)：#　判断s中是否有重复值
　 f＝[0]*len(s)
　 for i in s：
　 ①____________
　 if f[i]>1：
　　　　return False
　 return True
a＝[]
f＝open(″cj.txt″，″r″)
title＝f.readline().split()　#读取标题行
for line in f.readlines()：
　 line＝line.split()
　 a.append(line)
n＝len(a)；max＝0
for i in range(0，n**n)：
　 k＝i；s＝[0]*n；p＝0
　 while k！＝0：
　　　 s[p]＝k%n
　　　 k＝ ②________
　　　 p＝p＋1
　　if check(s)＝＝True：
　　　 sum＝0
　　　 for j in range(len(s)):
　　　　 sum＋＝int(③________)
　　　 if sum>max：
　　　　 ④__________
　　　　 ss＝s
print(″最佳参赛组合：”)
for i in range(n)：
　 print(a[i][0]，title[ss[i]＋1 ])
8.某影厅共12排，每排10座。座位编号以排号＋座号来命名，如第10排3座，编号命名为103。某一时刻，该影厅的最佳观影区为方框内的座位如图所示，即第5排3座～第10排8座的矩形位置。0表示该座位可选，非0表示已售(1表示系统推荐，2表示手工选择)
座位推荐算法：
(Ⅰ)只推荐最佳观影区的座位，并且所有座位号要连号。
(Ⅱ)优先选择最佳观影区内最中间的位置(若空位数为偶，则选择中间靠左)，若中间位置相同，则以靠前位置为佳。
(Ⅲ)若在最佳观影区内未找到可以推荐的座位时，系统将提示手工选择。
(1)如图所示的座位中，若要购买2张票，则推荐的排号是________
(2)实现上述功能的Python程序如下，请在划线处填入合适的代码。
#产生一个12行10列的二维数组，并随机产生座位情况，代码略
k＝int(input(″请输入购票数：″))
kwz＝0；wz＝[]
m＝12；n＝10
for i in range(4，10)：　#寻找中间空的座位，并把座位号保存到数组wz中。
　 for j in range(2，8)：
　 if a[i][j]＝＝0：
　　　　①________
　　　　wz.append(i*n＋j＋1)
#输出中间空位，代码略
minx＝n；s＝0；p＝0；x＝0
while p＋k－1　　if ②________
　 x＝abs(n∥2－(wz[p]＋wz[p＋k－1]))∥2%n　#计算中间位置
　 if x　　　 x＝minx
　　　 ③________
　　p＋＝1
ans＝″″
if s＝＝0：
　 ans ＝″未能推荐座位，请手工选座″
else：
　 for i in range(s，s＋k)：
　 ans ＝ ans ＋″第″ ＋ str(wz[i]∥n＋1) ＋″排″ ＋ str(wz[i] %n＋1) ＋″座″
print(ans)
9.某网约巴士，车上最初有12个空座位，从起点站向终点站行驶，不允许掉头或改变方向，现有新的订单，请判断其是否能预约成功。请回答下列问题：
(1)若网约巴士已预约成功的数据为：[2，1，5]，[1，3，7]，[3，2，8]，[2，4，7]，[3，5，10]，其中每个元素有3个数据项，分别表示预约人数、出发站点和到达站点，当前接到订单[4，5，8]，________(选填：能/不能)预约成功。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
#数组trips存储预约信息，trips[i]＝[num，start，end]表示第i个预约信息有num个乘客，出发站点为start，到达站点为end，站点编号为1～10。
total＝12　#空座位总数
stations＝10　#站点总数
diff＝[0]*(stations＋1)
count＝[0]*(stations)　#存储站点上下车后的乘客人数
for i in trips：
　 ①________
　 diff[i[2]]－＝i[0]
for j in range(1，stations)：
　for k in range(②________ )：
　 count[j]＋＝diff[k]
num＝int(input(″请输入乘车人数：″))
start＝int(input(″请输入出发站点编号：″))
end＝int(input(″请输入到达站点编号：″))
flag＝True
for i in range(start，end)：
　 if　③________：
　 flag＝False
　 break
if flag：
　　print(″预约成功， 请到站点等候！″)
else：
　　print(″该订单未能成功预约到即将驶来的 bus！″)
专题13　简单算法程序实现
学习目标　1. 基于生活中的问题设计情境，掌握分析问题、抽象建模、设计算法、编写程序的过程；
2.掌握利用算法解决问题的思维能力构建.
抽象和建模是用程序实现算法前的重要步骤，抽象找出影响问题的主要因素，明确已知什么和求什么。建模是描述主要因素之间的关系，一是明确方法，往往采用遍历列表的方法；二是明确步骤，往往是求符合条件的和、个数、最值和平均值。枚举算法简称枚举法，也称为列举法、穷举法，是暴力策略的具体体现，又称为蛮力法，在遍历过程中求值与条件进行比对的过程。枚举法的基本思想是：逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。
(2023年6月浙江省选考)某仓库有一排连续相邻的货位，编号依次为0～n－1，用于放置A、B两种类型的箱子，A型箱子占2个相邻货位，B型箱子占1个货位。编写程序，根据已完成的放置或搬离操作，输出空货位数及还可以放置A型箱子的最多数量(不移动已放置的箱子)。请回答下列问题：
箱子类型 操作类型 货位编号
B 放置 5
A 放置 2，3
B 放置 0
A 放置 7，8
A 搬离 2，3
(1)若n为10，开始时货位全空，经过如图所示的放置或搬离操作后，不移动已放置箱子的情况下，还可放置A型箱子的最多数量为________个。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
#读取货位总数存入n，代码略。
cnt1＝n
lst＝[0]*n　#货位状态，0表示对应的货位为空
while True：
　　#读取本次已描述数据：箱子类型、操作类型、货位编号起始值存入t，d和s，代码略
　　if t＝＝″A″：
　 w＝2
　　①________：
　 w＝1
　　else：　#不是″A″或″B″时退出循环
　 break
　　if d＝＝″P″：　#d为P时表示放置，否则表示搬离
　 ②________
　 else：
　 cnt1＋＝w
　 lst[s]＝1－lst[s]
　 if t＝＝″A″：
　 lst[s＋1]＝1－lst[s＋1]
　 i，cnt2＝0，0
　 while i< n－1：
　 if lst[i]＝＝0 and lst[i＋1]＝＝ 0：
　　　　 ③________
　　　　　cnt2＋＝ 1
　 i＋＝1
　　print(″当前空货位数″，cnt1，″，还可放置A型箱子的最多数量：″，cnt2)
答案　(1) 2或两　(2)①elif t＝＝'B' 或elif t＝＝″B″或elif t＝＝'″B″'或elif (t＝＝'B')　②cnt1－＝w或cnt1＝cnt1 － w　③i ＋＝1或i＝i＋1
解析　本题考查列表的遍历。(1)经过放置或搬离操作后，索引位置1－4是空的，6和9是空的，因此可以放置A型箱子2个。(2)① w是两种箱子所占货位，因此当输入是B时占位为1。②cnt1当前空货位数，d为P时表示放置，否则表示搬离，条件不成立时，空位增加，因此条件成立时，空位减少。③cnt2表示还可放置A型箱子的最多数量，当条件lst[i]＝＝0 and lst[i＋1]＝＝ 0成立时，表示可以放置A类型，因此下一个货位要跳过。
重难点1　单元素遍历
遍历是按照一定的规则和次序访问数据元素中的所有节点，使得每个节点都被访问一次且仅被访问一次。相同类型的数据往往保存在数组中，数组的特点是按照索引位置依次存放数据，若只有一个数组，可以通过按值访问的方法，对所有数据进行求和、计数、求平均值和求最大值或最小值等操作。若多个数组，他们拥有相同的索引，可以通过索引位置依次访问数据。
例题 根据某场馆一天中每位参观者的进馆和出馆时间，可统计该场馆当天人流量的分布情况。每个人进、出馆的时间用一个长度为11的字符串表示，例如“08：05－08：45”表示进馆时间为8点5分，出馆时间为8点45分。现要求统计当天馆内人数超过指定人数的总时长。
(1)8点01分到8点08分的进出馆人数如表所示：
分钟 01 02 03 04 05 06 07 08
进馆 人数 5 0 4 2 1 3 1 2
出馆 人数 0 1 1 1 6 3 2 2
馆内大于4人的时长为________分钟。
(2)每个参观者进入场馆和出馆时间保存在“参观记录.txt”文件中，编写Python程序，请将程序补充完整。
a＝[]
f＝open(″参观记录.txt″，encoding＝″utf－8″)
for i in f：
　 t＝i.find(″－″)
　 a.append(i[：t]＋″in″)
　 a.append(①________＋″out″)
#对列表a按时间进行升序排列，代码略。
sp ＝int(input(″请输入指定人数″))
t ＝ －1 ; cnt ＝ 0 ; sum ＝ 0
for i in a：
　 mts ＝int(i[：2])*60＋int(i[3：5])
　 if i[5：]＝＝″in″：
　 cnt＋＝1
　 else：
　 ②________
　 if cnt>sp：
　 if t＝＝－1：
　　　 t＝mts
　 elif t>－1：
　 ③________
　 t＝－1
print(″超过指定人数的总时长：″ ＋ str(sum) ＋″分钟″)
思维点拨
明考向 本题考查枚举算法、多分支选择结构
精点拨 (1)第1分钟5人，第3、4、5分钟分别在馆人数为7，8，3，后面的都没有超过4人，因此总时长为3分钟。(2)①把前后两个时间分开，分别加上in和out来区分。因此要找到“－”的位置t，当条件i[5：]＝＝″in″不成立时，取出出馆的时间。②当条件i[5：]＝＝″in″成立时，表示进馆，否则表示出馆，当前人数cnt应减少一个。③处是一个状态编程，当t值为－1时，表示还没有达到目标人数时状态，条件cnt>sp成立，且t值为－1，表示当前cnt值开始大于目标人数，因此t不是－1时，表示开始时间，当elif t>－1意味着cnt>sp不成立，表示这一段的结束时间，这一段的时间差为mts－t，把这些时间段累加起来
答案　(1)3　(2)①i[t＋1：]或 i[t＋1：len(i)]　②cnt－＝1　③sum＋＝mts－t
变式 每个人进、出馆的时间用一个长度为11的字符串表示，例如“08：05－08：45”表示进馆时间为8点05分，出馆时间为8点45分。现要求统计当天馆内人数超过指定人数的总时长，当天在馆人数最多时刻及在馆人数。
(1)8点01分到8点08分的进出馆人数如表所示：
分钟 01 02 03 04 05 06 07 08
进馆人数 5 0 4 2 1 3 1 2
出馆人数 0 1 1 1 6 3 2 2
在馆人数最多时刻为________。
(2)每个参观者进入场馆和出馆时间保存在“参观记录.txt”文件中，编写Python程序，请将程序补充完整。
rs＝[0]*540　#存储早上8点至下午5点每分钟的在馆人数
f＝open(″参观记录.txt″，encoding＝″utf－8″)
n＝0
for sj in f ：
　 m1＝int(sj[：2])*60＋int(sj[3：5])－480　#将入馆时间转换为上午8点以后的分钟数
　 m2＝int(sj[6：8])*60＋int(sj[9：11])－480
　 rs[m1]＋＝1
　 ①________
sp ＝int(input(″请输入指定人数：″))
totrs＝imax＝sumrs＝0
itime＝″″
for i in range(540)：
　 ②________
　 if totrs>sp：
　　　③________
　 if totrs>imax：
　　　imax＝totrs
　　　itime＝str(i∥60＋8)＋″：″＋str(i%60)
print(″超过指定人数的总时长：″ ＋ str(sumrs) ＋″分钟″)
print(″在馆人数最多时刻为：″ ＋ itime ＋″，共″ ＋ str(imax) ＋″人″)
答案　(1)8：04　(2)①rs[m2]－＝1　②totrs＋＝ rs[i]
③sumrs＋＝1
解析　本题考查枚举算法。(1)从8：01点到8：04人数变化情况依次为5，－1，3，1，在8：04分达到8人。(2)①rs存储早上8点至下午5点每分钟的在馆人数，m2表示出馆的时间，rs[m2]表示该时间的在馆人数，当有一个人出馆时，相应的在馆人数减少一人。②从早上8点开始遍历每分钟在馆人数，并进行累加到变量totrs中。③当累加和超过sp时，相应的时刻增加1个。
重难点2　连续多个元素遍历
在一个序列中遍历元素可以分为两种情况，一是对单个元素进行遍历，如对字符串进行加密、压缩算法。二是要找出序列中一个连续的子序列，如找一个依次相连的子串，找一个连续递增或递减的子序列。在第二种情况中，将涉及该元素与他前面或后面元素的关系，因此需与他们依次进行比较，比较总次数比元素的个数少1个。
例题 现有一个文档“压缩前.txt”中保存了大量的小写字母和数字，小明发现文档中有很多字母或数字是连续的，就想设计一个算法将字符串中连续的字母或数字进行压缩，如连续字符“abcd”可压缩为“a－d”，不连续的字符维持原状，例如，字符串“abcde1255hij”可压缩为“a－e1－255h－j”，并将压缩后的结果输出保存到“压缩后.txt”中。
该算法的部分Python代码如下：
def writedata(data)：
#将数据 data 输入到″压缩后.txt″中，代码略
fp＝open(″压缩前.txt″)
lines＝fp.readlines()
fp.close()
for line in lines:
　 flag＝False
　 ans＝″″
　 for i in range(len(line)－1)：
　 if ：
　　　 ans＋＝line[i]＋″－″
　　　 flag＝True
　 elif ord(line[i＋1])！＝ord(line[i])＋1：
　　　 ①________
　　　 flag＝False
　 ans＋＝line[i＋1]
　 ②________
(1)执行程序后，当输入字符串s 的值为″efg1234345hijk″时， 压缩后的字符串为________。
(2)请在划线处填入合适的代码。
(3)程序中加框处代码有误，请改正。
思维点拨
明考向 本题考查一个集合中两个元素的组合，或者是一段连续区间的开始位置和结束位置的遍历
精点拨 (1)略。(2)当条件ord(line[i＋1])！＝ord(line[i])＋1成立时，表示连续段已经结束，终点位置是i，因此需将line[i]连接入ans中。②读取一行数据，处理完后调用writedata函数，将压缩后的结果输出保存到“压缩后.txt”中。(3)找到连续段开始位置。flag是一个是否是头部的标志，初值为False，找到连续字符串的第1个位置后，flag的值变更为True
答案　(1)e－g1－43－5h－k　(2)① ans＋＝line[i]　②writedata(ans)　(3)ord(line[i＋1])＝＝ord(line[i])＋1 and not flag或ord(line[i＋1])＝＝ord(line[i])＋1 and flag＝＝False
变式 老年机因其较大的按键，很适合老年人使用，但其中英文字母的输入方式比较麻烦，导致很多老年人不太会用。如图是一款老年机的键盘，其字母的输入方式如下：
(1)若要输入英文字母“A”，则2键按1下；若要输入“B”，则2键按两下；其他英文字母的输入方式同理。
(2)若连续输入的英文字母在同一数字键中，则在输入下一个英文字母前，需先按下1键以表示确定；若连续输入的英文字母不在同一数字键中，则不需要按1键，直接按所要输入英文字母对应的数字键即可。
(3)若要输入空格，则按0键。
王老师依据该手机的字母输入规则，设计了一个 Python 程序。实现输入按键被点击的顺序，显示手机中输入的英文内容的功能。程序运行界面如图所示：
>>> 输入按键编号顺序：7999844666166 输出的内容是：PYTHON >>>
实现该功能的程序代码如下：
keyboard＝{″0″：″″，″2″：″ABC″，″3″：″DEF″，″4″：″GHI″，″5″：″JKL″，″6″：″MNO″，″7″：″PQRS″，″8″：″TUV″，″9″：″WXYZ″}
yw＝input(″输入按键编号顺序：″)
①________
i＝k＝1
result＝″″
while i　 if yw[i]＝＝key：
k＝k＋1
　　else：
if yw[i]＝＝″1″：
　　　 ②________
result＋＝keyboard[key][k－1]
key＝yw[i]
③________
　　 i＝i＋1
result＋＝keyboard[key][k－1]
print(″输出的内容是：″，result)
请回答下列问题：
(1)若按键点击的顺序是“616661666166”，则手机中输入的英文是________。
(2)要实现程序的功能，请完善划线处的代码。
答案　 (1)MOON　(2)①key＝yw[0]　②i＝i＋1
③k＝1
解析　(1)键6的第1个字母为M，同一数字键中，则在输入下一个英文字母前，需先按下 1 键，键6的第3个字母为O，第2个字母为N。(2)查找连续相同的键的个数。①变量i从1开始遍历，因此key的初值为yw[0]。若遍历到″1″，说明是相同两个键的分隔符，i的位置加1。③若不相同，则这个键是下一组的第1个键。
重难点3　双重遍历
当一个集合或两个集合中元素进行组合时，往往需要对这些集体遍历多次。可能发生的情景有：①对一个过程重复多次，如在二维表中，重复读取一行数据，并对一行数据进行分解处理，即一个集合有多个元素，每个元素有多个数据项。还有读取一个多行的文本文件，处理每行数据，对一个DataFrame对象进行遍历，查询数据项的过程等等；②在一个集合中，找出两个数据的组合，如统计一个数据的排名，各种排序算法，冒泡、插入排序等，还可以是一个连续段的开始位置和结束位置。③在两个集合中各取一个元素进行组合，把每一种组合遍历一次。
例题 挖金矿游戏。在一个8行8列的矩阵中，矿工位于第1行第1列的格子，n个金矿随机分布在第1行下面的各个格子中，每个金矿的横坐标依次保存x数组，纵坐标保存在y数组。矿工收集金矿方法：先确定每行最左边和最右边金矿的坐标，对于同一行的金矿，矿工先移动到最左边金矿正上方，再执行向下x步的指令进行挖矿，接着从该行左边第2个金矿开始一直挖到最右边。该行完成后，再依次挖下方各行的金矿。
如图a所示的金矿(图中黑色方块)分布图，按右侧所示的指令，可以收集全部金矿。
(1)现有4*4的金矿分布图如图b所示，矿工在左上角位置，写出矿工按规则获得所有金矿的指令(指令之间用逗号或空格隔开)_____________________________。
(2)编写程序，按顺序输出指令，使矿工按照规则得到所有金矿，将空白处填写完整。
x＝[2，2，5，5，5，8]　#各金矿行号，从小到大升序排列
y＝[1，2，4，5，8，6]　#各金矿列号，同一行金矿，列号从小到大升序排列
n＝len(x)　#金矿数量
px＝py＝1　#矿工初始位置行号和列号
i＝0
while i　 beg＝i
　　while i　 i＋＝1
　　if y[beg]　 print(″左″＋str(py－y[beg]))
　　elif y[beg]>py：
　 print(″右″＋str(①________))
　　　 print(″下″＋str(x[beg]－px))
　　　 print(″挖矿″)
　　　 for k in range(②________)：
　 print(″右″＋str(y[k]－y[k－1]))
　 print(″挖矿″)
px＝x[beg]
③________
i＋＝1
思维点拨
明考向 本题考查双重循环结构的应用
精点拨 (1)矿工在左上角位置，下1挖到第2行第1列的矿，下2挖到第4行1列的矿，再向右移动6，挖到第4行第4列的矿。(2)beg表示每一行最左边金矿的索引，条件x[i]＝＝x[i＋1]成立表示两个处于同一行的金矿，因此循环结束后，索引i表示当前行最右边的金矿的列号。①py表示矿工的列号，条件y[beg]>py成立表示最左边矿位于矿工的右边，需向右移动y[beg]－py个位置。②当前行可能还有多个金矿，因此当前已经挖了最左边beg位置上金矿，还需从y[beg＋1]位置挖到第y[i]列，由于range是一个左闭右开的区间，因此值为i＋1。③更新矿工的位置，其列号为最右边金矿的列号
答案　(1)下1挖矿下2挖矿右3挖矿或下1，挖矿，下2，挖矿，右3，挖矿　(2)①y[beg]－py　②beg＋1，i＋1　③py＝y[i]
变式 某物品柜有5层，每层有10个格子，每个格子只能放一个物品。输入一组物品的高度值(按降序排列)，将这些物品放在同一层的连续格子中。第一步：查找存放物品的格子。从第1层开始查找，若该层物品柜连续空格数量小于物品数量，则查找下一层。查找5层后还是不能找到连续存放位置，输出“不能连续存放”。若在某一层中找到符合要求的连续空格子，则进行第二步：将物品按中间高两端低的原则存放物品。先将高度最高的物品存放在连续空格的中间位置(若空格数量为偶数，则放在中间靠左位置)，接着依次将物品按先右后左的顺序依次存放。如输入物品高度为8，5，2，1，则依次放在第1排的第5，6，4，7的位置。第一排各个格子存放物品高度如图所示，其中0表示未存放物品。
0 0 0 2 8 5 1 0 0 0
(1)输入第1组物品高度依次为8，5，2，第2组依次为9，6，3，1，则高度为3的物品存放在第1排第________(填数字)个格子中。
(2)实现该功能的Python程序段如下，将空白处填写完整。
#将已经存放的物品高度存储在数组a中，如：
[[0，9，6，2，8，5，1，0，0，0]，[0，0，1，7，10，9，2，0，0，0]，……]，代码略。
s＝input(″输入一组降序的物品高度，用逗号分开：″)
wp＝list(map(int，s.split(″，″)))　#输入的数字转换成列表
flag＝False；i＝0
while i <5 and not flag：
　 beg＝0
　　for j in range(10)：
　　　 if a[i][j]＝＝0：　#物品柜格子为0表示没有存放物品
　　　 if j－beg＋1>＝len(wp)：
　　　　　　 hang＝i；end＝j；flag＝True
　　　 else：
　　　 if flag：
　　　　　　 break
　　　 ①________
　　　i＋＝1
if flag：
　　　②________
　　　a[hang][wz]＝wp[0]
　　　i＝1
　　　while i　　　 if ③________：
　　　 wz－＝i
　 else：
　　　 wz＋＝i
　　　 a[hang][wz]＝wp[i]
　　　 i＋＝1
else：
　　print(″不能连续存放″)
#输出物品柜的存放情况，代码略
答案　(1)7　(2)①beg＝j＋1　②wz＝(beg＋end)∥2　③i %2＝＝0
解析　本题考查二维数组的遍历和在一个序列中查找最值。(1)高度8，5，2依次存放第5、6、4的格子中，因此左边还有3个空格，右边有4个空格。高度9，6，3，1依次存放第8、9、7、10的格子中。(2)①确定连续空格子的最左边位置beg，若格子为空，计算连续空格子数量为j－beg＋1，若数量达到存放物品数量时，将flag设置为True。若格子不为空，则下一个空格子的位置只能在当前j的下一个位置。②中间位置的计算方法类似于二分查找，将左右位置相加再整除以2。③语句a[hang][wz]＝wp[0]的功能是放置最中间的物品，接下来放在i为1的物品，在中间的右边，即wz等于i＋1，当i的值为2时，放在左边的前面2个位置中，因此通过判断变量i的奇偶性来决定存放的位置。
重难点1　单元素遍历
1.某智能货架有一排货位，货位号从 0 开始编号，每个货位等宽。货架上可放置不同宽度(占 1～3 个货位)的箱子，箱子从左往右连续相邻摆放。每次放置箱子时，只能在货架上最后一个箱子的右侧放置新箱子。可以搬离中间的某个箱子，但该箱右侧所有箱子被自动左移。编写程序，模拟搬离或放置操作，操作结束后，输出当前货架上所有箱子的起始位置。
请回答下列问题：
(1)若货架有5个箱子，状态如图所示，搬离第2个箱子后，当前货架上最后一个箱子的起始位置是________。
(2)实现上述功能的部分 Python 程序如下，请在划线处填入合适的代码。
#共有n 个箱子供操作，代码略
lst＝[－1]*n
st＝m＝0
while True：
　　'''操作序列如[″P1″，″M0″，……. ，″E″]，依次读取序列元素，存入变量op，″P1″表示放置宽度为 1 的箱子，″M0″表示搬离第 1 个箱子，代码略'''
　　if op[0] ＝＝″P″：
　 w ＝ int(op[1：])　#表示箱子的宽度为w
　 lst[m]＝st
　　　 st＝st＋w
　 ①________
　　elif op[0]＝＝″M″：
　 i ＝ int(op[1：])　#表示第 i＋1 个箱子将被搬离
　 if lst[i＋1] ！＝ －1：　#计算移动的距离
　　　 dis＝②________
　 else：
　　　 dis＝st－lst[i]
　 while lst[i＋1]！＝ －1:
　　　 lst[i]＝lst[i＋1]－dis
　　　 i＝i＋1
　 lst[i] ＝ －1
　 st＝③________
　 m ＝m － 1
　 else：
　 break
#输出当前货架上所有箱子的起始位置，代码略
答案　(1)5　(2)①m＝m＋1　②lst[i ＋ 1]－ lst[i]　③st－dis
解析　(1)搬离第2个箱子，每个箱子向左移动3个单位，因此起始位置为5。(2)①从语句lst[m]＝st和st＝st＋w来看，m表示箱子索引号，st表示起始位置，起始位置每次增加箱子长度，因此箱子索引也要增加。②计算移动距离，条件lst[i＋1] ！＝ －1表示后面还有箱子，因此移出箱子的距离为前后两个箱子起始位置的差值。③语句lst[i] ＝ －1更新最后一个箱子往前移动后，少了一个箱子，因此起始位置也要相应往前移动。
2.实现第1题程序功能的程序代码还可以如下：
#共有n个箱子供操作，代码略
lst＝[－1]*n
wd＝[0]*n
st＝m＝0
while True：
　　'''操作序列如[″P1″，″M0″，……. ，″E″]，依次读取序列元素，存入变量op，″P1″表示放置宽度为 1 的箱子，″M0″表示搬离第 1 个箱子，代码略'''
　　if op[0] ＝＝″P″：
　 w ＝ int(op[1：])　#表示箱子的宽度为 w
　 lst[m]＝st
　 ①________
　 st＝st＋w
　 m＋＝1
　　elif op[0]＝＝″M″：
　 i ＝ int(op[1：])　#表示第 i＋1 个箱子将被搬离
　 t＝wd[i]
　 while ：
　　　 ②________
　　　 wd[i]＝ wd[i＋1]
　　　 i＝i＋1
　 ③________
　 st＝st－t
　 m ＝m － 1
　　else：
　 break
#输出当前货架上所有箱子的起始位置，代码略
(1)将程序空白处填写完整。
(2)实现加框处功能的语句还可以是________。
答案　(1)①wd[m]＝w　②lst[i] ＝ lst[i＋1]－t
③lst[i] ＝ －1或lst[m－1] ＝ －1　(2)i解析　本题考查列表的遍历和数据的移动。(1)①记录当前放置箱子的宽度。②将后面所有箱子向左移动，每个箱子的开始放置位置(共178张PPT)
第二部分　算法与程序设计
专题13　简单算法程序实现
1. 基于生活中的问题设计情境，掌握分析问题、抽象建模、设计算法、编写程序的过程；
2.掌握利用算法解决问题的思维能力构建.
目 录
CONTENTS
体系构建
01
真题再现
02
考点精练
03
当堂检测
04
课后练习
05
体系构建
1
抽象和建模是用程序实现算法前的重要步骤，抽象找出影响问题的主要因素，明确已知什么和求什么。建模是描述主要因素之间的关系，一是明确方法，往往采用遍历列表的方法；二是明确步骤，往往是求符合条件的和、个数、最值和平均值。枚举算法简称枚举法，也称为列举法、穷举法，是暴力策略的具体体现，又称为蛮力法，在遍历过程中求值与条件进行比对的过程。枚举法的基本思想是：逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。
真题再现
2
(2023年6月浙江省选考)某仓库有一排连续相邻的货位，编号依次为0～n－1，用于放置A、B两种类型的箱子，A型箱子占2个相邻货位，B型箱子占1个货位。编写程序，根据已完成的放置或搬离操作，输出空货位数及还可以放置A型箱子的最多数量(不移动已放置的箱子)。请回答下列问题：
箱子类型 操作类型 货位编号
B 放置 5
A 放置 2，3
B 放置 0
A 放置 7，8
A 搬离 2，3
答案　(1) 2或两　(2)①elif t＝＝'B' 或elif t＝＝″B″或elif t＝＝'″B″'或elif (t＝＝'B')　②cnt1－＝w或cnt1＝cnt1 － w　③i ＋＝1或i＝i＋1
解析　本题考查列表的遍历。(1)经过放置或搬离操作后，索引位置1－4是空的，6和9是空的，因此可以放置A型箱子2个。(2)① w是两种箱子所占货位，因此当输入是B时占位为1。②cnt1当前空货位数，d为P时表示放置，否则表示搬离，条件不成立时，空位增加，因此条件成立时，空位减少。③cnt2表示还可放置A型箱子的最多数量，当条件lst[i]＝＝0 and lst[i＋1]＝＝ 0成立时，表示可以放置A类型，因此下一个货位要跳过。
考点精练
3
重难点1　单元素遍历
遍历是按照一定的规则和次序访问数据元素中的所有节点，使得每个节点都被访问一次且仅被访问一次。相同类型的数据往往保存在数组中，数组的特点是按照索引位置依次存放数据，若只有一个数组，可以通过按值访问的方法，对所有数据进行求和、计数、求平均值和求最大值或最小值等操作。若多个数组，他们拥有相同的索引，可以通过索引位置依次访问数据。
例题 根据某场馆一天中每位参观者的进馆和出馆时间，可统计该场馆当天人流量的分布情况。每个人进、出馆的时间用一个长度为11的字符串表示，例如“08：05－08：45”表示进馆时间为8点5分，出馆时间为8点45分。现要求统计当天馆内人数超过指定人数的总时长。
(1)8点01分到8点08分的进出馆人数如表所示：
分钟 01 02 03 04 05 06 07 08
进馆人数 5 0 4 2 1 3 1 2
出馆人数 0 1 1 1 6 3 2 2
馆内大于4人的时长为________分钟。
思维点拨
明考向 本题考查枚举算法、多分支选择结构
精点拨 (1)第1分钟5人，第3、4、5分钟分别在馆人数为7，8，3，后面的都没有超过4人，因此总时长为3分钟。(2)①把前后两个时间分开，分别加上in和out来区分。因此要找到“－”的位置t，当条件i[5：]＝＝″in″不成立时，取出出馆的时间。②当条件i[5：]＝＝″in″成立时，表示进馆，否则表示出馆，当前人数cnt应减少一个。③处是一个状态编程，当t值为－1时，表示还没有达到目标人数时状态，条件cnt>sp成立，且t值为－1，表示当前cnt值开始大于目标人数，因此t不是－1时，表示开始时间，当elif t>－1意味着cnt>sp不成立，表示这一段的结束时间，这一段的时间差为mts－t，把这些时间段累加起来
答案　(1)3　(2)①i[t＋1：]或 i[t＋1：len(i)]　②cnt－＝1　③sum＋＝mts－t
变式 每个人进、出馆的时间用一个长度为11的字符串表示，例如“08：05－08：45”表示进馆时间为8点05分，出馆时间为8点45分。现要求统计当天馆内人数超过指定人数的总时长，当天在馆人数最多时刻及在馆人数。
(1)8点01分到8点08分的进出馆人数如表所示：
分钟 01 02 03 04 05 06 07 08
进馆人数 5 0 4 2 1 3 1 2
出馆人数 0 1 1 1 6 3 2 2
在馆人数最多时刻为________。
(2)每个参观者进入场馆和出馆时间保存在“参观记录.txt”文件中，编写Python程序，请将程序补充完整。
rs＝[0]*540　#存储早上8点至下午5点每分钟的在馆人数
f＝open(″参观记录.txt″，encoding＝″utf－8″)
答案　(1)8：04　(2)①rs[m2]－＝1　②totrs＋＝ rs[i] ③sumrs＋＝1
解析　本题考查枚举算法。(1)从8：01点到8：04人数变化情况依次为5，－1，3，1，在8：04分达到8人。(2)①rs存储早上8点至下午5点每分钟的在馆人数，m2表示出馆的时间，rs[m2]表示该时间的在馆人数，当有一个人出馆时，相应的在馆人数减少一人。②从早上8点开始遍历每分钟在馆人数，并进行累加到变量totrs中。③当累加和超过sp时，相应的时刻增加1个。
重难点2　连续多个元素遍历
在一个序列中遍历元素可以分为两种情况，一是对单个元素进行遍历，如对字符串进行加密、压缩算法。二是要找出序列中一个连续的子序列，如找一个依次相连的子串，找一个连续递增或递减的子序列。在第二种情况中，将涉及该元素与他前面或后面元素的关系，因此需与他们依次进行比较，比较总次数比元素的个数少1个。
例题 现有一个文档“压缩前.txt”中保存了大量的小写字母和数字，小明发现文档中有很多字母或数字是连续的，就想设计一个算法将字符串中连续的字母或数字进行压缩，如连续字符“abcd”可压缩为“a－d”，不连续的字符维持原状，例如，字符串“abcde1255hij”可压缩为“a－e1－255h－j”，并将压缩后的结果输出保存到“压缩后.txt”中。
思维点拨
明考向 本题考查一个集合中两个元素的组合，或者是一段连续区间的开始位置和结束位置的遍历
精点拨 (1)略。(2)当条件ord(line[i＋1])！＝ord(line[i])＋1成立时，表示连续段已经结束，终点位置是i，因此需将line[i]连接入ans中。②读取一行数据，处理完后调用writedata函数，将压缩后的结果输出保存到“压缩后.txt”中。(3)找到连续段开始位置。flag是一个是否是头部的标志，初值为False，找到连续字符串的第1个位置后，flag的值变更为True
答案　(1)e－g1－43－5h－k　(2)① ans＋＝line[i]　②writedata(ans)　(3)ord(line[i＋1])＝＝ord(line[i])＋1 and not flag或ord(line[i＋1])＝＝ord(line[i])＋1 and flag＝＝False
变式 老年机因其较大的按键，很适合老年人使用，但其中英文字母的输入方式比较麻烦，导致很多老年人不太会用。如图是一款老年机的键盘，其字母的输入方式如下：
(1)若要输入英文字母“A”，则2键按1下；若要输入“B”，
则2键按两下；其他英文字母的输入方式同理。
(2)若连续输入的英文字母在同一数字键中，则在输入下一个英文字母前，需先按下1键以表示确定；若连续输入的英文字母不在同一数字键中，则不需要按1键，直接按所要输入英文字母对应的数字键即可。
(3)若要输入空格，则按0键。
王老师依据该手机的字母输入规则，设计了一个 Python 程序。实现输入按键被点击的顺序，显示手机中输入的英文内容的功能。程序运行界面如图所示：
>>>
输入按键编号顺序：7999844666166
输出的内容是：PYTHON
>>>
实现该功能的程序代码如下：
keyboard＝{″0″：″″，″2″：″ABC″，″3″：″DEF″，″4″：″GHI″，″5″：″JKL″，″6″：″MNO″，″7″：″PQRS″，″8″：″TUV″，″9″：″WXYZ″}
yw＝input(″输入按键编号顺序：″)
①________
i＝k＝1
请回答下列问题：
(1)若按键点击的顺序是“616661666166”，则手机中输入的英文是________。
(2)要实现程序的功能，请完善划线处的代码。
答案　 (1)MOON　(2)①key＝yw[0]　②i＝i＋1 ③k＝1
解析　(1)键6的第1个字母为M，同一数字键中，则在输入下一个英文字母前，需先按下 1 键，键6的第3个字母为O，第2个字母为N。(2)查找连续相同的键的个数。①变量i从1开始遍历，因此key的初值为yw[0]。若遍历到″1″，说明是相同两个键的分隔符，i的位置加1。③若不相同，则这个键是下一组的第1个键。
重难点3　双重遍历
当一个集合或两个集合中元素进行组合时，往往需要对这些集体遍历多次。可能发生的情景有：①对一个过程重复多次，如在二维表中，重复读取一行数据，并对一行数据进行分解处理，即一个集合有多个元素，每个元素有多个数据项。还有读取一个多行的文本文件，处理每行数据，对一个DataFrame对象进行遍历，查询数据项的过程等等；②在一个集合中，找出两个数据的组合，如统计一个数据的排名，各种排序算法，冒泡、插入排序等，还可以是一个连续段的开始位置和结束位置。③在两个集合中各取一个元素进行组合，把每一种组合遍历一次。
例题 挖金矿游戏。在一个8行8列的矩阵中，矿工位于第1行第1列的格子，n个金矿随机分布在第1行下面的各个格子中，每个金矿的横坐标依次保存x数组，纵坐标保存在y数组。矿工收集金矿方法：先确定每行最左边和最右边金矿的坐标，对于同一行的金矿，矿工先移动到最左边金矿正上方，再执行向下x步的指令进行挖矿，接着从该行左边第2个金矿开始一直挖到最右边。该行完成后，再依次挖下方各行的金矿。
如图a所示的金矿(图中黑色方块)分布图，按右侧所示的指令，可以收集全部金矿。
思维点拨
答案　(1)下1挖矿下2挖矿右3挖矿或下1，挖矿，下2，挖矿，右3，挖矿　
(2)①y[beg]－py　②beg＋1，i＋1　③py＝y[i]
明考向 本题考查双重循环结构的应用
精点拨 (1)矿工在左上角位置，下1挖到第2行第1列的矿，下2挖到第4行1列的矿，再向右移动6，挖到第4行第4列的矿。(2)beg表示每一行最左边金矿的索引，条件x[i]＝＝x[i＋1]成立表示两个处于同一行的金矿，因此循环结束后，索引i表示当前行最右边的金矿的列号。①py表示矿工的列号，条件y[beg]>py成立表示最左边矿位于矿工的右边，需向右移动y[beg]－py个位置。②当前行可能还有多个金矿，因此当前已经挖了最左边beg位置上金矿，还需从y[beg＋1]位置挖到第y[i]列，由于range是一个左闭右开的区间，因此值为i＋1。③更新矿工的位置，其列号为最右边金矿的列号
变式 某物品柜有5层，每层有10个格子，每个格子只能放一个物品。输入一组物品的高度值(按降序排列)，将这些物品放在同一层的连续格子中。第一步：查找存放物品的格子。从第1层开始查找，若该层物品柜连续空格数量小于物品数量，则查找下一层。查找5层后还是不能找到连续存放位置，输出“不能连续存放”。若在某一层中找到符合要求的连续空格子，则进行第二步：将物品按中间高两端低的原则存放物品。先将高度最高的物品存放在连续空格的中间位置(若空格数量为偶数，则放在中间靠左位置)，接着依次将物品按先右后左的顺序依次存放。如输入物品高度为8，5，2，1，则依次放在第1排的第5，6，4，7的位置。第一排各个格子存放物品高度如图所示，其中0表示未存放物品。
0 0 0 2 8 5 1 0 0 0
(1)输入第1组物品高度依次为8，5，2，第2组依次为9，6，3，1，则高度为3的物品存放在第1排第________(填数字)个格子中。
(2)实现该功能的Python程序段如下，将空白处填写完整。
#将已经存放的物品高度存储在数组a中，如：
[[0，9，6，2，8，5，1，0，0，0]，[0，0，1，7，10，9，2，0，0，0]，……]，代码略。
s＝input(″输入一组降序的物品高度，用逗号分开：″)
wp＝list(map(int，s.split(″，″)))　#输入的数字转换成列表
flag＝False；i＝0
while i <5 and not flag：
答案　(1)7　(2)①beg＝j＋1　②wz＝(beg＋end)∥2　③i %2＝＝0
解析　本题考查二维数组的遍历和在一个序列中查找最值。(1)高度8，5，2依次存放第5、6、4的格子中，因此左边还有3个空格，右边有4个空格。高度9，6，3，1依次存放第8、9、7、10的格子中。(2)①确定连续空格子的最左边位置beg，若格子为空，计算连续空格子数量为j－beg＋1，若数量达到存放物品数量时，将flag设置为True。若格子不为空，则下一个空格子的位置只能在当前j的下一个位置。②中间位置的计算方法类似于二分查找，将左右位置相加再整除以2。③语句a[hang][wz]＝wp[0]的功能是放置最中间的物品，接下来放在i为1的物品，在中间的右边，即wz等于i＋1，当i的值为2时，放在左边的前面2个位置中，因此通过判断变量i的奇偶性来决定存放的位置。
当堂检测
4
重难点1　单元素遍历
重难点2　连续多个元素遍历
重难点3　双重遍历
1.某智能货架有一排货位，货位号从 0 开始编号，每个货位等宽。货架上可放置不同宽度(占 1～3 个货位)的箱子，箱子从左往右连续相邻摆放。每次放置箱子时，只能在货架上最后一个箱子的右侧放置新箱子。可以搬离中间的某个箱子，但该箱右侧所有箱子被自动左移。编写程序，模拟搬离或放置操作，操作结束后，输出当前货架上所有箱子的起始位置。
答案　(1)5　(2)①m＝m＋1　②lst[i ＋ 1]－ lst[i]　③st－dis
解析　(1)搬离第2个箱子，每个箱子向左移动3个单位，因此起始位置为5。
(2)①从语句lst[m]＝st和st＝st＋w来看，m表示箱子索引号，st表示起始位置，起始位置每次增加箱子长度，因此箱子索引也要增加。②计算移动距离，条件lst[i＋1] ！＝ －1表示后面还有箱子，因此移出箱子的距离为前后两个箱子起始位置的差值。③语句lst[i] ＝ －1更新最后一个箱子往前移动后，少了一个箱子，因此起始位置也要相应往前移动。
解析　本题考查列表的遍历和数据的移动。(1)①记录当前放置箱子的宽度。②将后面所有箱子向左移动，每个箱子的开始放置位置也要发生变动，后一个箱子的开始位置就是当前箱子的结束位置，将该位置减去移动箱子的宽度，就是移动的距离。③将第m个箱子移动后，该位置初始值设置为－1。(2)一共有m个箱子，最后一个箱子的索引为m－1。
答案　(1)①wd[m]＝w　②lst[i] ＝ lst[i＋1]－t
③lst[i] ＝ －1或lst[m－1] ＝ －1　(2)i3.在一条宽度为L的直线小河中，一只青蛙想沿着直线从河的左侧跳到右侧。小河中有n片位置互不相同的荷叶，青蛙必须跳到荷叶上过河，否则会掉入水中。开始时青蛙站在河的左侧(坐标为0)，接着不停地向右侧跳跃，每次跳跃的距离不超过W，当青蛙跳到或跳过河的右侧(坐标为L)时，青蛙完成过河。根据小河的长度，青蛙每次跳跃的最大长度和荷叶位置，求至少需要增加的荷叶数。
hl＝32　#小河的长度
w＝4　#青蛙每次跳跃的最大长度
a＝[0，2，9，11，17，24，30]
a.append(hl)　#起点为a[0]，终点为河长hl，把该位置加入数组a中
p＝1　#第1片荷叶的初始索引位置
d＝tot＝0　#d表示青蛙的位置
while d答案　①a[p]－d>＝w　②p＝p＋1　③d＋＝w
解析　①变量d表示青蛙所处位置，他可能在荷叶上，也可能在新增加的荷叶上，变量p表示青蛙下一步要到过的荷叶或位置，因此只有满足条件a[p]－d>＝w才可能到达下一荷叶，若条件为a[p]－a[p－1]>＝w，当青蛙无法一步到达下一张荷叶时，虽然在else增加了荷叶，但a[p－1]的值没有发生变化，因此还是无法达到下一张荷叶。②更新荷叶的位置。③增加了一张荷叶，更新青蛙可以到过的最大位置。
4.某平台新上架影片推荐度的计算方式为：由5位专业评审与5位大众评审给影片评分，评分区间为[1，10]，将专业评审均分的60%与大众评审均分的40%进行求和并取整，根据得分确定等级(分值与等级的关系如图a所示)。评委打分情况如图b所示，“A”表示专业评审，“B”表示大众评审，“A4－10”表示第4位专业评审给出10分。
分值 等级
1－2 ★
3－4 ★★
5－6 ★★★
7－8 ★★★★
9－10 ★★★★★
图a
图b
答案　(1)3　(2)①x＝line[0]　②pub＋＝t　③(socre＋1)∥2或 (socre－1)∥2＋1　(3)else 或 if x＝＝″B″ 或if x！＝″A″ 或elif x！＝″A″ 或其他等价表达式
解析　(1)专业评审均分为6，大众评审均分为7，将专业评审均分的60%与大众评审均分的40%进行求和并取整，得到3.6＋2.8＝6.4分，取整后为6，因此为3颗星。(2)①条件x＝＝″A″表示读取每条记录的第1个字符，因此x的值为line[0]。②语句score＝int(pro/5*0.6＋pub/5*0.4)计算综合得分，因此pub为大众评审，因此该值将增加1。③socre值的范围为1－10，分为1至5共5个等级，将socre的值加1，其范围为2至11，整除2后的值为1至5。或者将socre的值减去1，其范围为0至9，整除2后的值为0至4，再加上1，其值范围为1至5。
5.某小区停车场停车使用车位锁，其中私家车车位，车主可将感应器插在私家车的USB电源接口上，感应器在30～50米内发出高频信号(如图a)，当私家车靠近，车位锁自动降下解锁，车离开(20秒后)车位锁自动升起上锁。其余为收费车位，可扫描二维码控制车位锁并收费(如图b)。
收费车位计费规则如下：停车时长不到半小时按2元计费；半小时及以上则按每小时5元计费；超过整小时部分，不足半小时的时长不计费，半小时及以上则按一小时计费。该停车场当日的停车记录存储在“parking.txt”文件中，文件内容如图c所示，每一行共有4项数据，用逗号分隔，每项数据分别为进(出)场时间、车牌号、进出场状态(0表示进场，1表示出场)、车位状态(0表示私家车位，1表示收费车位)。小林编写了Python程序，从该文本文件中读取所有数据，并计算该停车场当日的总收入。请完成下列问题：
图a　私家车位
图b　收费车位
图c
答案　(1)C　(2)elif car[3]＝＝'1'
(3)①calT(dic[car[1]]，car[0])
②(T＋30)∥ 60 *price或int(T/60＋0.5)*price
解析　(1)接USB口能获取电源，并能主动发送信息，因此属于有源电子标签。(2)car[2]进出场状态，car[3]表示车位状态，当进场状态为0且为收费车牌时，在字典dic创建一个车牌号码为键，进场时间为值的键值对，只有收费车牌时才计算费用，而私家车是不用计费的。①调用函数计算停车费用。calT函数的第1个参数为入场时间，第2个参数为出场时间，入场时间在dic字典中获取，出场时间为当前记录的时间。②计算费用。超过整小时部分，不足半小时的时长不计费，半小时及以上则按一小时计费，四舍五入计算整小时数，并按每小时5元计费。
答案　(1)ZZY　(2)①x－1>＝0 and s[x]＝＝s[x－1]　②x＋1<＝len(s)－1 and s[x]＝＝s[x＋1] ③s＋＝chr(ord(″X″)＋m)　④R－L>＝2 ⑤i＝L
解析　(1)消除过程：XYYYXXZZY→XXXZZY→ZZY。(2)①从右向左查找相邻的两个位置x和他前一个位置x－1是否相同，注意边界问题。②从左向右查找相邻的两个位置x和他后一个位置x＋1是否相同，注意边界问题。③随机生成一个仅由大写字母″X″″Y″″Z″组成长度为 n 的字符串。④向左查找的最左边界为L，向右查找相同的最右边界为R，消除该字符串连续3个及以上的相同字符，则R－L＋1需大于等于3。⑤消除后，i要退回到L的位置重新判断。
2.某酒店的房间编号为1到1000，对于空余的房间的记录，采用连续空房间的起始房间编号和连续空房间数量进行记录，例如：有空房间1、2、3、6、7、9号时，记录的方法为：(1，3)，(6，2)，(9，1)，共3条记录。当有人退房时，一般出现4种情况：
·若退出房间号为4时，属于“上靠”情况，则第1条记录修改为(1，4)；
·若退出房间号为5时，属于“下靠”情况，则第1条记录修改为(5，3)；
·若退出房间号为8时，属于“上下靠”情况，则第2条、第3条记录合并，修改为(6，4)；
·若退出房间号为12时，属于“不靠”情况，则新增1条记录为(12，1)。
请回答下列问题：
(1)当已有的空房间记录为(3，5)，(9，5)，(16，3)，(30，2)，当退出房间号为8时，空房间记录修改为________。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
″″″
读入已有的空房间记录，个数为n，这些记录已按房间起始号升序排好，每条记录的房间起始号存入数组room，对应的连续空房间的个数存入数组num，下标均为0到n－1
″″″
x＝int(input(″请输入退出房间号：″))
pos＝0
while　①________：
答案　(1)(3，11)，(16，3)，(30，2) (2)①pos < n and x > room[pos]
②num[pos － 1] ＋＝ 1 ＋ num[pos] ③x＋1＝＝room[pos]　④n ＋＝ 1
解析　 本题考查数组元素的插入和删除。(1)退房前的空房间情况为3－7，9－13，8号房间退出，符合上下靠的情况，更改为3－13，16－18，30－31。(2)①找到起始空房间号room[pos]大于x房间号，为pos确保是有效索引，加上条件pos < n。②由条件“room[pos－1]＋num[pos－1]＝＝x and x＋1＝＝room[pos]”可知是属于上下靠的情况，连续空房间数量为两处数量之和再加1，合并操作会导致空房间记录总数减少，for循环是将后面空房间数据前移动。③由语句room[pos]＝x; num[pos]＋＝1可知是下靠的情况。④else表示剩下是不靠的情况，需要新增一条记录，为了保持空房间记录的有序性，需要在pos索引处插入新记录，故在插入前将n－1到pos的所有记录后移一位(for循环实现)，新增记录后，空房间记录总数增加1。
答案　(1)6　(2)①n＝len(s)　②i解析　 (1)第1个1表示代码以1开头，第2个1，表示1的个数，因此有1＋5＝6个1。(2)①对n赋值为s的长度。②不断地向后查找数字。③num表示压缩的数的个数，将这些数解压缩并存在ns中。
4.非空字符串s由互不相同的n个英文小写字母按升序排列而成，可将其中连续的多个字母缩写(如“abcd”缩写为“a～d”，“ab”写作“a～b”)。例如字符串“abcghijkmnopqsvwxyz”可缩写为“a～cg－km～qsv～z”。对于s，每当输入一个小写字母c时，若c已存在于s中，则视为从s中删掉此字母；否则将c插入到s中，并保持字母升序，输出更新s后对应的缩写字符串。请回答下列问题：
(1)如图所示，初始时字符串为“abcghijkmnopqsvwxyz”，依次输入“d”、“z”、“o”，在当前状态下，更新字符串缩写为________。
原字符串缩写为：a～cg－km－qsv～2
→请输入一个小写字母：d
更新字符串缩写为：a～dg－km～qgv～z
→请输入一个小写字母：2
更新字符串缩写为：a－dg－km～qsv～y
→请输入一个小写字母：o
更新字符串缩写为：
答案　(1)a～dg～km～np－qsv～y　(2)①c1＝s[i]　②pos解析　(1)输入“d”， “abc”更新为“a～d”，输入“z” “o”，该字符已存在，删除该字符。(2)①c1是连续子串的最左边的字母，当相邻的两个字母不相连时，更新c1。②在一个升序的子串中查找是否存在字符c，同时注意边界问题。③若c不在字符串中，将c插入到pos的位置中。
5.某商场对所有商品按价格升序排序，按相同价格划分成一段的方式，将数据分割成若干段，对每段数据进行压缩，最后存储为一个数字序列，压缩规则如下：
①使用两个整数x，y对一段连续相同的价格数据进行压缩。其中x为当前段表示的商品的价格较前一段商品的价格的增值(若为第1段，则x为第1段的价格数据)，y表示当前段的数据个数(其中0≤x，y≤1000，且均为正整数)。
②将各段价格数据压缩的结果通过“，”连接。
例如，各商品价格为“1，1，3，3，3，5，8，9，9，9，9，10”，先将连续相同的各段数据进行压缩，然后连接各段压缩的结果，如图所示。
答案　(1)2，3，3，2，2，4, 　(2)①tmp ＝ tmp * 10 ＋ int(s[i])或tmp ＝ tmp*10＋ord(s[i])－ord('0')　 ②a[k] ＝ a[k － 1]　③not f　(3)ans ＋＝ j － i 或 ans ＝ ans ＋ j － i　(4)3
解析　(1)3个2表示为2，3，2个5(增量3)表示为3，2，4个7(增量2)表示为2，4，压缩结果为2，3，3，2，2，4。(2)①变量tmp表示连续取出的数据或数据的个数，由于其值可能大于9，因此①表示取出是数字时，每次扩大10倍并加当前值计入tmp。②变量f为是否是数据的标志，值为False时表示数据，值为True时，表示数据的个数。k的初值为1，a[1]为a[0]加上第1个数据，因此a[1]存储第1个数据。同理a[k]表示连续多个数据的第1个数据。当f值为True时，还需在数组a中添加tmp－1个数据。③f设置为False和True之间的轮流变化。(3)每次找一个最小价格和最大价格，先找到一个最大价格，保证这两个价格之和要小于资金数量。若能找到，以最小价格购买第1个商品，另一个商品为最小价格之后到最大价格之间所有商品之一，方案数ans为两个价格的长度减1。(4)前两次，购买第1个商品价格为22，最大价格77，两者和小于100。第3次，购买第1个商品价格为24，最大价格76。若购买第1个商品价格为55，另外的商品加起来超过100。
1.数据在网络传输中，带宽是宝贵的资源，通过压缩传输的字符串，可以减少数据量，从而加快传输速度，节省带宽资源。现有一种字符压缩方法描述如下：对于连续的若干个相同的子串“X”会压缩为“[DX]”的形式(D是一个整数且1≤D≤99)，如字符串“ABABABAB”就压缩为“[4AB]”或者“[2[2AB]]”，类似于后面这种压缩之后再压缩的称为二重压缩。如果是“[2[2[2AB]]]”则是三重的。现给出一串压缩后的结果，并对其进行解压缩。
思路：先找出每个左括号的位置，然后从后往前枚举，找出每一个括号内要解压的子串以及要解压的次数，将子串解压后得到一个新串，重复操作，得到最终的解压缩结果。
例如：[2[2[2AB]]]→[2[2ABAB]]→[2ABABABAB]→ABABABABABABABAB。
(1)已知采用上述压缩方法得到的压缩结果是“[2Z[2DB]]”，则解压缩结果为________。
答案　(1)ZDBDBZDBDB　(2)①j＝start[i]＋1　②temp＋＝s[j]　
③ans ＋s[j＋1：]
解析　本题考查连续多个元素的遍历。(1)解压的过程为[2Z[2DB]] →[2Z[DBDB]] →[2ZDBZDB] →[ZDBZDBZDBZDB]。(2)①遍历压缩结果s，将每个″[″字符的索引位置记入start列表中。根据压缩规则，从最内层的″[″开始解压缩，因此需倒着遍历start。变量j初始值为每一层最左边位置，即″[″后面的位置。②取出每一层的数字num和子串temp，遍历到非数字时，将字符连接到temp中。③while循环结束后，s[j]的值为″]″，在重新构造字符串过程中，只是去除当前这层中的″[″和″]″，把ans连接入新的字符串s中，因此前半部分″[″前面的字符串s[：start[i]]，后半部分为″]″后的右中括号s[j＋1：]。
2.有m个人结伴旅行(m<＝9，每人用整数1～m编号)。期间既有全员参与的集体活动，也有自主参与的小团队活动。每项活动的消费由参与人平均分摊，其中一人先行垫付并记录。记录内容包括该项活动的人均消费金额(元)、参与人。每项活动的参与人用字符串表示，垫付人排在第1位。如″25134″表示2、5、1、3、4号参与该项活动，其中2号是垫付人。旅行活动结束依据所有活动的消费记录进行结算。要求输出转账明细。(编号小的付款人优先转账给编号小收款人)
(1)若有4个人参加3项活动，每项活动的参与人分别是“31”，“124”，“23”，每项活动的平均消费金额分别为50元，100元，300元， 则3号人员应还款项为________元。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
a＝['315', '523', '25134', '345', '41', '13524', '513', '451', '153']
x＝[50, 60, 30, 120, 75, 35, 95, 55, 30]
n＝len(a)
m＝5
#读取所有消费记录，显示在屏幕中，如图1所示，代码略
答案　(1)250　(2)①b[p]＋＝x[i]　②c＋＝1　③w＝b[i]＋b[j]
解析　(1) 活动1：3号垫付－50元，1号应付50元；活动2：1号垫付－200元，2、4号应付100元；活动3：2号垫付－300元， 3号应付300元，因此3号应付款项－50＋300＝250。(2)①计算每个活动第2个开始的成员应付款项，x[i]表示每个活动的平均费用。②统计需要还款人的人数c，需要还款人的应付金额大于0。
③该空与变量w相关，当w大于0时，v的值为b[i]－w，同时b[i]更新为原值减去v，b[i]是大于0的，是需要转账的，而b[j]是小于0的，是接收转账的，因此w是两者之和。
3.编排试场。每个试场有30个座位，试场号、座位号和班内序号均从1开始。对n个班级的学生编排试场，要求连续分配座位的两个学生不属于同一个班级。
分配方法：按班级人数降序排列，每次编排第1个班级的学生，完成一个学生考号的编排后，先将第1和第2个班级互换，再从第2个班级开始排序，当班级人数小于等于后面班级人数时，依次交换。如1班至3班的人数为36，35，35，第1试场座位号1的学生为1班学生，交换并排序后的班级依次为2，3，1，每班人数均为35人，座位号为2的学生是第1个班级(2班)。
(1)若1班至4班的人数分别38，36，36，36，则第1试场座位号为5的班级是________。
答案　(1)4　(2)①num[0]－＝1　②sch＋＝1 ③j解析　(1)座位1号分配后，人数为36，37，36，36；座位2号分配后，人数为37，36，36，35；座位3号分配后，人数为36，36，36(1班)，35(2班)，接着4班的学生。(2)①总是分配人数最多的班级bj[0]，因此分配后该班人数num[0]将减少一个。②每个试场有30个座位，到了第31人，试场数将增加一个。③与后面的数进行比较，如果小于或等于后面的班级人数，进行交换。
课后练习
5
重难点1　单元素遍历
重难点2　连续多个元素遍历
重难点3　双重遍历
答案　(1)2A2B或″2A2B″　(2)①s[i]＝＝g[i] ②cnt2[int(g[i])]＋＝1或cnt2[int(g[i])]＝cnt2[int(g[i])]＋1　③B＝B＋m或B＋＝m
解析　(1)数字位置均正确的有2个，数字对位置错的有两个。(2)①检测数字s[i]和猜的数字位置g[i]是否正确，变量A为数字位置正确的个数。②cnt1用于统计s中相应数字出现的次数，cnt2用于统计猜数g中相应数字出现的次数。
③数字位置均正确的没有统计在cnt1和cnt2中。若m＝0，说明该数字或者没有出现过，或者只在g或s某一个出现过，此时应不计数；若m＝1，说明这个数字在g和s中均出现了1次，但没有被统计到A中，即数字正确而位置不正确有1；若m＝2，说明数字正确而位置不正确，依次类推。
2.机器人移动路线管理。机器人在一平面内按照程序预置数据来完成移动操作(如图a所示)，规则如下：①只能水平或垂直方向移动，方向取值：上：U、下：D、左：L、右：R，不能走斜线；每次移动1－5单位距离；②从起点出发，经过若干步后，尽可能返回到起点，如不能自动返回，则计算剩余移动次数。请完成划线处代码。
图a
图b
答案　(1)pos[0]或bp　(2)[x，y]　(3)int(line[1])
(4)new_pos[1]＝pos[1]＋y*lg　(5)p＝p＋1
解析　(1)起点坐标保存在列表bp索引为零的位置。(2)功能为输入起点坐标，返回坐标[x，y]的值，返回值类型为列表。(3)函数调用代码move(pos[i]，dirt[i]，step[i]), step[i]对应参数lg，lg是一个整数。(4)new_pos[0]是横坐标，new_pos[1]是纵坐标。(5)根据returnp，可知变量p保存的是移动次数。根据p＝abs(p1－p2)∥5，如果条件语句不满足(能整除5)，函数值就直接返回p了。
3.抢红包游戏：微信抢红包游戏成为一代人的经典回忆，游戏将总金额为n的“红包”随机分配给m个玩家，红包的分配需同时满足以下规则：①所有人抢到的金额总和跟总金额n相等；②每个人至少抢到1分钱；③每个人抢到的金额随机；④每个人抢到金额大小的概率平等。
满足以上规则的最简单算法可描述为：假设总金额为n元，为使问题简单化，将总金额乘以100，此时的单位为分，使得问题在整数范围内解决。假设分发给m个人，则只需在[1，100*(n－1)]长度的范围内随机生成m－1个不重复的点，这些点将长为100*n的线段划分为m个段，每一段长度即可表示红包金额，再将每一段长度数据除以100换算为单位元输出。程序运行的结果如图所示。
输入红包金额：100
输入红包数量：5
红包金额：54.4，11.59，28.09，4.09，1.84
手气最佳：54.4
答案　①m－1　②f[n]＝True　③red ＝ i － p
解析　本题考查迭代的算法思想。 把一个长度为n*100的线段分成m段，所有线段之和为一个定值n*100，每个线段的长度代表了红包的金额，线段长度越长，金额越大。因此先产生m－1个线段，因此①处答案为m－1。每个线段的终点位置t取到，则f[t]的值为True，最后一个线段的终点必须是n，否则金额的总和不等于n，因此②处答案为f[n] ＝ True。③p是每段的开始，初值为0，下段的起点是该段的终点，因此该段的计算方法是i － p。
4.有n名同学参加春游，已知现有公用经费total元，同时每位同学又随身携带一些现金，用数组cash存储。春游地点有不同类型自行车若干辆供游客租用，每种类型的自行车按租金从高到低存储在数组info中。info[i]表示某类型自行车信息，包含租金和数量。其中，info[i][0]表示该类型自行车租金，info[i][1]表示该类型自行车数量。
每位同学优先使用自己携带的现金租车，现金不够时可使用公用经费补足费用。为方便财务管理，规定每位同学只能为自己租用自行车，且不会相互借钱。请编写程序计算这n个同学是否能够全部租到自行车。
(1)若人数n＝5，total＝80，cash＝[21，15，10，8，5]，info＝[[60，1]，[50，2]，[35，2]，[25，3]]，判断这5个同学是否都能租到自行车________(单选，填字母：A.是/B.否)。
答案　(1)B　(2)①m－n　②total－＝bike[i]－cash[j]　(3)A
解析　(1)优先安排租便宜的自行车，一共5人，需要租3辆25元的和2辆35元的，共需要25*3＋35*2＝145元，但是公用经费和每位同学自己带的钱共80＋21＋15＋10＋8＋5＝139元，不足以租5辆自行车。(2)info存储每种自行车的租金及库存，两个for循环在bike数组中添加了总共可以租的车辆m和每个车的租金。租金从高到低排列，资金能满足租借最便宜的车子就可以了。①变量i从租金最少的第m－n开始遍历。②现金cash[j]不够时可使用公用经费total补足费用。(3)可以租借时，租借的车辆从m－n到m，共有n个学生借到了自行车。
5.输入一个1－99999之间正整数金额，转换成相应的大写人民币形式，处理的方式：
1)人民币大写形式分″零壹贰叁肆伍陆柒捌玖″共10个数字和″拾佰仟万″4个单位。
2)从左向右向后处理每一位数字，同时读取该位数后面的一个数字。对当前数字分0和非0两个情况进行处理，若当前位为0，不加″拾佰仟万″等单位，如102转换为壹佰零贰元。
3)最后一位数单独处理，若为0，直接在转换后的字符串后加上“元”，否则加上对应的大写数字和文字“元”。
实现该功能的程序代码如下，请将划线处填写完整。
sn＝″零壹贰叁肆伍陆柒捌玖拾佰仟万″
s＝input(″输入一个大于0但小于10万的正整数：″)
ans＝″″
for i in ①________：
答案　①range(len(s)－1)　②elif t2 ！＝0　③t1＝int(s[－1])
解析　①最后一位数单独处理，因此先处理前面的数字。②分3种情况，当前数字0和非0，当前数字0及后面数字是0和非0。该处应填写后面数字非0的情况。③取出最后一个数字。
1.现有一个由n位大写字母组成的密码串，将其分成m段长度相同的子密码串，已知n是m的倍数。小明编写了一个Python程序，输入密码串和正确的子密码串，检查这m段子密码串的正确情况。若子密码串与正确的子密码串不完全相同，则该子密码串错误，需指出错误字符在该子密码串中的位置。例如，密码串为“ABCDEFGABBDKFGABCDEFKABCDGFG”，正确的子密码串为“ABCDEFG”，则检查结果如图a所示，程序运行界面如图b所示。
图a
图b
(1)密码串为“ACDEFACDEEABDEFACDFF”，正确的子密码串为“ACDEF”，则有________段子密码串错误。(填：阿拉伯数字)
答案　(1)3　(2)①k＝i*p　②j

解析　(1)略。(2)①m表示子密码串的个数，每个子串的长度为p，因此每个子串的开始位置为i*p。②j表示子串中的位置，从0开始，到p－1为止，共有p个字符。③将每处错误之处记录到errinfo数组中。
2.在仅包含星号*和小写字母的字符串中，可以对星号进行消除。若字符串中含有除星号和小写字母以外的其他字符，则输出无法消除；否则按如下规则进行消除：
①从左向右依次消除一个星号，直至消除所有的星号。
②一次消除时，需要同时消去星号及星号前的一个字母，若星号前无字母，则仅消除该星号。
如对字符串″pyt**ho*n″的消除过程为：
第1次消除″t*″，字符串变为″py*ho*n″第2次消除″y*″，字符串变为″pho*n″，第3次消除″o*″，字符串变为″phn″，消除完成，结果字符串为″phn″。
(1)对字符串″*fightin**g*″消除后的结果为________。
(2)编写程序实现上述消除，代码如下，请完成划线处的代码。
s＝input(″请输入一个字符串：″)
i＝0; flag＝True
while ①________：
答案　(1)″fight″　(2)①i②s[：i－1]＋s[i＋1：]　③not(″a″<＝s[i]<＝″z″)或s[i]<″a″ ors [i]>″z″或s[i]！＝″*″ and (s[i]<″a″ or s[i]>″z″)或not(s[i]＝＝″*″ or ″a″<＝s[i]<＝″z″)或其他等价答案　④i＋＝1
解析　(1)经过4次删除操作，字符串依次为″fightin**g*″、″fighti*g*″、″fightg*″和″fight″。(2)①遍历每个字符，且可以对星号进行消除，变量flag为True表示可以消除。②一次消除时，需要同时消去星号及星号前的一个字母，若星号前无字母，则仅消除该星号。
3.如果连续数字之间的差严格地在正数和负数之间交替，则该序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。对于不是摆动序列的序列，可删除其中的部分元素，剩余元素顺序不变，从而得到符合要求的摆动子序列。
例如，[1，7，4，9，2]是一个5个数字的摆动序列，因为差值[6，－3，5，－7]为正负交替出现，如图a所示。但是[2，5，8，2，5]和[2，5，3，3，6]不是摆动序列，其中[2，5，8，2，5]的前两个差值都为正数，如图b所示，而[2，5，3，3，6]的倒数第二个差值为0，如图c所示。图b中②－⑤为递增，⑤－⑧不为递减，因此②－⑤－⑧中需要删除一个数，此外图c中⑤－③为递减，③－③不为递增，因此⑤－③－③中需要删除一个元素。摆动子序列的长度均为4。
编写程序，随机生成n个元素的序列，输出该序列中删除元素后最长摆动子序列的长度。
　　　 图a　　　 　 图b　　　　 　图c
(1)若序列为[3，6，4，4，2，5，7]，则该序列删除元素后的最长摆动子序列的长度为________。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
import random
n＝int(input())
a＝[]
for i in range(①________):
答案　(1)4　(2)①n　②cnt＝1　③pre>＝0 and cur<0
解析　(1)4，其中 6－4－4－2 是一个下降区间，只能保留两个元素。2－5－7 是一个上升区间，只能保留两个元素。因此该序列的最长摆动子序列长度为 4。(2)①n，用于随机生成 n 个元素，需要将 for 循环执行 n 次；②cnt＝1，首个元素一定保留，因此 cnt 的初值为 1；③pre>＝0 and cur<0，只有当前段的单调性 cur 和上一段的单调性 pre 不同时，才可确定增加了一个“摆动”。
4.某公路由于长期没有维修，路上出现了很多个坑。为了尽快填补好这些坑，交通管理部门决定对m处地段采取交通管制。将该公路看成一条直线，坑就是直线上的坐标点，坑所在的路段需要封控管制。例如某管制路段2～4，需封控2、3、4路段。交管部门为了减少管制路段的长度，希望将这n个坑分成m段(一段可以只有一个坑)，使得这m段公路的总长度最小。请你根据n个坑的位置(位置已按照从小到大进行排序)，计算管制路段最小的总长度。代码运行效果如图所示。
路段数量：4
坑的坐标依次为：3，4，6，8，14，15，16，17，21，25，26，27，30，31，40，41，42，43
维修管制的路段依次为：
3～8
14～17
21～31
40～43
管制总长度为25
答案　(1)22　(2)①not flag[j]　②t＝i＋1 ③dis＋s[n－1]－s[t]＋1
解析　(1)若将4段分成5段，只需要其中一段中两个坑之间间隔最大的分割，在这里最大的为21～25，分割之后长度减少了3，故总长度为22。(2)①根据程序的输出结果，可知变量dis为最后的总长度，最后一个循环中变量t为每一段起始位置的下标，i为末尾位置的下标，flag[i]表示s[i]与s[i＋1]是否分割。故当输出每一段之后，dis加上每一段的举例，变量t要更新为i＋1，故②处填写t＝i＋1。当结束循环，还有最后一段的长度未加上，最后一段为s[t]～s[n－1]，则③处填写为dis＋s[n－1]－s[t]＋1。根据flag数组的含义，当flag[k]为True表示s[k]与s[k＋1]已经分割，则下一次找分割位置时，必须为未分割的部分，故①处填写not flag[j]。
5.小明编写一个 Python 程序，实现找到字符串 s1 和 s2 中相同的最长子串s，并定位子串在字符串 s2 中出现的位置，运行结果如图所示。
s1：Python
s2：thanks tnanks thanks
最长共同子串：　th
子串出现位置：
0/7/14/
(4)主程序，请在划线处填入合适的代码。
s1 ＝ input(″s1：″)
s2 ＝ input(″s2：″)
s ＝　____________
print(″最长共同子串：″， s)
pos(s，s2)
答案　(1)h　(2)①s1[i － 1] ＝＝ s2[j － 1]　②h ＝ i　(3)start ＋＝ 1　(4)longstr(s1, s2)
解析　(1)只有一个共同字符h。(2)m是一个len(s2)＋1行len(s1)＋1列的二维列表，其每个元素的初值均为0。外循环i遍历字符串s1，内循环j遍历字符串s2，当两个字符串中字符相等时，那么长度是前一次相等的基础上加1，t表示具有相同字符的最大个数，找到最大个数时，需记录其位置i。因此①表示两个位置上字符相等，其索引位置为i－1和j－1。②为最大长度的结束位置h。(3)对st的每个位置start从0开始遍历，则start不断地向后移动。(4)longstr函数，功能是找到字符中s1和s2中相同的最长子串，此处调用longstr(s1，s2)函数找出相同的最长字串赋值给变量s，故填longstr(s1，s2)。
答案　(1)①qa[i]<＝h　②i＋1，n
③qa[j]>h and abs(qa[i]－qa[j])(2)qb[i]＋qb[j]＝＝imax
解析　(1)①条件一QA值都必须大于指定参数h，若条件不满足直接枚举下一个人。②组合问题，他与后面的所有人员进行组合，保存不会重复，因此i枚举到n－2，每趟从i＋1开始枚举到n－1。③检测j人员是否满足条件1以及条件2是否满足。(2)当最大值有两个或两个以上的情况。
2.现代诗的连排格式为各句以“/”分开，例如余光中先生的《乡愁》的部分内容为：″小时候/乡愁是一枚小小的邮票/我在这头/母亲在那头/长大后/乡愁是一张窄窄的船票/我在这头/新娘在那头″，现以右起竖式形式打印这部分内容，如图所示。请回答下列问题：
(1)若按照右起竖式对“ABC/CBDA”进行打印，打印内容的第三行为________。
解析　本题考查字符串遍历、拼接等相关操作。(1)第三行为“/”分隔的两部分的第3个字符，即“ABC”中的C和“CBDA”中的D，由于是右起竖式形式，所以D在C的前面。(2)①遍历字符串poem，将“/”分隔每部分t添加到列表s中，当前字母c不是“/”，将字母c连接到变量t的后面。②找出“/”分隔每部分的最大长度，因此变量n为列表s中字符串数量len(s)。③竖排的最大行数为maxlen，变量i表示行的索引；变量j 的范围从0到n－1，因此表示列表s每个字符串，当s[j]的长度大于行索引时，就将该字符串第i个索引位置的字母连接到t的前面。
答案　(1)DC 　(2)①t ＝ t ＋ c　②n ＝ len(s)　③len(s[j]) － 1 >＝ i或len(s[j]) > i或等价表达式
3.有n列砖组成的一面砖墙，每列砖由数量不等的砖块组成，每块砖的长宽高都为1。小明为了美化这面墙，需要在这面墙中找到一块面积最大的矩形用于涂鸦。如图a所示，有6列高度依次为2、1、5、6、2、3组成的砖墙，图b和图c是其中的两种方案。编写Python程序，找出面积最大的矩形，并输出其位置和面积。
答案　(1) 10　(2)①range(i，n)　②s ＝ minh*(j－i＋1)　③maxs ＝ s
解析　本题考查根据题意建模，代码的分析理解能力。(1)由高度5和6组成的矩阵面积为10，达到最大值。(2)①从当前砖头i开始，不断地向后遍历。②矩形面积取决于宽度和高度，变量i，j表示宽度的开始和结束位置，向后查找构成矩形的最小高度minh，根据宽度j－i＋1计算对应的面积；③更新最大面积maxs的值为s。
电影名称 搞笑镜头 拥抱镜头 打斗镜头 影片类型
宝贝当家 45 2 9 喜剧片
唐人街探案 23 3 17 喜剧片
我的特工爷爷 6 4 21 动作片
…… …… …… …… ……
泰坦尼克号 9 39 8 爱情片
罗马假日 9 38 2 爱情片
新步步惊心 8 34 17 爱情片
图a
电影名称 搞笑镜头 拥抱镜头 打斗镜头 影片类型
美人鱼 19 18 5 ？
图b
距离最近的前5部影片为：
唐人街探案19.62，罗马假日 22.56，新步步惊心 22.83, 泰坦尼克号 23.45，我的特工爷爷 24.92
图c
请回答下列问题：
(1)与《美人鱼》距离最近的前5部影片如图c所示，则该影片属于________(单选，填字母：A.喜剧片 /B.动作片 /C.爱情片)。
答案　(1)C　(2)1　(3)①data[i][j]－x[j]或x[j]－data[i][j]　②dic[data[p][4]]＋＝1　③k－＝1
解析　(1)距离最近的5部影片中，喜剧片1部，爱情片3部，动作片1部，因此该影片类型为爱情片。(2)在存储标记为False的位置中，查找最小值的索引，43，33，65三个数中最小值索引为1。(3)①遍历所有的样本数据data，计算出“美人鱼”与样本中所有影片的距离。data[i][1]、data[i][2]、data[i][3]分别表示样本数据中搞笑镜头、打斗镜头、拥抱镜头的值，用变量j表示这些下标，计算与x[j]的平方差的和。②调用mvmin函数计算最小距离的索引p，即对应的样本的索引，在数组元素data[p][4]中存储的是该影片的类型，需要对该类型的数量增加1。③处理下一个样本数据。
5.某校图书馆提供 3 类自习室，A 类最多容纳 2 人，B 类最多容纳 4 人，C 类最多容纳 8 人，以 1 小时为单位进行预约，每人每天只能预约一次，每次预约仅限个人，规定预约时间结束之前必须离开。图书馆每天 6 点开馆，22 点闭馆。编写程序，输入某自习室号牌，根据已预约情况，输出该自习室还能被预约的时间段。例：读取“A102”已预约情况[[6，11], [15，18], [8，12], [15，22]]，其中“A102”表示为 A 类 102 号自习室，[6，11]表示某个人预约 6：00 开始，11：00 前必须离开，时间占用如图所示，则该自习室还能预约的时间段为[[6，8]，[11，15]，[18，22]]。请回答下列问题：
答案　(1)[[6，8], [11，22]]　(2)①period[1]　②ringt＝i或right＋＝1　③i＋＝1或i＝i＋1
解析　(1)[6，11]表示某个人预约6：00开始，11：00前必须离开，因此6－7点还可以容纳2人，8－10点已经约了4人，11点还可以容纳2人，12－22点还可以容纳4人。(2)①遍历各个预约时间段，将各个预约时刻记录到预约的人数bucket数组中，period表示每个预约时间段，period[0]是预约的开始时间，period[1]是预约的离开时间。②条件bucket[i]6.上城小学将在本学期开展趣味运动会，一(10)班的班主任邀请你为他们设计一个Python程序，用于挑选参加集体项目的选手。挑选规则为：当班级有足够候选人员时，进行随机挑选，并输出人员名单；若无足够人员时，提示“无足够候选人员参加比赛！”，并规定每个学生最多参加一个集体项目。程序要求用户按照规范输入比赛项目及相关人员要求，例如输入“投篮：8，2”即篮球项目要求男生8人，女生2人。该程序的运行效果如图所示：
请输入比赛项目及相关人员要求：跳绳：5，5，
赶猪：15，15；投篮：8，2
跳绳项目：
男：艾震宇　蔡温淼　叶埕奇　王子硕
女：王晓清　黄鑫橼　陈佳妮　陈昱彤　陈奕臻
赶猪项目：
无足够侯选人员参加比赛！
投篮项目：
男：陈展骢　李俊翰　张子俊　刘泓成　胡海伟　王子涵　叶赛特　伍越
女：贾熙　钱梓涵
(1)实现挑选集体项目选手的Python代码如下，程序中用到的列表函数与方法如表所示，请在划线处填入合适代码。
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop(i) 将列表w末尾下标为i的元素赋值给x，并将其从w中删除
解析　本题考查列表的方法实现。(1)①自定义函数player的功能是输出列表前n个元素，并删除这些元素。表中所示x＝w.pop(i)将列表w末尾下标为i的元素赋值给x，并将其从w中删除，因此下标i的值为0。②ctemp数组存储男生和女生名单，因此需遍历c数组的每个元素p，并根据p[0]的值进行相应的处理。③分别处理男生和女生的情况，因此需重复2次。(2)player函数是处理一个一维数组，即分别处理男生和女生的名单。
答案　(1)①xm＝x.pop(0)　②p
③range(len(ctemp))或range(2)
(2)ctemp[i]＝player(ctemp[i]，sj[t][i])
7.某校举行趣味运动赛，共有n个比赛项目，每班派n位学生参加，每位同学分别参加一个项目。某班有n位选手报名参加比赛，现需要依据他们平时练习中各个项目的平均得分，找出最佳参赛组合，查找规则为各项目得分总和最大，例如：图a所示的数据中，最佳参赛组合是“唐昌新：跳绳，胡鹏：飞镖，杨胜超：颠球，陈伟：套圈”。完成下划线的代码。
图a
最佳参赛组合：
唐昌新　跳绳
胡鹏　 飞镖
杨胜超 　颠球
陈伟　 套圈
图b
答案　①f[i]＋＝1　②k∥n　③a[j][s[j]＋1]　④max＝sum
解析　①数组f是一个桶，f[i]用于记录i的数组，遍历到i，就对f[i]加1操作，当f[i]大于1，说明有重复。②共有n个比赛项目，每班派n位学生参加，每位同学分别参加一个项目。参加为1，不参加为0，可以看成是n位二进制数，每一位代表一位同学，有两种可能性。因此有n**n种可能性，将k转换成对应的二进制数。③将n位选手各项成绩进行累加。④更新最大值为sum。
8.某影厅共12排，每排10座。座位编号以排号＋座号来命名，如第10排3座，编号命名为103。某一时刻，该影厅的最佳观影区为方框内的座位如图所示，即第5排3座～第10排8座的矩形位置。0表示该座位可选，非0表示已售(1表示系统推荐，2表示手工选择)
座位推荐算法：
(Ⅰ)只推荐最佳观影区的座位，并且所有座位号要连号。
(Ⅱ)优先选择最佳观影区内最中间的位置(若空位数为偶，则选择中间靠左)，若中间位置相同，则以靠前位置为佳。
(Ⅲ)若在最佳观影区内未找到可以推荐的座位时，系统将提示手工选择。
(1)如图所示的座位中，若要购买2张票，则推荐的排号是________
(2)实现上述功能的Python程序如下，请在划线处填入合适的代码。
#产生一个12行10列的二维数组，并随机产生座位情况，代码略
k＝int(input(″请输入购票数：″))
kwz＝0；wz＝[]
m＝12；n＝10
for i in range(4，10)：　#寻找中间空的座位，并把座位号保存到数组wz中。
答案　(1)6　(2)①kwz＋＝1
②wz[p＋k－1]－wz[p] ＝＝ k－1
③ s＝p
解析　本题考查数组的遍历。按规则，第5排选择第4、5列，第6排选择第5、6列，第6排更靠中间。(2)①寻找中间空的座位，并把座位号保存到数组wz中，从条件p＋k－19.某网约巴士，车上最初有12个空座位，从起点站向终点站行驶，不允许掉头或改变方向，现有新的订单，请判断其是否能预约成功。请回答下列问题：
(1)若网约巴士已预约成功的数据为：[2，1，5]，[1，3，7]，[3，2，8]，[2，4，7]，[3，5，10]，其中每个元素有3个数据项，分别表示预约人数、出发站点和到达站点，当前接到订单[4，5，8]，________(选填：能/不能)预约成功。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
#数组trips存储预约信息，trips[i]＝[num，start，end]表示第i个预约信息有num个乘客，出发站点为start，到达站点为end，站点编号为1～10。
total＝12　#空座位总数
stations＝10　#站点总数
diff＝[0]*(stations＋1)
count＝[0]*(stations)　#存储站点上下车后的乘客人数
答案　(1)不能　(2)①diff[i[1]]＋＝i[0]　②1，j＋1或0，j＋1或j＋1或j，0，－1，或j，－1，－1　③count[i]＋num>total或num>total－count[i]
解析　(1)用如表格的第2－6行表示每个订单每个站台的变化人数，最后一行表示该车从该站台开出时的总人数。
站台 1 2 3 4 5 6 7 8 9 10
单1 2 2 2 2 －2 　 　 　 　 　
单2 　 　 1 1 1 1 －1 　 　 　
单3 　 3 3 3 3 3 3 　 　 　
单4 　 　 　 2 2 2 －2 　 　 　
单5 　 　 　 　 3 3 3 3 3 －3
人数 2 5 6 8 7 9 3 3 3 －3
站台6当前有9个，加上4人超出12人。
(2)①遍历预约信息trips，有num个乘客，出发站点为start，到达站点为end，因此start站要加上num个乘客。②数组diff存储每站的变化人数，因此每站实际人数统计0至j站的变化人数的累加和。③车上最初有total个座位，当前站总人数为与当前站将要上车人数num之和不能超出座位总数total。

展开更多......

收起↑