资源简介

课时7　枚举算法思想
【学业要求】
知识点 学业水平等级
1.掌握解析算法、枚举算法的算法特征,并会用计算机程序实现这两种算法。 4
2.理解迭代算法的思想,应用迭代算法处理实际的问题。 4
　　本节课的目的是提取浙江选考真题的填空题(第13、14和15题)中关于枚举算法思想的部分,围绕这个算法思想,并加以练习。枚举算法是计算机解决问题的主要方法,在第13、14和第15题中,往往要去枚举某个数据集,找到其中符合条件的情况,并进行统计和计算。如2023年6月遍历数组的各个元素,输出空货位数及还可以放置A型箱子的最多数量。2024年6月浙江选考遍历数组d的红灯和绿灯的状态值进行统计。在第15题的也有体现,如2023年6月浙江选考枚举有依赖关系的个数1st列表,进行链表节点的连接,同时为前驱节点的作一个标记为1。
1.(2024年6月浙江选考)某监控设备可定时采集红绿信号灯状态数据,数据格式记为[a,b],其中a、b分别为红灯和绿灯的状态值,0表示灯灭,1表示灯亮,如[0,1]表示红灯灭、绿灯亮。现要编写程序,每隔1秒采集并检测信号灯是否存在如下异常状态:第一类,红绿灯同亮或同灭;第二类,红灯或绿灯超时,即保持同一状态时长大于上限值(如300秒)。检测到异常状态就发送相应信息。请回答下列问题:
(1)若检测到“红绿灯同亮”异常,则采集到的数据是　　　　(单选,填字母)。
A.[0,0] B.[0,1]
C.[1,0] D.[1,1]
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
tlimit=300　#设置信号灯保持同一状态时长上限值
pre=[-1,-1]
t=[0,0]　#t[0]、t[1]分别记录红灯、绿灯保持同一状态的时长
while True:
　# 收一次采集到的状态数据,存入d,代码略
　if　①　　　　:
　　　if d[0]==1:
　　　　#发送“红绿灯同亮”信息,代码略
　　　else:
　　　　#发送“红绿灯同灭”信息,代码略
　for i in ②　　　　:
　　　if d[i] == pre[i]:
　　　　t[i]+= 1
　　　　if ③　　　　:
　　　　　　if i==0:
　　　　　　　#发送“红灯超时”信息,代码略
　　　　　　else:
　　　　　　　#发送“绿灯超时”信息,代码略
　　　else:
　　　　t[i]=1
　pre=d
　#延时1秒,代码略
答案　(1)D　(2)①d[0]==d[1] 　②range
(2)或range(len(d))　③t[i]>tlimit
解析　本题考查利用算法程序解决生活实际问题。 (1)1表示灯亮,两个灯同亮,值均为1。(2)①第一类,红绿灯同亮或同灭,表示采集的数据d中两个元素d[0]和d[1]的值相等。②从条件d[i] == pre[i]来看,变量i表示0或1,依次表示红灯或绿灯的索引位置。③t[0]、t[1]分别记录红灯、绿灯保持同一状态的时长,第二类,红灯或绿灯超时,即保持同一状态时长大于上限值(如300秒),当某个灯i的持续时间t[i]大于上限值tlimit时,出现超时信息。
2.(2023年6月浙江选考)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任务A依赖于任务B。
图b
实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
'''
工程包含的任务数存入变量n,任务间的依赖关系存入lst列表,lst[0]包含3项,任务lst[i][0]依赖于任务lst[i][l],lst[i][2]存放保留/删除标记,任务数据存入task列表task[i]包含2项,task[i][0]为完成任务所需天数,task[i][1]的初值为-1,代码略。
'''
pr=[0]*n
m=erase(lst)　#调用erase函数删除列表lst标记为“F”的依赖关系,返回依赖关系个数
for i in 　　　　:
　 task[lst[i][1]][1]=lst[i][0]
　 pr[lst[i][0]]=1
#计算各个任务是最晚开始时间,代码略。
答案　range(m)
解析　本题考查枚举算法思想。调用erase函数删除列表lst标记为“F”的依赖关系,返回依赖关系的个数,枚举有依赖关系的个数lst列表,进行链表节点的连接,同时为前驱节点的作一个标记为1,表示其前驱节点是有后继的,不是头节点。
1.遍历指访问集合中每一个数据,并且访问　　　　次。枚举指在遍历过程中,对访问的数据进行求和、计数或求最值的过程。
2.遍历集合中(如a=[3,6,4,2])的数据有两种方式,一是按　　　　遍历,如for i in a,那么循环变量i就是集合中3等数字;二是按　　　　遍历,如for i in range(len(a),那么a[i]才能表示集合中3等数字。
3.按位置遍历集合中数据时,位置i中数据可以是一个数据,也可以是一个用　　　　表示的多个数据。
4.按位置遍历时,循环变量i往往出现在　　　　里面,从而可以理解遍历的集合名称。
自我校对:1.一　2.值　位置　3.列表　4.中括号
【典例1】 某监测设备可定时采集甲、乙两通道的排放数据,数据格式记为[a,b]。数据异常分两种情况。其一,当a超过500,b也超过500时;其二,当a与b的和超过1200时。
编写程序,每隔1秒采集排放数据,当排放数据持续异常的时长超过上限t1时,打开阀门。阀门开启的时长固定为t2秒,t2秒后阀门将自动关闭,并重新开始监测。请回答下列问题:
(1)下列数据属于数据异常的是　　　　(单选,填字母)。
A.[985,211] B.[500,500]
C.[666,888] D.[0,1000]
(2)实现上述功能的部分Python程序段如下,请在划线处填入合适的代码。
t1=10　#设置持续异常的时长上限值
t2=3　#设置阀门每次开启的时长
switch=False　#用True、False分别表示阀门开、关状态
time1,time2=0,t2
while True:
　#接收一次采集到的排放数据,存入d,代码略
　if switch:
　　　①　　　
　　　if time2==0:
　　　　switch=False
　　　　time1=0
　else:
　　　if d[0]>500 and d[1]>500 or d[0]+d[1]>1200:
　　　　time1+=1
　　　if ②　　　　:
　　　　switch=True
　　　　time2=t2
　　　　#执行“打开阀门”操作,代码略
　　 else:
　　　　　③　　　
　#延时1秒,代码略
思维点拨
明考向 本题考查枚举算法思想
精点拨 (1)C选项当a与b的和超过1200时,属于数据异常。(2)①阀门开启的时长固定为t2秒,t2秒后阀门将自动关闭。打开阀门时,time2的值为t2,每次减少1,当time2的值为0时,关闭阀门,重新计时。②当排放数据持续异常的时长time1超过上限t1时,打开阀门。③当排放数据不持续异常时,将重新计时。
答案　(1)C　(2)①time2-=1　②time1>t1　③time1=0
【变式1】 某密码强度判断程序功能如下:将密码字符分为大写字母、小写字母、数字字符以及其他符号四种类型。输入一串密码字符,如果该字符串的长度小于8,则输出“密码长度不符合要求!”;若该字符串包含三种字符及以上,则输出“强度:强”;若该字符串包含两种字符,则输出“强度:中”;若该字符串仅包含一种字符,则输出“强度:弱”。
(1)请在划线处填入合适的代码。
r=[0]*4;sum=0
s=input("输入密码:")
①　　　
if n<8:
　print("密码长度不符合要求!");
else:
　 for ②　　　　:
　　　ch=s[i]
　　　if ch>="a" and ch<="z":
　　　　 r[0]=1
　　　elif ch>="A" and ch<="Z":
　　　 　r[1]=1
　　　 ③　　　　:
　　　　 r[2]=1
　　　else:
　　　 　r[3]=1
　　　sum=r[0]+r[1]+r[2]+r[3]
　　　if sum>=3:
　　　　 print("强度:强")
　　　elif ④　　　　:
　　　 　print("强度:中")
　　　else:
　　　　 print("强度:弱")
(2)若输入的密码字符串为“Assd 237”,则输出的结果为　　　　。
(3)若删除加框处语句,则②处应填写的语句是　　　　。
答案　(1)①n=len(s)　②i in range(len(s)) 　
③elif "0"<=ch<="9"　④sum==2
(2)强度:强　(3)ch in s
解析　本题考查枚举算法思想。(1)①在条件n<8中,没有对n进行定义和初始化。②语句为ch=s[i],变量i没有定义,因此循环变量为i,是在字符串中位置。③第3种情况是判断是否是数字。④当sum的值为2时,有2种类别,强度为中。(2)字符串长度等于8且有4种类型的字符,属于强度为强的情况。(3)若删除加框处语句,则循环变量应为ch,是对字符串s中每个元素进行遍历。
【典例2】 某数据分析系统的功能为:采集实时数据val,生成最近连续5次数据的均值ave,如图a所示,绘制如图b所示的折线图,并发出数据异常信号:
异常一,上穿异常,虚线(数据val)上穿实线(数据ave),如图b中时刻5→6;
异常二,下穿异常,虚线(数据val)下穿实线(数据ave),如图b中时刻7→8。
time val ave
1 5.05
2 5.10
3 5.05
4 5.10
5 5.00 5.06
6 5.20 5.09
7 5.25 5.12
8 5.00 5.11
图a
图b
请回答下列问题。
(1)关于异常信号,下列说法正确的是　　　　 (单选,填字母)。
A.系统可能连续发出2个相同的异常信号
B.系统不可能连续发出2个相同的异常信号
(2)实现上述功能的部分Python代码如下,请在划线处填入合适的代码。
data=[]
while True:
　#接收实时数据val ,代码略
　data.append(val)
　if len(data)>=6:
　　sum=0
　　for i in①　　　　:
　　　　sum+=i
　　　　pre_ave=(sum - data[-1])/5　#上一个近5次均值
　　　　ave=②　　　　　#近5次均值
　　if data[-1]>ave:
　　　　#发出异常一信号,代码略
　　#判断并发出异常二信号,代码略
#绘制折线图,代码略
(3)程序中加框处代码有错,请改正。
思维点拨
明考向 本题考查枚举算法思想
精点拨 (1)要产生上穿异常,本次val的值要大于本次ave值,而上次val值要小于上次ave的值。要产生下穿异常,则本次val的值要小于本次ave值,而上次val值要大于上次ave的值。因此系统不可能连续发出2个相同的异常信号。(2)①从语句sum+=i来看,sum为6个数字之和,因此该集合中表示的最近6次的值。②近5次均值应为sum减去最1个数据的值之后求平均。(3)需要上一次的实线值小于上一次的平均值,即data[-2]ave
答案　(1)B　(2)①data[-6:]　②(sum-data[-6])/5或(sum-data[len(data)-6])/5
(3)data[-1]>ave and data[-2]【变式2】 某公司有编号为0至n-1的n个会议室。每个预定的会议包含开始时间和结束时间,都会在未占用且编号较小的会议室举办,如果没有可用的会议室,会议将会延期到有空闲的会议室为止,并且优先提供给原开始时间最早的会议。编写Python程序,求举办最多次会议的会议室。请回答下列问题:
(1)若会议室n为2,会议如图所示,编号为1(即第2个)会议室承办的会议次数为　　　　。
会议序号 开始时间 结束时间
会议1 0 30
会议2 5 10
会议3 15 20
会议4 17 35
(2)请完成下列划线处的代码。
#读取会议室数量存存储到变量n。
#读取会议到列表meetings中,每个元素包含会议开始时间和结束时间,并按开始时间排序,代码略。
cnt=[0]*n
tim=[0]*n　#存储当前每个会议室承办会议的结束时间
for m in meetings:
　best=0;i=0
　while i 　　if tim[i]<=m[0]:
　　　　　①　　　
　　　　　tim[i]=m[1]
　　　　　break
　　if tim[i]　　i+=1
　if i==n:
　　cnt[best]+=1
　　②　　　
ans=0
for i in range(1,n):
　if ③　　　　:
　　ans=i
print("承办会议最多的会议室编号为:",ans)
答案　(1)3　(2)①cnt[i]+=1　②tim[best]+=m[1]-m[0]　③cnt[ans]解析　(1)会议室1承办会议1,30结束,会议室2承办会议2,10结束,承办会议3,20结束,承办会议4,38结束,因此会议室承办3个会议。(2)①遍历每个会议,tim存储当前每个会议室承办会议的结束时间,若某个会议室结束时间小于等于当前会议开始时间,表示该会议室可以承办该会议,该会议室的承办次数增加1次。②best记录了最早结束会议的会议室索引,若条件i==n成立,表示没有找到结束时间早于当前会议开始的会议室,那么让结束会议最早的会议室承办,该会议室会议结束时间更新为上次会议结束时间和本次会议所需时间之和(当前会议结束时间减去开始时间)。③cnt记录每个会议室承办会议的次数,ans表示承办会议最多的索引(编号),遍历所有会议室,若当前会议室承办会议次数cnt[i]大于cnt[ans],将承办会议最多的会议室编号更新为ans。
　　枚举算法是一种简单而直接的算法策略,通过将问题的所有可能解一一列举出来,并逐一检查每个解是否符合问题的要求,从而找到问题的解。这种算法通常用于解决规模较小、解空间有限的问题,因为它在解空间非常大时可能会变得非常低效,甚至不可行。在解题过程中,可以从循环变量出现的位置来确定枚举的对象,有按值枚举和按位置枚举两种方式。若循环变量出现在方括号中,表示是某个列表或者列表元素的下标,是典型的按位置枚举。枚举的对象可以是一个值,也可以是包含多个值的列表。
1.中华人民共和国居民身份证号码共18位,其中前17位为数字本体码,第18位为校验码。作为尾号的校验码,是按统一的公式计算出来的,校验码的计算方法为:
(1)将身份证前17位分别乘以不同的系数,系数依次为7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2;
(2)将这17位数字和系数相乘的结果相加;
(3)求用上述相加的和除以11的余数;
(4)余数只可能有0,1,2…9,10共11个数字,分别对应校验码1,0,X,9,8,7,6,5,4,3,2。
例如:身份证号34052419800101001X,计算3*7+4*9+0*10+5*5+…+1*2=189,用189除以11得出余数2,对应的校验码是X。
编写Python程序,判断输入的身份证号码的校验码是否正确,正确输出“Yes”,否则输出“No”,请在划线处填入合适代码。
def judge(s):
　v=[7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2]
#系数
　m='10X98765432'　#余数对应的校验码
　①　　　
　if n!=18:
　　　return False
　res=0
　for i in range(n-1):
　　　②　　　
　res=res%11
　code=m[res]
　if ③　　　　:
　　　return True
　else:
　　　return False
s=input(输入身份证号码:')
if ④　　　　:
　　print('Yes')
else:
　　print('No')
答案　①n=len(s)　②res+=int(s[i])*v[i]
③code==s[-1]　④judge(s)==True或judge(s)
解析　自定义函数judge用于判断输入身份证号码s是否合法,若合法返回True。①处下方语句if n!=18,因此该处肯定与n有关。②将这17位数字和系数相乘的结果相加并存储到res中。③执行语句res=res%11后,求用上述相加的和除以11的余数;code对应校验码,若计算出来的校验码与身份证号码是最后一位相同,则表示身份证有效。④调用自定义函数并判断输入的号码是否合法。
2.有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)
答案　(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。
3.某公司举办抽奖活动,设有一、二、三等奖。每张奖券印有3个互不相同的数字,每次在兑奖前公布中奖号码,兑奖时不考虑中奖数字的先后顺序,兑奖规则如下表所示。编程统计奖券获得的总奖金。
奖项 一等奖 二等奖 三等奖
兑奖条件 3个数字均匹配 2个数字匹配 1个数字匹配
奖金 500元 200元 100元
(1)某次中奖号码为3,1,8,则号码为1,6,3的奖券可以获得奖金　　　　元。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#输入中奖号码,依次存储到列表元素win[0]至win[2]中,代码略
rew=[0,100,200,500]
①　　　　
n=int(input("输入奖券数量:"))
for i in ②　　　　　:
　cnt=0
　#输入奖券的号码,依次存储到列表元素tic[0]至tic[2]中,代码略。
　for j in range(3):
　　　if tic[j] in win:
　　　　　cnt+=1
　mon=③　　　　
print("总奖金金额为:",mon)
答案　(1)200　(2)①mon=0　②range(n)
③mon+rew[cnt]
解析　(1)匹配到1和3共两个数字,因此获二等奖。(2)①对总奖金金额mon赋初值0。②共有n张奖券,需重复n次。③cnt为匹配到的数字数量,则rew[cnt]为每张奖券的中奖金额。对这些金额进行累加求和。
4.服务器接收到的数据中包含一个状态信息码,状态信息码由3个数字组成,第1个为智能终端编号,第2个、第3个为温度、湿度状态(0为偏低、1为正常、2为偏高),如“101”表示1号终端的温度偏低、湿度正常。如果某终端的状态连续异常称为一个异常段,异常段内的状态个数称为长度,服务器将接收到的所有状态信息码按接收时间顺序保存到列表res中,如["111","012","211","901","100","211",……],编写程序对res进行处理,要求统计出各智能终端异常段长度超过阈值m的次数,请在划线处填入正确代码。
#数据保存到res,阈值保存到m,代码略
size=[0]*10
c=[0]*10
for code in res:
　①　　　　
　if code[1:]!="11":
　　 　size[k]+=1
　else:
　　 　if size[k]>m:
　　　　　②　　　　
　　 　size[k]=0
for i in range(10):
　if size[i]>m:
　　 　③　　　　
for i in range(10):
　print("编号为"+str(i)+"的智能终端异常段长度超过阈值次数:"+str(c[i]))
答案　①k=int(code[0])　②c[k]+=1
③c[i]+=1
解析　①一共有10个终端,在code的第1个状态码中获取终端号码k,由于k为作size数组的下标,因此需转换成数字型。②条件code[1:]!="11"成立,表示k终端状态不正常,该终端的不正常次数size[k]加1,当状态正常时,将异常段长度与阈值m比较,如果大于m,则该终端的c[k]的值将增加1。③若某个终端最后一次的状态不正常,仅对次数size[k]增加了1,没有与m进行比较。对所有终端这种情况进行判断,若第i个终端最后一次不正常且次数超过m,则c[i]的值增加1。
5.某酒店的房间编号为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])
答案　(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.哥德巴赫猜想是近代三大数学难题之一,即任一大于2的偶数,都可表示成两个素数之和。采用Python验证100以内哥德巴赫猜想的正确性。
import math
def isprime(num):
　i=2
　while i<=int(math.sqrt(num)):
　　　if num % i==0:
　　　　　return False
　　　i+=1
　return True
n=6
while n<=100:
　　for j in range(3,int(n/2)):
　　　if　　　　　　　:
　　　　　print (n,"=",j,"+",n-j)
　　n+=2
则划线处的代码为　　　　　　　　。
答案　isprime(j) and isprime(n-j)
解析　本题考查自定义函数。自定义isprime的功能是判断num是否是素数。验证100以内哥德巴赫猜想的正确性,由于4=2+2,正确;n从6开始的偶数,因此n表示递增2。将n分解为j和n-j两个数,如果这两个数同时为素数,则验证成功。
2.输出2至100之间的所有素数。算法:采用一个flag数组来标记100以内含100的数是否是素数。循环变量i从2开始遍历,如果是素数,再将区间内所有i的倍数标记为False,依此类推,直到输出区间内所有素数。
编写的程序代码如下,请将空白处填写完整。
flag=[True]*101
for x in ①　　　　　:
　if flag[x]:
　　print(x,end=",")
　　t=2
　　while ②　　　　　:
　　　　　③　　　　　
　　　　　t+=1
答案　①range(2,101)　②t*x<101
③flag[t*x]=False
解析　①从2开始遍历到100,判断并输出该区间的素数。②t表示x的倍数,从2倍开始,不断增加,直到t*x的值超出100。③将该数的倍数标记为False。
3.某字符串s是由一个原始字符串反复重叠形成的。例如字符串"abcababcababcab"的是由原始字符串"abcab"重叠而成。输出最长的原始字符串。检测的算法:原始字符串从1个字母开始枚举,将该字符串划分成与原始字符串若干段,若划分的字符串每一段与第一段相同,则认为该字符串是由这段字符重叠而成。若枚举的最大长度为字符串s的一半时,则不可能有原始子串叠加而成。请完成下列空白处代码。
s="abcababcababcababcababcab"
n=len(s);ans=""
for i in　①　　　　:#变量i表示子串的长度
　if n%i==0 :
　　for j in　②　　　　:#在字符串s中依次取出长度为i的子串
　　　　if s[:i]!=s[j:j+i]:
　　　　　　break
　　else:
　　　　③　　　
print("原始串是:"+ans)
答案　①range(1,n∥2+1)　②range(i,n,i)
③ans= s[:i]
解析　字符串s长度肯定是原始字符串长度i的整数倍。①原始字符串的长度最小为1,最大为s字符串长度的一半。②前面第一段为原始子串,从索引i开始,每隔长度i取出一个子串,如果取出的子串与原始子串不相同,表示该原始子串不符合要求,结束长度为i子串的遍历。③当整个字符串s全部遍历完成后,所有的子串s[j:j+i]均与原始子串s[:i]相等,没有执行break,则要执行for循环的else部分。
4.给定n个形如[L,R]的区间,合并所有存在交集的区间(若两个区间在端点处相交,也认定存在交集),如区间[1,3]和[2,6]可以合并为区间[1,6]。编写程序,输出合并后的区间个数。#读入包含多个区间的data数组,并将各个区间按左区间升序,若左区间相等按右区间升序,代码略,类似data=[[1,2],[2,4],[3,6],[5,6],[7,8],[7,9]]
newdata=[]
left=data[0][0];right=data[0][1]
for i in　① 　　　　:
　if data[i][0]<=right:
　　　if ②　　　　:
　　　　right=data[i][1]
　else:
　　　newdata.append([left,right])
　　　left=data[i][0]
　　　right=data[i][1]
③　　　
print(newdata)
答案　①range(1,len(data))　②data[i][1]>right
③newdata.append([left,right])
解析　①left和right表示合并新区间的左右边界,默认值为第1个区间的左右边界,因此从第2个区间开始遍历。②如果遍历到区间的左边界小于等于right,表示与新区间有交集。可能是新区间的子集,包含在新区间的内部,也可能右边界比right大,此时需更新右边界。③遍历到最后一个区间时,该区间可能与前面一个区间有交集,此时执行if部分,没有添加到newdata;也可能单独成一个新区间,语句newdata.append([left,right])只是将前面的区间添加进去,语句left=data[i][0]、right=data[i][1]定义新区间的左右边界,但没有添加到newdata。
5.小陈在学习历史时,从公元1000年至今,发现有的日期特别的“优美”,如1010年01年01日,2021年12月02日,小陈把它们称为“对称日”。为了寻找指定年份中的“对称日”,小陈编写了如下的Python程序,程序运行结果如图所示,请在划线处填入合适的代码。
请输入开始年份:2000 请输入结束年份:2023 20200202 20211202
def check(k):
　check=True
　y=int(k[0:4]); m=int(k[4:6])
　d=int(k[6:8])
　flag=0
　if m<1 or m>12:
　　　check=False
　if (y%4==0 and y %100!=0 or y%400==0) and ①　　　　:#判断闰年时的相应情况
　　　flag=1
　if　②　　　　:
　　　check=False
　③　　　
ks=int(input("请输入开始年份:"))
js=int(input("请输入结束年份:"))
lst=[31,28,31,30,31,30,31,31,30,31,30,31]
for i in range(ks,js+1):
　k1=str(i)
　k1=k1+ k1[::-1]
　if check(k1)==True:
　　　print(k1)
答案　①m==2　②check==True and d>lst[m-1]+flag或check==True and(d<1 or d>lst[m-1]+flag)　③return check
解析　 遍历开始年份至结束年份,先创建一个对称的日期,再调用函数去检测这个日期是否合理。①check是日期是否合理的标志,flag表示闰年的2月比其他年份多1天,如果是其值为1,判断是否是闰年外,还需加一个条件是否是2月份。②在日期合理,且check是真的前提下,如输入的d大于当月的天数,则输入的d无效。③返回是否效的结果check。
6.某快递分拣站有4个分拣机器人(编号0~3),根据包裹重量分为优先包裹和普通包裹,两种包裹的分拣规则如下:
①重量≥10 kg的包裹为优先包裹,优先分配:
·先选择当前空闲的机器人(同空闲状态则编号小优先)
·若无空闲机器人,则选当前任务剩余时间最短的机器人(同剩余时间则编号小优先)
②重量<10 kg的包裹为普通包裹,按机器人累计分拣件数分配,选择累计分拣件数最少的机器人(同分拣件数则编号小优先)
(1)某时刻状态:
机器人0:空闲(累计200件);
机器人1:忙碌,剩余8分钟(累计150件);
机器人2:忙碌,剩余5分钟(累计150件);
机器人3:忙碌,剩余8分钟(累计220件)。
此时到达一个包裹,下列选项包裹重量和分配的机器人相匹配的是　　　　(单选,填字母)。
A.3 kg,机器人0 B.5 kg,机器人1
C.10 kg,机器人2 D.15 kg,机器人3
(2)以下Python代码段实现优先包裹的分配:
#[False,0,200]分别表示机器人状态(空闲),当前任务剩余时间,累计分拣件数
robots=[[False,0,200],[True,5,150],[True,8,150],[True,3,220]]
def assign_urgent():
　for i in range(4):
　　　if ①　　　　　:
　　　　#更新机器人状态和累计分拣件数,代码略
　　　　return i　#直接分配空闲机器人
　k=0
　for i in range(1,4):
　　　if ②　　　　　:
　　　　k=i
　　　③　　　　　　#更新累计分拣件数
　return k
答案　(1)B　(2)①not robots[i][0]或robots[i][0]==False　②robots[i][1]③robots[k][2]+=1
解析　(1)A选项包裹重量为3 kg,则分配给累计分拣数最少的机器人1;B选项包裹重量为5 kg,则分配给累计分拣数最少的机器人1;C选项包裹重量为10 kg,则分配给当前空闲机器人0;D选项包裹重量为15 kg,则分配给当前空闲机器人0。(2)①若当前有空闲机器人时(状态为False时),将包裹分配给空闲机器人。②a若不存在空闲机器人,则需要依次遍历每个机器人的当前任务剩余时间,找到最小值k。③此时k为当前选中的机器人,则要让其分拣次数robots[k][2]加1。
7.新能源汽车电池在使用中会经历多次充放电,设计算法模拟电池充放电过程。列表a存储充放电数据,索引的偶数位-1表示放电,1表示充电,奇数位表示充放电量。如a=[-1,5,1,40],表示先放电5度,然后充电40度。一次操作充满电后多余数值不计,同理每次放电时剩余电量最多到0。根据上述算法,回答下列问题:
(1)若电池最大容量10,初始满电。列表a=[-1,15,1,8,-1,10],则实际放电总量为　　　　。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#生成列表a,共200个元素,偶数位是-1或1,奇数位是5~100的整数,代码略。
cap=100;use=0　#电池初始满电100度,初始使用量0
for i in range(①　　　　　):
　if ②　　　　　 or a[i]+cap==101:
　　continue
　elif a[i]==-1:
　　if cap>=a[i+1]:
　　　　cap-=a[i+1];use+=a[i+1]
　　else:
　　　　cap=0;use+=cap
　else:　#充电
　　if cap+a[i+1]>100:
　　　　cap=100
　　else:
　　　　③　　　　
print("实际放电量",use,"度")
答案　(1)18　(2)①0,len(a),2或0,200,2
②a[i]+cap==-1或a[i]+cap<0
③cap+=a[i+1]
解析　(1)若电池最大容量10,初始满电。列表a=[-1,15,1,8,-1,10]的使用中,-1,15只能放电10,1,8充电8,-1,10时只有电量8可用,放电8,结果总放电18。(2)①程序中,每轮使用i和i+1两个位置,要全部遍历,得出答案。②此处是满电还要充电或者电池空还要放电两种无效情况的判断,a[i]+cap==101是满电还要充电,则填空处是电池剩余电量0(cap=0)还要放电(a[i]=-1)。③上面if的代码是充电限额,此处是正常充电a[i+1]的电量。
8.某十字路口地面方向标志如图a所示,其红绿灯采用四相位(东西直行、东西左转、南北直行、南北左转)依次动态控制,如图b所示。每个相位的绿灯时长根据两个方向中较大的车辆数动态调整,调整范围为10~30秒。黄灯亮3秒后开始调整下一个相位。每辆车通过十字路口的平均时长为2秒。例如:东向西直行16辆,西向东直行2辆,计算绿灯时长为32秒,按调整范围要求将东西直行相位的绿灯时长调整为30秒。
(1)若从0开始计时,东西直行相位最大车辆数为20,下一个相位(东西左转)最大车辆数为6,则南北直行相位的绿灯从第　　　　秒开始。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def get_data():
　#实时获取交通数据,将图b中的①~⑧方向的车辆数依次存储在列表中,如[11,3,5,4,12,22,13,11],代码略
base=2;short=10;long=30
cur=0
while True:　#依次判定四相位的绿灯时长
　car=get_data()
　　①　　　　
　if car[cur+1]>t:
　　　t=car[cur+1]
　green=long
　if short<=t*base<=long:
　　　②　　　　
　elif t*base　　　green=short
　#调整该相位的绿灯时长并亮起,之后绿灯熄灭,黄灯亮起,代码略
　cur=③　　　　
答案　(1)48　(2)①t=car[cur]　②green=t*base
③(cur+2)%8
解析　(1)东西直行相位最大车辆数20,需时长40秒,调整为最大值30秒;东西左转相位最大车辆数6,需12;黄灯时长均为3秒,总共时间为30+3+12+3=48秒。(2)①实时获取交通数据,将题图b中的①~⑧方向的车辆数依次存储在列表car中,cur表示当前相位对应的第1个方向,变量t表示当前相位两个方向较多的车辆数,初值t为car[cur]。若该相位第2个方向车辆数car[cur+1]大于第1个方向中,更新t的值为最多方向的车辆数。②动态调整的绿灯有3种可能,当t*base大于30时,默认为上限30;若t*base在[10,30]范围内时,绿灯时长直接取t*base;若低于下限10,则绿灯时长取下限。
③每个相位有2个方向(直行和左转),cur值的范围是0至7,每次cur需要加2并对8取模。
9.某路口的交通信号灯控制系统每隔1秒采集路口车辆情况,若在1分钟以内(采集60次)检测到持续有车辆通过路口,且持续数量最大值超过30辆时视为大流量,需要设置绿灯持续50秒,黄灯持续5秒,红灯持续45秒。其他流量情况下设置绿灯持续30秒,黄灯持续5秒,红灯持续25秒。如[2,4,0,1,0,3]表示检测了6次,每次检测到的车辆数分别是2、4、0、1、0、3辆车,最大持续通过的车辆数是6辆。请回答下列问题。
(1)若十次检测的车辆数据是[3,0,2,4,0,3,1,1,0,7],则持续数量最大是　　　　。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适代码。
while True:
　　cur=0;maxn=0
　　for i in range(60):
　　　　#接受一次系统中监控设备检测到的车辆数量,存入n,代码略
　　　　if n>0:
　　　　　　cur+=n
　　　　　　if ①　　　　　　:
　　　　　　　maxn=cur
　　　　else:
　　　　　　②　　　　　
　　　　#延时到1秒,代码略
　　if ③　　　　　　:
　　　　#发送“大流量”状态信息,设置下一轮的绿灯时间 50秒,
　　　　#黄灯时间 5秒,红灯时间45秒,代码略
　　else:
　　　　#发送“正常流量”状态信息,设置下一轮的绿灯时间 30秒,
　　　　#黄灯时间 5秒,红灯时间25秒,代码略
　　　　#等待当前一轮红绿灯结束,进行下一轮红绿灯设置,代码略
答案　(1)7　(2)①maxn30
解析　本题考查枚举算法思想。(1)持续有车辆的数据分别是3、6、5、7,最大持续数量是第10次检测结果7。(2)①若n大于0,表示持续有车辆经过,将n累加到cnt后,判断条件cur>maxn是否成立,若成立需要更新最大值maxn。②若n的值为0,表示未检测到车辆,将累加值cur初始为0。③最大持续的车流量maxn若大于30,发送“大流量”状态信息。
10.2024年巴黎奥运会乒乓球混双比赛采取七局四胜制,一方获胜四局即停止此场比赛。每局比赛采用11分制,即当一方得分达到11分且领先对手至少2分时,该局比赛结束。为熟悉比分规则,某球迷编写程序模拟混双比赛过程,依次输出每局比赛比分。请回答下列问题:
(1)根据比分规则,若某局比赛的比分为10∶13,　　　　(选填:合理/不合理)。
(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。
m=4
count=1
wa=wb=0
while ①　　　　　　:
　　a=b=0　#变量a存储一方得分,变量b存储对方得分
　　while a<11 and b<11 or abs(a-b)<2:
　　　　#输入一方得分t,代码略。若得分t为0,对手得1分,t为1,则对手得0分。
　　　　a+=t
　　　　②　　　　　
　　print("第",count,"局:",a,":",b)
　　if a>b:
　　　　wa+=1
　　else:
　　　　wb+=1
　　　　③　　　　　
print("胜负情况:",wa,":",wb)
答案　(1)不合理　(2)①wa解析　(1)当一方得分为10分,对方得分为12分时,结束该局比赛。(2)①判断双方获胜局数都没有达到4局。②当一方得分,即t为1时,a加1分,当t为0时,b得1分,因此b得1-t。③count表示第几局,当一局结束后,将递增1。
11.有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 total>=0:
　　print("能够满足全部同学租用自行车")
else:
　　print("资金不足,无法满足")
答案　(1)B　(2)①m-n　②total-=bike[i]-cash[j]　(3)B
解析　(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车开始遍历,遍历到m-1,共有n个学生借到了自行车。②现金cash[j]不够时可使用公用经费total补足费用。(3)从m-n遍历m-1,共遍历了几个元素,若循环结束后,i的值为m,表示已经完成了n个学生的租借,因此条件是等效的。(共88张PPT)
必修一　数据与计算
课时7　枚举算法思想
知识点 学业水平等级
1.掌握解析算法、枚举算法的算法特征,并会用计算机程序实现这两种算法。 4
2.理解迭代算法的思想,应用迭代算法处理实际的问题。 4
目 录
CONTENTS
真题剖析
01
知识梳理
02
课堂突破
03
当堂检测
04
课后作业
05
真题剖析
1
　　本节课的目的是提取浙江选考真题的填空题(第13、14和15题)中关于枚举算法思想的部分,围绕这个算法思想,并加以练习。枚举算法是计算机解决问题的主要方法,在第13、14和第15题中,往往要去枚举某个数据集,找到其中符合条件的情况,并进行统计和计算。如2023年6月遍历数组的各个元素,输出空货位数及还可以放置A型箱子的最多数量。2024年6月浙江选考遍历数组d的红灯和绿灯的状态值进行统计。在第15题的也有体现,如2023年6月浙江选考枚举有依赖关系的个数1st列表,进行链表节点的连接,同时为前驱节点的作一个标记为1。
1.(2024年6月浙江选考)某监控设备可定时采集红绿信号灯状态数据,数据格式记为[a,b],其中a、b分别为红灯和绿灯的状态值,0表示灯灭,1表示灯亮,如[0,1]表示红灯灭、绿灯亮。现要编写程序,每隔1秒采集并检测信号灯是否存在如下异常状态:第一类,红绿灯同亮或同灭;第二类,红灯或绿灯超时,即保持同一状态时长大于上限值(如300秒)。检测到异常状态就发送相应信息。请回答下列问题:
(1)若检测到“红绿灯同亮”异常,则采集到的数据是________(单选,填字母)。
A.[0,0] B.[0,1]
C.[1,0] D.[1,1]
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
tlimit=300　#设置信号灯保持同一状态时长上限值
pre=[-1,-1]
t=[0,0]　#t[0]、t[1]分别记录红灯、绿灯保持同一状态的时长
while True:
　# 收一次采集到的状态数据,存入d,代码略
　if　①________:
　　　if d[0]==1:
　　　　#发送“红绿灯同亮”信息,代码略
　　　else:
　　　　#发送“红绿灯同灭”信息,代码略
　for i in ②________:
　　　if d[i] == pre[i]:
　　　　t[i]+= 1
　　　　if ③________:
　　　　　　if i==0:
　　　　　　　#发送“红灯超时”信息,代码略
　　　　　　else:
　　　　　　　#发送“绿灯超时”信息,代码略
　　　else:
　　　　t[i]=1
　pre=d
　#延时1秒,代码略
答案　(1)D　(2)①d[0]==d[1] 　②range　(2)或range(len(d))　③t[i]>tlimit
解析　本题考查利用算法程序解决生活实际问题。 (1)1表示灯亮,两个灯同亮,值均为1。(2)①第一类,红绿灯同亮或同灭,表示采集的数据d中两个元素d[0]和d[1]的值相等。②从条件d[i] == pre[i]来看,变量i表示0或1,依次表示红灯或绿灯的索引位置。③t[0]、t[1]分别记录红灯、绿灯保持同一状态的时长,第二类,红灯或绿灯超时,即保持同一状态时长大于上限值(如300秒),当某个灯i的持续时间t[i]大于上限值tlimit时,出现超时信息。
2.(2023年6月浙江选考)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任务A依赖于任务B。
图b
实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
'''
工程包含的任务数存入变量n,任务间的依赖关系存入lst列表,lst[0]包含3项,任务lst[i][0]依赖于任务lst[i][l],lst[i][2]存放保留/删除标记,任务数据存入task列表task[i]包含2项,task[i][0]为完成任务所需天数,task[i][1]的初值为-1,代码略。
'''
pr=[0]*n
m=erase(lst)　#调用erase函数删除列表lst标记为“F”的依赖关系,返回依赖关系个数
for i in ________:
　 task[lst[i][1]][1]=lst[i][0]
　 pr[lst[i][0]]=1
#计算各个任务是最晚开始时间,代码略。
答案　range(m)
解析　本题考查枚举算法思想。调用erase函数删除列表lst标记为“F”的依赖关系,返回依赖关系的个数,枚举有依赖关系的个数lst列表,进行链表节点的连接,同时为前驱节点的作一个标记为1,表示其前驱节点是有后继的,不是头节点。
知识梳理
2
1.遍历指访问集合中每一个数据,并且访问________次。枚举指在遍历过程中,对访问的数据进行求和、计数或求最值的过程。
2.遍历集合中(如a=[3,6,4,2])的数据有两种方式,一是按________遍历,如for i in a,那么循环变量i就是集合中3等数字;二是按________遍历,如for i in range(len(a),那么a[i]才能表示集合中3等数字。
3.按位置遍历集合中数据时,位置i中数据可以是一个数据,也可以是一个用________表示的多个数据。
4.按位置遍历时,循环变量i往往出现在________里面,从而可以理解遍历的集合名称。
一
值
位置
列表
中括号
课堂突破
3
【典例1】 某监测设备可定时采集甲、乙两通道的排放数据,数据格式记为[a,b]。数据异常分两种情况。其一,当a超过500,b也超过500时;其二,当a与b的和超过1200时。
编写程序,每隔1秒采集排放数据,当排放数据持续异常的时长超过上限t1时,打开阀门。阀门开启的时长固定为t2秒,t2秒后阀门将自动关闭,并重新开始监测。请回答下列问题:
(1)下列数据属于数据异常的是________(单选,填字母)。
A.[985,211] B.[500,500]
C.[666,888] D.[0,1000]
(2)实现上述功能的部分Python程序段如下,请在划线处填入合适的代码。
t1=10　#设置持续异常的时长上限值
t2=3　#设置阀门每次开启的时长
switch=False　#用True、False分别表示阀门开、关状态
time1,time2=0,t2
while True:
　#接收一次采集到的排放数据,存入d,代码略
　if switch:
　　　①______
　　　if time2==0:
　　　　switch=False
　　　　time1=0
　else:
　　　if d[0]>500 and d[1]>500 or d[0]+d[1]>1200:
　　　　time1+=1
　　　if ②________:
　　　　switch=True
　　　　time2=t2
　　　　#执行“打开阀门”操作,代码略
　　 else:
　　　　　③______
　#延时1秒,代码略
答案　(1)C　(2)①time2-=1　②time1>t1　③time1=0
思维点拨
明考向 本题考查枚举算法思想
精点拨 (1)C选项当a与b的和超过1200时,属于数据异常。(2)①阀门开启的时长固定为t2秒,t2秒后阀门将自动关闭。打开阀门时,time2的值为t2,每次减少1,当time2的值为0时,关闭阀门,重新计时。②当排放数据持续异常的时长time1超过上限t1时,打开阀门。③当排放数据不持续异常时,将重新计时。
【变式1】 某密码强度判断程序功能如下:将密码字符分为大写字母、小写字母、数字字符以及其他符号四种类型。输入一串密码字符,如果该字符串的长度小于8,则输出“密码长度不符合要求!”;若该字符串包含三种字符及以上,则输出“强度:强”;若该字符串包含两种字符,则输出“强度:中”;若该字符串仅包含一种字符,则输出“强度:弱”。
(1)请在划线处填入合适的代码。
r=[0]*4;sum=0
s=input("输入密码:")
①______
if n<8:
　print("密码长度不符合要求!");
else:
　 for ②________:
　　　if ch>="a" and ch<="z":
　　　　 r[0]=1
　　　elif ch>="A" and ch<="Z":
　　　 　r[1]=1
　　　 ③________:
　　　　 r[2]=1
　　　else:
　　　 　r[3]=1
　　　sum=r[0]+r[1]+r[2]+r[3]
　　　if sum>=3:
　　　　 print("强度:强")
　　　elif ④________:
　　　 　print("强度:中")
　　　else:
　　　　 print("强度:弱")
(2)若输入的密码字符串为“Assd 237”,则输出的结果为________。
(3)若删除加框处语句,则②处应填写的语句是________。
答案　(1)①n=len(s)　②i in range(len(s)) 　③elif "0"<=ch<="9"　④sum==2　
(2)强度:强　(3)ch in s
解析　本题考查枚举算法思想。(1)①在条件n<8中,没有对n进行定义和初始化。②语句为ch=s[i],变量i没有定义,因此循环变量为i,是在字符串中位置。③第3种情况是判断是否是数字。④当sum的值为2时,有2种类别,强度为中。(2)字符串长度等于8且有4种类型的字符,属于强度为强的情况。(3)若删除加框处语句,则循环变量应为ch,是对字符串s中每个元素进行遍历。
【典例2】 某数据分析系统的功能为:采集实时数据val,生成最近连续5次数据的均值ave,如图a所示,绘制如图b所示的折线图,并发出数据异常信号:
异常一,上穿异常,虚线(数据val)上穿实线(数据ave),如图b中时刻5→6;
异常二,下穿异常,虚线(数据val)下穿实线(数据ave),如图b中时刻7→8。
time val ave
1 5.05
2 5.10
3 5.05
4 5.10
5 5.00 5.06
6 5.20 5.09
7 5.25 5.12
8 5.00 5.11
图a
图b
请回答下列问题。
(1)关于异常信号,下列说法正确的是________(单选,填字母)。
A.系统可能连续发出2个相同的异常信号
B.系统不可能连续发出2个相同的异常信号
(2)实现上述功能的部分Python代码如下,请在划线处填入合适的代码。
data=[]
while True:
　#接收实时数据val ,代码略
　data.append(val)
　if len(data)>=6:
　　sum=0
　　for i in①________:
　　　　sum+=i
　　　　pre_ave=(sum - data[-1])/5　#上一个近5次均值
　　　　ave=②________　#近5次均值
　　　　#发出异常一信号,代码略
　　#判断并发出异常二信号,代码略
#绘制折线图,代码略
(3)程序中加框处代码有错,请改正。
答案　(1)B　(2)①data[-6:]　②(sum-data[-6])/5或(sum-data[len(data)-6])/5
(3)data[-1]>ave and data[-2]思维点拨
明考向 本题考查枚举算法思想
精点拨 (1)要产生上穿异常,本次val的值要大于本次ave值,而上次val值要小于上次ave的值。要产生下穿异常,则本次val的值要小于本次ave值,而上次val值要大于上次ave的值。因此系统不可能连续发出2个相同的异常信号。(2)①从语句sum+=i来看,sum为6个数字之和,因此该集合中表示的最近6次的值。②近5次均值应为sum减去最1个数据的值之后求平均。(3)需要上一次的实线值小于上一次的平均值,即data[-2]ave
【变式2】 某公司有编号为0至n-1的n个会议室。每个预定的会议包含开始时间和结束时间,都会在未占用且编号较小的会议室举办,如果没有可用的会议室,会议将会延期到有空闲的会议室为止,并且优先提供给原开始时间最早的会议。编写Python程序,求举办最多次会议的会议室。请回答下列问题:
(1)若会议室n为2,会议如图所示,编号为1(即第2个)会议室承办的会议次数为________。
会议序号 开始时间 结束时间
会议1 0 30
会议2 5 10
会议3 15 20
会议4 17 35
(2)请完成下列划线处的代码。
#读取会议室数量存存储到变量n。
#读取会议到列表meetings中,每个元素包含会议开始时间和结束时间,并按开始时间排序,代码略。
cnt=[0]*n
tim=[0]*n　#存储当前每个会议室承办会议的结束时间
for m in meetings:
　best=0;i=0
　while i 　　if tim[i]<=m[0]:
　　　　　①______
　　　　　tim[i]=m[1]
　　　　　break
　　if tim[i]　　i+=1
　if i==n:
　　cnt[best]+=1
　　②______
ans=0
for i in range(1,n):
　if ③________:
　　ans=i
print("承办会议最多的会议室编号为:",ans)
答案　(1)3　(2)①cnt[i]+=1　②tim[best]+=m[1]-m[0]　③cnt[ans]解析　(1)会议室1承办会议1,30结束,会议室2承办会议2,10结束,承办会议3,20结束,承办会议4,38结束,因此会议室承办3个会议。(2)①遍历每个会议,tim存储当前每个会议室承办会议的结束时间,若某个会议室结束时间小于等于当前会议开始时间,表示该会议室可以承办该会议,该会议室的承办次数增加1次。②best记录了最早结束会议的会议室索引,若条件i==n成立,表示没有找到结束时间早于当前会议开始的会议室,那么让结束会议最早的会议室承办,该会议室会议结束时间更新为上次会议结束时间和本次会议所需时间之和(当前会议结束时间减去开始时间)。③cnt记录每个会议室承办会议的次数,ans表示承办会议最多的索引(编号),遍历所有会议室,若当前会议室承办会议次数cnt[i]大于cnt[ans],将承办会议最多的会议室编号更新为ans。
　　枚举算法是一种简单而直接的算法策略,通过将问题的所有可能解一一列举出来,并逐一检查每个解是否符合问题的要求,从而找到问题的解。这种算法通常用于解决规模较小、解空间有限的问题,因为它在解空间非常大时可能会变得非常低效,甚至不可行。在解题过程中,可以从循环变量出现的位置来确定枚举的对象,有按值枚举和按位置枚举两种方式。若循环变量出现在方括号中,表示是某个列表或者列表元素的下标,是典型的按位置枚举。枚举的对象可以是一个值,也可以是包含多个值的列表。
当堂检测
4
1.中华人民共和国居民身份证号码共18位,其中前17位为数字本体码,第18位为校验码。作为尾号的校验码,是按统一的公式计算出来的,校验码的计算方法为:
(1)将身份证前17位分别乘以不同的系数,系数依次为7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2;
(2)将这17位数字和系数相乘的结果相加;
(3)求用上述相加的和除以11的余数;
(4)余数只可能有0,1,2…9,10共11个数字,分别对应校验码1,0,X,9,8,7,6,5,4,3,2。
例如:身份证号34052419800101001X,计算3*7+4*9+0*10+5*5+…+1*2=189,用189除以11得出余数2,对应的校验码是X。
编写Python程序,判断输入的身份证号码的校验码是否正确,正确输出“Yes”,否则输出“No”,请在划线处填入合适代码。
def judge(s):
　v=[7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2]
#系数
　m='10X98765432'　#余数对应的校验码
　①______
　if n!=18:
　　　return False
　res=0
　for i in range(n-1):
　　　②______
　res=res%11
　code=m[res]
　if ③________:
　　　return True
　else:
　　　return False
s=input(输入身份证号码:')
if ④________:
　　print('Yes')
else:
　　print('No')
答案　①n=len(s)　②res+=int(s[i])*v[i] 　③code==s[-1]　
④judge(s)==True或judge(s)
解析　自定义函数judge用于判断输入身份证号码s是否合法,若合法返回True。①处下方语句if n!=18,因此该处肯定与n有关。②将这17位数字和系数相乘的结果相加并存储到res中。③执行语句res=res%11后,求用上述相加的和除以11的余数;code对应校验码,若计算出来的校验码与身份证号码是最后一位相同,则表示身份证有效。④调用自定义函数并判断输入的号码是否合法。
2.有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)
答案　(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。
3.某公司举办抽奖活动,设有一、二、三等奖。每张奖券印有3个互不相同的数字,每次在兑奖前公布中奖号码,兑奖时不考虑中奖数字的先后顺序,兑奖规则如下表所示。编程统计奖券获得的总奖金。
奖项 一等奖 二等奖 三等奖
兑奖条件 3个数字均匹配 2个数字匹配 1个数字匹配
奖金 500元 200元 100元
(1)某次中奖号码为3,1,8,则号码为1,6,3的奖券可以获得奖金________元。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#输入中奖号码,依次存储到列表元素win[0]至win[2]中,代码略
rew=[0,100,200,500]
①________
n=int(input("输入奖券数量:"))
for i in ②__________:
　cnt=0
　#输入奖券的号码,依次存储到列表元素tic[0]至tic[2]中,代码略。
　for j in range(3):
　　　if tic[j] in win:
　　　　　cnt+=1
　mon=③________
print("总奖金金额为:",mon)
答案　(1)200　(2)①mon=0　②range(n) 　③mon+rew[cnt]
解析　(1)匹配到1和3共两个数字,因此获二等奖。(2)①对总奖金金额mon赋初值0。②共有n张奖券,需重复n次。③cnt为匹配到的数字数量,则rew[cnt]为每张奖券的中奖金额。对这些金额进行累加求和。
4.服务器接收到的数据中包含一个状态信息码,状态信息码由3个数字组成,第1个为智能终端编号,第2个、第3个为温度、湿度状态(0为偏低、1为正常、2为偏高),如“101”表示1号终端的温度偏低、湿度正常。如果某终端的状态连续异常称为一个异常段,异常段内的状态个数称为长度,服务器将接收到的所有状态信息码按接收时间顺序保存到列表res中,如["111","012","211","901","100","211",……],编写程序对res进行处理,要求统计出各智能终端异常段长度超过阈值m的次数,请在划线处填入正确代码。
#数据保存到res,阈值保存到m,代码略
size=[0]*10
c=[0]*10
for code in res:
　①________
　if code[1:]!="11":
　　 　size[k]+=1
　else:
　　 　if size[k]>m:
　　　　　②________
　　 　size[k]=0
for i in range(10):
　if size[i]>m:
　　 　③________
for i in range(10):
　print("编号为"+str(i)+"的智能终端异常段长度超过阈值次数:"+str(c[i]))
答案　①k=int(code[0])　②c[k]+=1　③c[i]+=1
解析　①一共有10个终端,在code的第1个状态码中获取终端号码k,由于k为作size数组的下标,因此需转换成数字型。②条件code[1:]!="11"成立,表示k终端状态不正常,该终端的不正常次数size[k]加1,当状态正常时,将异常段长度与阈值m比较,如果大于m,则该终端的c[k]的值将增加1。③若某个终端最后一次的状态不正常,仅对次数size[k]增加了1,没有与m进行比较。对所有终端这种情况进行判断,若第i个终端最后一次不正常且次数超过m,则c[i]的值增加1。
5.某酒店的房间编号为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])
答案　(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。
课时作业
5
1.哥德巴赫猜想是近代三大数学难题之一,即任一大于2的偶数,都可表示成两个素数之和。采用Python验证100以内哥德巴赫猜想的正确性。
import math
def isprime(num):
　i=2
　while i<=int(math.sqrt(num)):
　　　if num % i==0:
　　　　　return False
　　　i+=1
　return True
n=6
while n<=100:
　　for j in range(3,int(n/2)):
　　　if　____________:
　　　　　print (n,"=",j,"+",n-j)
　　n+=2
则划线处的代码为________________。
答案　isprime(j) and isprime(n-j)
解析　本题考查自定义函数。自定义isprime的功能是判断num是否是素数。验证100以内哥德巴赫猜想的正确性,由于4=2+2,正确;n从6开始的偶数,因此n表示递增2。将n分解为j和n-j两个数,如果这两个数同时为素数,则验证成功。
2.输出2至100之间的所有素数。算法:采用一个flag数组来标记100以内含100的数是否是素数。循环变量i从2开始遍历,如果是素数,再将区间内所有i的倍数标记为False,依此类推,直到输出区间内所有素数。
编写的程序代码如下,请将空白处填写完整。
flag=[True]*101
for x in ①__________:
　if flag[x]:
　　print(x,end=",")
　　t=2
　　while ②__________:
　　　　　③__________
　　　　　t+=1
答案　①range(2,101)　②t*x<101　③flag[t*x]=False
解析　①从2开始遍历到100,判断并输出该区间的素数。②t表示x的倍数,从2倍开始,不断增加,直到t*x的值超出100。③将该数的倍数标记为False。
3.某字符串s是由一个原始字符串反复重叠形成的。例如字符串"abcababcababcab"的是由原始字符串"abcab"重叠而成。输出最长的原始字符串。检测的算法:原始字符串从1个字母开始枚举,将该字符串划分成与原始字符串若干段,若划分的字符串每一段与第一段相同,则认为该字符串是由这段字符重叠而成。若枚举的最大长度为字符串s的一半时,则不可能有原始子串叠加而成。请完成下列空白处代码。
s="abcababcababcababcababcab"
n=len(s);ans=""
for i in　①________:#变量i表示子串的长度
　if n%i==0 :
　　for j in　②________:#在字符串s中依次取出长度为i的子串
　　　　if s[:i]!=s[j:j+i]:
　　　　　　break
　　else:
　　　　③______
print("原始串是:"+ans)
答案　①range(1,n∥2+1)　②range(i,n,i) 　③ans= s[:i]
解析　字符串s长度肯定是原始字符串长度i的整数倍。①原始字符串的长度最小为1,最大为s字符串长度的一半。②前面第一段为原始子串,从索引i开始,每隔长度i取出一个子串,如果取出的子串与原始子串不相同,表示该原始子串不符合要求,结束长度为i子串的遍历。③当整个字符串s全部遍历完成后,所有的子串s[j:j+i]均与原始子串s[:i]相等,没有执行break,则要执行for循环的else部分。
4.给定n个形如[L,R]的区间,合并所有存在交集的区间(若两个区间在端点处相交,也认定存在交集),如区间[1,3]和[2,6]可以合并为区间[1,6]。编写程序,输出合并后的区间个数。#读入包含多个区间的data数组,并将各个区间按左区间升序,若左区间相等按右区间升序,代码略,类似data=[[1,2],[2,4],[3,6],[5,6],[7,8],[7,9]]
newdata=[]
left=data[0][0];right=data[0][1]
for i in　① ________:
　if data[i][0]<=right:
　　　if ②________:
　　　　right=data[i][1]
　else:
　　　newdata.append([left,right])
　　　left=data[i][0]
　　　right=data[i][1]
③______
print(newdata)
答案　①range(1,len(data))　②data[i][1]>right　③newdata.append([left,right])
解析　①left和right表示合并新区间的左右边界,默认值为第1个区间的左右边界,因此从第2个区间开始遍历。②如果遍历到区间的左边界小于等于right,表示与新区间有交集。可能是新区间的子集,包含在新区间的内部,也可能右边界比right大,此时需更新右边界。③遍历到最后一个区间时,该区间可能与前面一个区间有交集,此时执行if部分,没有添加到newdata;也可能单独成一个新区间,语句newdata.append([left,right])只是将前面的区间添加进去,语句left=data[i][0]、right=data[i][1]定义新区间的左右边界,但没有添加到newdata。
5.小陈在学习历史时,从公元1000年至今,发现有的日期特别的“优美”,如1010年01年01日,2021年12月02日,小陈把它们称为“对称日”。为了寻找指定年份中的“对称日”,小陈编写了如下的Python程序,程序运行结果如图所示,请在划线处填入合适的代码。
请输入开始年份:2000
请输入结束年份:2023
20200202
20211202
def check(k):
　check=True
　y=int(k[0:4]); m=int(k[4:6])
　d=int(k[6:8])
　flag=0
　if m<1 or m>12:
　　　check=False
　if (y%4==0 and y %100!=0 or y%400==0) and ①________:#判断闰年时的相应情况
　　　flag=1
　if　②________:
　　　check=False
　③______
ks=int(input("请输入开始年份:"))
js=int(input("请输入结束年份:"))
lst=[31,28,31,30,31,30,31,31,30,31,30,31]
for i in range(ks,js+1):
　k1=str(i)
　k1=k1+ k1[::-1]
　if check(k1)==True:
　　　print(k1)
答案　①m==2　②check==True and d>lst[m-1]+flag或check==True and(d<1 or d>lst[m-1]+flag)　③return check
解析　 遍历开始年份至结束年份,先创建一个对称的日期,再调用函数去检测这个日期是否合理。①check是日期是否合理的标志,flag表示闰年的2月比其他年份多1天,如果是其值为1,判断是否是闰年外,还需加一个条件是否是2月份。②在日期合理,且check是真的前提下,如输入的d大于当月的天数,则输入的d无效。③返回是否效的结果check。
6.某快递分拣站有4个分拣机器人(编号0~3),根据包裹重量分为优先包裹和普通包裹,两种包裹的分拣规则如下:
①重量≥10 kg的包裹为优先包裹,优先分配:
·先选择当前空闲的机器人(同空闲状态则编号小优先)
·若无空闲机器人,则选当前任务剩余时间最短的机器人(同剩余时间则编号小优先)
②重量<10 kg的包裹为普通包裹,按机器人累计分拣件数分配,选择累计分拣件数最少的机器人(同分拣件数则编号小优先)
(1)某时刻状态:
机器人0:空闲(累计200件);
机器人1:忙碌,剩余8分钟(累计150件);
机器人2:忙碌,剩余5分钟(累计150件);
机器人3:忙碌,剩余8分钟(累计220件)。
此时到达一个包裹,下列选项包裹重量和分配的机器人相匹配的是________(单选,填字母)。
A.3 kg,机器人0 B.5 kg,机器人1
C.10 kg,机器人2 D.15 kg,机器人3
(2)以下Python代码段实现优先包裹的分配:
#[False,0,200]分别表示机器人状态(空闲),当前任务剩余时间,累计分拣件数
robots=[[False,0,200],[True,5,150],[True,8,150],[True,3,220]]
def assign_urgent():
　for i in range(4):
　　　if ①__________:
　　　　#更新机器人状态和累计分拣件数,代码略
　　　　return i　#直接分配空闲机器人
　k=0
　for i in range(1,4):
　　　if ②__________:
　　　　k=i
　　　③__________　#更新累计分拣件数
　return k
答案　(1)B　(2)①not robots[i][0]或robots[i][0]==False　
②robots[i][1]解析　(1)A选项包裹重量为3 kg,则分配给累计分拣数最少的机器人1;B选项包裹重量为5 kg,则分配给累计分拣数最少的机器人1;C选项包裹重量为10 kg,则分配给当前空闲机器人0;D选项包裹重量为15 kg,则分配给当前空闲机器人0。(2)①若当前有空闲机器人时(状态为False时),将包裹分配给空闲机器人。②a若不存在空闲机器人,则需要依次遍历每个机器人的当前任务剩余时间,找到最小值k。③此时k为当前选中的机器人,则要让其分拣次数robots[k][2]加1。
7.新能源汽车电池在使用中会经历多次充放电,设计算法模拟电池充放电过程。列表a存储充放电数据,索引的偶数位-1表示放电,1表示充电,奇数位表示充放电量。如a=[-1,5,1,40],表示先放电5度,然后充电40度。一次操作充满电后多余数值不计,同理每次放电时剩余电量最多到0。根据上述算法,回答下列问题:
(1)若电池最大容量10,初始满电。列表a=[-1,15,1,8,-1,10],则实际放电总量为________。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#生成列表a,共200个元素,偶数位是-1或1,奇数位是5~100的整数,代码略。
cap=100;use=0　#电池初始满电100度,初始使用量0
for i in range(①__________):
　if ②__________ or a[i]+cap==101:
　　continue
　elif a[i]==-1:
　　if cap>=a[i+1]:
　　　　cap-=a[i+1];use+=a[i+1]
　　else:
　　　　cap=0;use+=cap
　else:　#充电
　　if cap+a[i+1]>100:
　　　　cap=100
　　else:
　　　　③________
print("实际放电量",use,"度")
答案　(1)18　(2)①0,len(a),2或0,200,2　②a[i]+cap==-1或a[i]+cap<0
③cap+=a[i+1]
解析　(1)若电池最大容量10,初始满电。列表a=[-1,15,1,8,-1,10]的使用中,-1,15只能放电10,1,8充电8,-1,10时只有电量8可用,放电8,结果总放电18。(2)①程序中,每轮使用i和i+1两个位置,要全部遍历,得出答案。②此处是满电还要充电或者电池空还要放电两种无效情况的判断,a[i]+cap==101是满电还要充电,则填空处是电池剩余电量0(cap=0)还要放电(a[i]=-1)。③上面if的代码是充电限额,此处是正常充电a[i+1]的电量。
8.某十字路口地面方向标志如图a所示,其红绿灯采用四相位(东西直行、东西左转、南北直行、南北左转)依次动态控制,如图b所示。每个相位的绿灯时长根据两个方向中较大的车辆数动态调整,调整范围为10~30秒。黄灯亮3秒后开始调整下一个相位。每辆车通过十字路口的平均时长为2秒。例如:东向西直行16辆,西向东直行2辆,计算绿灯时长为32秒,按调整范围要求将东西直行相位的绿灯时长调整为30秒。
(1)若从0开始计时,东西直行相位最大车辆数为20,下一个相位(东西左转)最大车辆数为6,则南北直行相位的绿灯从第________秒开始。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def get_data():
　#实时获取交通数据,将图b中的①~⑧方向的车辆数依次存储在列表中,如[11,3,5,4,12,22,13,11],代码略
base=2;short=10;long=30
cur=0
while True:　#依次判定四相位的绿灯时长
　car=get_data()
　　①________
　if car[cur+1]>t:
　　　t=car[cur+1]
　green=long
　if short<=t*base<=long:
　　　②________
　elif t*base　　　green=short
　#调整该相位的绿灯时长并亮起,之后绿灯熄灭,黄灯亮起,代码略
　cur=③________
答案　(1)48　(2)①t=car[cur]　②green=t*base　③(cur+2)%8
解析　(1)东西直行相位最大车辆数20,需时长40秒,调整为最大值30秒;东西左转相位最大车辆数6,需12;黄灯时长均为3秒,总共时间为30+3+12+3=48秒。(2)①实时获取交通数据,将题图b中的①~⑧方向的车辆数依次存储在列表car中,cur表示当前相位对应的第1个方向,变量t表示当前相位两个方向较多的车辆数,初值t为car[cur]。若该相位第2个方向车辆数car[cur+1]大于第1个方向中,更新t的值为最多方向的车辆数。②动态调整的绿灯有3种可能,当t*base大于30时,默认为上限30;若t*base在[10,30]范围内时,绿灯时长直接取t*base;若低于下限10,则绿灯时长取下限。③每个相位有2个方向(直行和左转),cur值的范围是0至7,每次cur需要加2并对8取模。
9.某路口的交通信号灯控制系统每隔1秒采集路口车辆情况,若在1分钟以内(采集60次)检测到持续有车辆通过路口,且持续数量最大值超过30辆时视为大流量,需要设置绿灯持续50秒,黄灯持续5秒,红灯持续45秒。其他流量情况下设置绿灯持续30秒,黄灯持续5秒,红灯持续25秒。如[2,4,0,1,0,3]表示检测了6次,每次检测到的车辆数分别是2、4、0、1、0、3辆车,最大持续通过的车辆数是6辆。请回答下列问题。
(1)若十次检测的车辆数据是[3,0,2,4,0,3,1,1,0,7],则持续数量最大是________。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适代码。
while True:
　　cur=0;maxn=0
　　for i in range(60):
　　　　#接受一次系统中监控设备检测到的车辆数量,存入n,代码略
　　　　if n>0:
　　　　　　cur+=n
　　　　　　if ①____________:
　　　　　　　maxn=cur
　　　　else:
　　　　　　②__________
　　　　#延时到1秒,代码略
　　if ③____________:
　　　　#发送“大流量”状态信息,设置下一轮的绿灯时间 50秒,
　　　　#黄灯时间 5秒,红灯时间45秒,代码略
　　else:
　　　　#发送“正常流量”状态信息,设置下一轮的绿灯时间 30秒,
　　　　#黄灯时间 5秒,红灯时间25秒,代码略
　　　　#等待当前一轮红绿灯结束,进行下一轮红绿灯设置,代码略
答案　(1)7　(2)①maxn30
解析　本题考查枚举算法思想。(1)持续有车辆的数据分别是3、6、5、7,最大持续数量是第10次检测结果7。(2)①若n大于0,表示持续有车辆经过,将n累加到cnt后,判断条件cur>maxn是否成立,若成立需要更新最大值maxn。②若n的值为0,表示未检测到车辆,将累加值cur初始为0。③最大持续的车流量maxn若大于30,发送“大流量”状态信息。
10.2024年巴黎奥运会乒乓球混双比赛采取七局四胜制,一方获胜四局即停止此场比赛。每局比赛采用11分制,即当一方得分达到11分且领先对手至少2分时,该局比赛结束。为熟悉比分规则,某球迷编写程序模拟混双比赛过程,依次输出每局比赛比分。请回答下列问题:
(1)根据比分规则,若某局比赛的比分为10∶13,________(选填:合理/不合理)。
(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。
m=4
count=1
wa=wb=0
while ①____________:
　　a=b=0　#变量a存储一方得分,变量b存储对方得分
　　while a<11 and b<11 or abs(a-b)<2:
　　　　#输入一方得分t,代码略。若得分t为0,对手得1分,t为1,则对手得0分。
　　　　a+=t
　　　　②__________
　　print("第",count,"局:",a,":",b)
　　if a>b:
　　　　wa+=1
　　else:
　　　　wb+=1
　　　　③__________
print("胜负情况:",wa,":",wb)
答案　(1)不合理　(2)①wa③count+=1或者count=wa+wb
解析　(1)当一方得分为10分,对方得分为12分时,结束该局比赛。(2)①判断双方获胜局数都没有达到4局。②当一方得分,即t为1时,a加1分,当t为0时,b得1分,因此b得1-t。③count表示第几局,当一局结束后,将递增1。
11.有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
答案　(1)B　(2)①m-n　②total-=bike[i]-cash[j]　(3)B
解析　(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车开始遍历,遍历到m-1,共有n个学生借到了自行车。②现金cash[j]不够时可使用公用经费total补足费用。(3)从m-n遍历m-1,共遍历了几个元素,若循环结束后,i的值为m,表示已经完成了n个学生的租借,因此条件是等效的。

展开更多......

收起↑