资源简介

课时8　桶与索引的算法思想
【学业要求】
知识点 学业水平等级
1.能依据解决问题的需求来界定关键问题、抽象建模及设计算法,运用三种控制结构和算法描述方法合理地表示算法。 4
2.理解迭代算法的思想,应用迭代算法处理实际的问题。 4
　　本节课的目的是提取浙江选考真题的填空题(第13、14和15题)中关于桶和索引算法思想的部分,围绕这个算法思想,并加以练习。数据往往存储在数组的某个位置中,这个位置就是桶的名称,可以表示一类数据。2021年1月浙江选考中,用桶来表示可以容纳多少人的分组名称,就少了查找数据的过程,提高了算法效率。当某个数据集合的元素有多个数据项时,用索引来表示元素的位置,如2023年6月卷第15题,把各个任务下标按完成的先后顺序,依次添加到c数组中,如2024年6月浙江选考“重排”处理数据,将不同位置的数据依次复制到新的位置。
(2024年6月浙江选考)某项活动有n个单位(编号1到n)参加,需将员工分成若干个小组,每个小组的人数上限为m,小组编号按新建次序从1开始编号。分组时,首先按单位编号次序依次在各单位内部分分组,每m人分配到一个新建小组中,不足m人的剩余员工暂不分配;然后按剩余员工人数由大到小的顺序,依次为各单位剩余员工分配小组。若某单位剩余员工人数为k,则分配方法为:在已建的小组中查找空位数(该小组还可容纳的人数)大于或等于k的小组,如果找到的小组有多个,则选择空位数最少的小组,将此k人分配到该小组中;如果没有找到,则新建一个小组,将此k人分配到该小组中。设n为5,m为20,各单位员工人数及单位内部的分组过程
#读取小组人数上限存入m;读取1至n号单位的数据,依次存入列表data的data[0]至data[n-1]中。data[i]包含2个数据项,data[i][0],data[i][1]分别存放单位编号及员工人数,代码略
#对各单位内部进行分组,组号依次存储在a[0]至a[n-1]中,共有gnum个分组代码略
bubble_sort(data)　#根据每个单位的剩余员工人数,对data进行降序排序
b=[[] for i in range(m)]
i=0
while i　　①　　　
　　while j　　　　j+=1
　　if j　　　　v=b[j].pop()
　　else:
　　　　gnum+=1;v=gnum
　　a[data[i][0]].append(v)
　　 ②　　　
　　i+=1
#输出各单位的分组编号,代码略
答案　①j=data[i][1]
②b[j-data[i][1]].append(v)
解析　本题考查桶的算法思想。①新建一个大小为m列表b表示各个分组的剩余人数,b[0]至b[m-1]的初值均为0。对每个单位的剩余员工人数降序排序,并遍历n个单位,首先查找是否存在一个大于等于该单位剩余人数最小分组,其方法是用循环while j1.桶是数据结构中一个通用的概念,用来描述一种将数据分　　　　或分类的方法,以便有效地进行查找、排序或分析。
2.桶适用的条件是数据分组的数量是　　　　知的,桶用列表来存储数据,列表的下标就是分组的代号。
3.桶应用第一步是创建一定数量的　　　　桶,如a=[0]*n或a=[[]for i in range(n)]。
4.桶中每个元素可以是一个数值,往往表示该分组中数据的数量,可以是一个逻辑值,表示该分组是否存在,还可以是一个　　　　,往往是多个原始数据集合的下标。
5.桶应用的第二步是分配元素到桶,遍历原数据集合,根据特定的规则,将每个元素放入对应的　　　　中。
6.桶应用的第三步是收集结果,依次从每个　　　　中取出元素,返回原数据集合中的数据。
7.索引是一种用来提高数据访问效率的机制。它通过创建一个新的　　　　来指向原始数据中的位置,从而使得查找、插入和删除等操作能够更快地完成。
自我校对:1.组　2.已　3.空　4.列表　5.桶　6.桶　7.列表　
【典例1】 某学校有n位教职员工,对本单位m条(m大于20)新闻进行投票,选出校园十大新闻,并输出头条新闻的投票者。每位教职员工必须在1至m编号的新闻中,选择10条新闻进行投票。实现的Python程序如下,请将空白处填写完整。
#读取教职员工数量,存储变量n中。
#读取参选新闻数量,存储变量m中。
#读取教职员工数量的投票信息,依次存储到data[0]至data[n-1]中,代码略
number=[[]for i in range(m+1)]
for i in range(len(data)):
　for x in data[i]:
　　　①　　　
order=[i for i in range(m+1)]　#将1至m新闻编号依次存储在order[1]至order[m]
for i in range(10):　#按投票数量降序选出最大的10个新闻编号
　　for j in range(m,i+1,-1):
　　　if ②　　　　 :
　 　　　order[j],order[j-1]=order[j-1],order[j]
s="头条新闻的投票者有:"
for x in ③　　　　 :
　s+=str(x)+","
#输出校园十大新闻以及头条新闻的投票者,代码略。
思维点拨
明考向 本题考查桶和索引的算法思想
精点拨 ①初始化了一个名为number的桶,作用是存储每个新闻的投票者编号。遍历投票数据data,第i名投票者有10个投票的编号,将投票者i添加到他所投的桶number[x]。②number数组中存储是各个新闻的投票数量,order是新闻的编号,按投票数量降序选出最大的10个新闻编号,因此比较对象为number[order[j]]和number[order[j-1]],他们的长度越大,说明投票数越多。③经过排序后,order[1]是投票数最多的新闻编号,number[order[1]]中存储了该编号的投票者
答案　①number[x].append(i)
②len(number[order[j]])>len(number[order[j-1]])
③number[order[1]]
【变式1】 抢红包游戏:微信抢红包游戏成为了一代人的经典回忆,游戏将总金额为n的“红包”随机分配给m个玩家,红包的分配需同时满足以下规则:①所有人抢到的金额总和跟总金额n相等;
②每个人至少抢到1分钱;③每个人抢到的金额随机;④每个人抢到金额大小的概率平等。
算法为:将总金额n元乘以100,换算成以分为单位。在[1,100*n-1]范围内随机生成m-1个不重复的点,将区间0至100*n划分为m段,每一段可表示一个红包金额。
实现上述功能的Python程序如下,请在划线处填入合适的代码。
import random
n=int(input("输入红包金额:"))*100
m=int(input("输入红包数量:"))
if m>n:
　　print("游戏无法继续,结束!")
else:
　　f=[False]*(n+1)
　　for i in　①　　　　:
　　　　t=random.randint(1, n-1)
　　　　while f[t]:
　　　　　　t=random.randint(1, n-1)
　　　　f[t]=True
　　②　　　
　　p,amax=0,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))
答案　①range(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。
【典例2】 有m个人结伴旅行(m<=9,每人用整数1~m编号)。期间既有全员参与的集体活动,也有自主参与的小团队活动。每项活动的消费由参与人平均分摊,其中一人先行垫付并记录。记录内容包括该项活动的人均消费金额(元)、参与人。每项活动的参与人用字符串表示,垫付人排在第1位。如"25134"表示2、5、1、3、4号参与该项活动,其中2号是垫付人。旅行活动结束依据所有活动的消费记录进行结算。要求输出转账明细。(编号小的付款人优先转账给编号小收款人)
(1)若有3个人参加3项活动,每项活动的参与人分别是"31","12","123",每项活动的平均消费金额分别为50元,100元,300元,则3号人员应还款项为　　　　 元。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#读取参与活动人员数量m;
#读取n项参加活动人员依次存储在a[0]至a[n-1]中;
#读取每项活动平均金额依次存储在x[0]至x[n-1],代码略。
b=[0 for i in range(m+1)]　#保存应还款数据
for i in range(n):　#根据消费记录计算应还款
　 p=int(a[i][0])
　　　
　 for j in range(1,len(a[i])):
　　　p=int(a[i][j])
　　　b[p]+=x[i]
pay=[];rec=[]
for i in ②　　　　:
　if b[i]>0:
　　　pay.append(i)
　elif b[i]<0:
　　　rec.append(i)
j=0
for i in range(len(pay)):
　while j　　　print("用户"+str(pay[i])+"向用户"+str(rec[j])+"支付"+str(-b[rec[j]]))
　　　b[pay[i]]+=b[rec[j]]
　　　j+=1
　if b[pay[i]]>0:
　　　print("用户"+str(pay[i])+"向用户"+str(rec[j])+"支付"+str(b[pay[i]]))
　　　④　　　
思维点拨
明考向 本题考查桶的算法思想
精点拨 (1)活动1:3号垫付-50元,1号应付50元;活动2:1号垫付-100元,2号应付100元;活动3:1号垫付-600元,2、3号应付300元,因此3号应款项-50+300=250。(2)①p为第i项活动的垫付人,一共垫付len(a[i])-1人,每人平均消费金额为x[i]元。②遍历b数组,统计编号1至m编号的人员的应还款。③支付金额为正,垫付金额为负,当两者之和大于等于0,表示支付的金额大于等于垫付金额(绝对值),应从支付金额中送去垫付者可以接受的金额,同时j向后移动。④循环结束后,支付的金额肯定小于垫付金额,因此垫付者接受了部分金额(b[pay[i]]),需更新b[rec[j]]的值
答案　(1)250　(2)①b[p]-=(len(a[i])-1)*x[i]
②range(1,m+1)或range(len(b))　③b[rec[j]]+b[pay[i]]>=0　④b[rec[j]]+=b[pay[i]]
【变式2】 编排试场。每个试场有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]　#读取班级数量,存储变量n中。
bj=[3, 2, 1, 4, 6, 5, 7]　#读取每个班级的人数并按人数降序排列,依次存储到num[0]至num[n-1]中,将排序后的班级依次存储到bj[0]至bj[n-1],代码略
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)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人,试场数将增加一个。③与后面的数进行比较,如果小于或等于后面的班级人数,进行交换。
　　若已知某个数据范围,可以对这些数据进行分类分组,并创建一个列表,用下标来表示这些类别,每个元素存储一个类别的数量或内容,在处理这些数据时,只要知道这些数据的类别,就不需要进行查找,依次从每个桶中取出元素,返回原数据集合中的数据。索引是一种用来提高数据访问效率的机制,通过创建一个新的列表来指向原始数据中的位置,从而使得查找、插入和删除等操作能够更快地完成。
1.有如下Python程序段:
s1=input("请输入字符串:")
a=[0]*128
for item in s1:
　ch=ord(item)
　a[ch]=a[ch]+1
s2=""
for i in range(len(a)):
　 for j in range(a[i]):
　 　　s2=s2+chr(i)
print(s2)
列表a各元素的初始值都为0,s1中输入的内容为"abs54int"。执行该程序后,程序输出的结果中第5个字符为(　　)
A.n B.s
C.4 D.i
答案　D
解析　利用桶统计字符串s1各个字符的个数,字母ch的ASCII码值作为桶的下标。遍历各个桶的下标i,若该桶a[i]不为0,将桶中各个字符chr(i)拼接到字符串s2中。
2.某Python程序实现的功能:运行程序输入一个四位整数,能够判断该四位整数是否存在数字重复的位。程序代码如下:
n=int(input("请输入一个四位正整数:"))
f=[0]*10
while n>0:
　　y=n%10
　　①　　　
　　n=n∥10
if ②　　　　:
　　print("有重复的位。")
else:
　　print("没有重复的位。")
划线处的代码应填(　　)
A.①f[y]=1　　 ②sum(f)<4
B.①f[y]+=1 ②sum(f)<4
C.①f[y] =1 ②sum(f)==4
D.①f[y]+=1 ②sum(f)==4
答案　A
解析　本题考查桶的算法思想。表达式n%10的功能是取出个位数,语句n=n∥10的功能是去除个位数。语句f[y]=1的功能是y是否出现过,如果出现为1,没有出现为0。语句f[y]+=1的功能是统计y出现的次数。sum(f)是统计f列表元素之和。
3.有如下Python程序:
s1="0312";s2="ABCDEFGH"
m=0;c=""
for i in range(len(s2)) :
　k=int(s1[i%4])
　m=4*(i∥4)
　c+=s2[k+m]
执行该程序段后,变量c的值是(　　)
A."ADBCADBC" B."ABCDEFGH"
C."AHBGCFDE" D."ADBCEHFG"
答案　D
解析　遍历字符串s2各个位置,当i为0至3时,m的值为0,其余m的值为4,即把字符串s2分成"ABCD"和"EFGH"两段,每段分别取出偏移位置为0,3,1,2的字符。
4.某公司在内部设置了一项彩票。该彩票的规则是:每张彩票上印有3个各不相同的数字,每次在兑奖前公布一个由3个各不相同的数字构成的中奖号码。兑奖时不考虑彩票上的数字和中奖号码中的各个数字出现的位置。共设置3个奖项,一等奖至三等奖,兑奖规则如下表所示。现已知某次的中奖号码和小明买的若干张彩票号码,请写程序帮助小明统计他可以获得多少奖金。
奖项 一等奖 二等奖 三等奖
中奖条件 匹配3个数字 匹配2个数字 匹配1个数字
奖金 500元 300元 100元
(1)某次中奖号码为3,1,8,则号码为1,6,3的彩票可以获得奖金　　　　元。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
w=list(map(int,input("输入中奖号码:").split()))　#输入3个数字并保存到列表list
flag=[0]*14
rst=[0]*4
m=[0,500,300,100]
for i in range(3):
　flag[w[i]]=1
n=int(input("输入彩票数量:"))
for i in range(n):
　①　　　
　tmp=list(map(int,input().split()))　#输入彩票的3个数字并保存到列表tmp
　for j in range(3):
　　　if ②　　　　:
　　　　cnt+=1
　rst[(4-cnt)%4]+=1
mon=0
for i in range(1,4):
　③　　　
print("总奖金数为:",mon)
答案　(1)300　(2)①cnt=0　②flag[tmp[j]] ==1
③mon+=rst[i]*m[i]
解析　(1)匹配到2个数字,获二等奖。(2)①变量cnt表示匹配到的数字,对cnt赋初值0。②遍历tmp列表,若tmp[j]的值在flag列表中对应值为1,表示匹配到一个数字。③rst[i]存储各个奖项的数量,m[i]存储对应奖项的获奖金额。
5.字母异位词指两个不同的单词由相同的字母组成,且不区分大小写,但字母出现的位置可以不同。比如"Heart"和"earth"是字母异位词,"apple"和"Paper"不是字母异位词。现编写 Python 程,文本文件“words.txt”中保存着若干对单词组,从文件“words.txt”中读取多对单词组,并判断该组中两个单词是否为字母异位词。
(1)请在划线处填入合适的代码。
def change(x):　#将字母都转换为小写字母
　for k in x:
　　　if "A"<=k<="Z":
　　　　　①　　　
　　　if "a"<=k<="z":
　　　　　y+=k
　return y
def fs(m, n) :
　cnt=[0]*26
　for i in range(len(m)) :
　　　ch=ord(m[i])
　　　②　　　
　for i in range(len(n)) :
　　　ch=ord(n[i])
　　　cnt[ch-ord("a")]-=1
　return cnt
#读取words.txt文件中的内容,将其中的单词依次保存在列表text中,代码略。
s1=s2=""
num=len(text)
for i in range(num) :
　s1=text[i][0]
　s2=text[i][1]
　c= ③　　　
　j=0
　while j　　　if c[j]!=0:
　　　　print(sl,"和",s2,"不是字母异位词")
　　　　break
　　　j+=1
　else:　#在循环正常结束后执行
　　　print(s1,"和",s2,"是字母异位词")
(2)下列程序代码中,加框处的语句　　　　 (选填:能/不能)改写成语句 elif "a"<=k<="z":
答案　(1)①k=chr(ord(k)+32)或k=chr(ord(k)+ord("A")- ord("a"))或 k=k.lower()
②cnt[ch-ord("a")]+=1或 cnt[ch-97]+=1
③fs(change(s1),change(s2))或fs(change(s2),change(s1))　(2)不能
解析　(1)①小写字母的ASCII码值是对应大写字母ASCII码值加上32。②语句cnt=[0]*26定义共26个元素的桶,每个桶分别存储每个字母的数量,因此需将其ASCII值减去97得到0至15的位置。③将s1、s2调用fs。(2)略。
6.某路边有一排照明装饰灯,编号依次为1~n。现发现有多个装饰灯不亮,受维修成本的限制,只对其中的一部分进行维修,维修后保证有k个编号连续的装饰灯能够正常照明。编写程序,根据已损坏的装饰灯编号,输出最少需要维修的装饰灯数量。请回答下列问题:
(1)若路边有10个照明装饰灯(编号1~10),其中编号为1、4、8、10的装饰灯不亮,维修后需保证有6个编号连续的装饰灯能正常照明,则最少需要维修的装饰灯数量是　　　　。
(2)请完成下列划线处的代码。
#输入照明装饰灯的总数n、编号连续的正常照明装饰灯数量k,代码略
#读取不亮的装饰灯编号,存入d,代码略
v=[0]*(n+1);c=[0]*(n+1)
ans=n
for i in ①　　　　　:
　v[d[i]]=1
for i in range(1,n+1):
　c[i]=c[i-1]+v[i]
i=1
while i<=n-k+1:
　last= ②　　　　
　num=c[last]-c[i-1]
　if ③　　　　　:
　　 　ans=num
　i=i+1
print(ans)
答案　(1)1　(2)①range(len(d))　②i+k-1　③num解析　(1)修理编号为4的装饰灯,即可保证2到7号这6个装饰灯正常照明。(2)①语句v[d[i]]=1统计损坏装饰灯数量,损坏的装饰灯存入d中,需遍历d中所有数据。②数组c统计到当前位置共损坏灯的数量。i表示连续亮灯的开始位置,其最大值为n-k+1。last是连续亮灯的结束位置i+k-1。
③连续k个灯的区间内的损坏灯的数量为num,找出最小修理数量ans。
7.某公路由于长期没有维修,路上出现了很多个坑。为了尽快填补好这些坑,交通管理部门决定对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)
答案　(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]。
1.有如下Python程序段:
a=[7,4,9,4,3]
b=[0]*10;c=[0]*10
for i in a:
　 b[i]+=1
pa=0
for j in range(10):
　for k in range(b[j]):
　　　c[pa]=j
　　　pa+=1
执行以上程序,数组c[0]至c[4]数据依次是(　　)
A.7,9,4,4,3 B.3,4,4,7,9
C.4,4,7,9,3 D.9,7,4,4,3
答案　B
解析　本题考查桶排序。第一个for循环中,语句b[i]+=1的功能是:利用桶对数组a中数据进行计数。桶的下标是有序的,对应数的值,按桶的编号输出各个桶中的数。在第二个循环中,当b[j]值大于0时,开始重复地把j的值依次放在c数组中。
2.有如下Python程序段:
a=[0]*10;s="533774"
for i in s:
　 a[int(i)]=1
ans,n=0,0
i=9
while i>=0 and n<3:
　 　if a[i]==1:
　 　　ans=ans*10+i
　　 　n+=1
　i-=1
print(ans)
运行程序段后,显示的内容是(　　)
A.9876 B.754
C.775 D.7754
答案　B
解析　第一个for循环是统计出现的数字,如果出现过,该数对应下标的a数组值为1,否则为0,并没有统计各个数字出现的次数。接着从高位向低位遍历3个数字,将出现过的数字按先后顺序拼接成一个3位整数。
3.有如下Python程序段:
n=6;k=0
a=[8,5,8,6,1,8]
f=[0]*10;b=[0]*n
for i in range(n):
　f[a[i]]+=1
　if f[a[i]]!=1:
　　 　b[n-k-1]=a[i]
　　 　k+=1
　else:
　　 　b[i-k]=a[i]
print(b[2])
执行该程序段后,显示的内容为 (　　)
A.1 B.5
C.6 D.8
答案　C
解析　程序的功能是去重。遍历列表a,统计每次数字出现的次数,若不是第1次出现,用变量k进行计数,并将该数存放在最后。若是第1次出现,将该数赋值给b[i-k]。
4.猜数游戏。游戏规则如下:设定一个秘密数,每猜错一次会得到格式为“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")
答案　(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,说明数字正确而位置不正确。
5.先统计每个分数(0~100分)人数,再将全体学生按成绩划分ABCDE五个等级,各等级比例如表所示,每个等级按比例乘以总人数取整,输出各个等级最低分数线。
等级 A等 B等 C等 D等 E等
比例 15% 30% 30% 20% 5%
累计比例
思考:A等是分数最高的前0.15,若总人数为500人,则A等人数为多少 那么B等多少人呢 怎么计算 完成上面表格中人数的计算表达式 程序运行结果如图所示。
等级A最低分数线是92,人数822,占比0.16 等级B最低分数线是75,人数1560,占比0.31 等级C最低分数线是60,人数1530,占比0.3 等级D最低分数线是51,人数912,占比0.18 等级E最低分数线是10,人数246,占比0.05
(1)实现上述功能的Python程序如下,请在划线处填入合适的代码。
(2)程序中加框处代码有错,请改正。
#读取学生成绩到数组a中,代码略
n=len(a)
b=[0]*101
c=[0]*102
dj=[0.15,0.30,0.30,0.20,0.05]
for i in a:
　b[i]+=1
for i in range(100,1,-1):
　①　　　
for i in range(1,len(dj)):
　dj[i]=dj[i]+dj[i-1]
djfs=[0]*5
j=100
p=101
for i in range(len(djfs)):
　while c[j]<=int(dj[i]):
　　　j-=1
　②　　　
　print("等级"+chr(65+i)+"最低分数线是"+str(j)+",人数"+str(t)+",占比"+str(round(t/n,2)))
　p=③　　　
答案　(1)①c[i]=c[i+1]+b[i]　②t=c[j]-c[p]
③j　(2)c[j]解析　本题考查计数语句与前缀和。(1)①将统计100分到当前分数的各个分数的人数之和,如a[99]表示99分和100分的人数之和。②在print语句中有个人数t未赋值,最低分数线是j,p的初值为101,而c[101]的人数为0,因此该等级的人数和为当前分数人数和减去上一档次的人数和,同时得到 ③答案为j。(2)在语句for i in range(len(djfs))中,变量i表示第i个等级,因此第i个等级为dj[i]*n,j的初值为100,每次减去1,表示分数,显然c[j]小于int(dj[i]*n)要继续,等于时表示已经达到要求,退出循环。
6.根据某场馆一天中每位参观者的进馆和出馆时间,可统计该场馆当天人流量的分布情况。每个人进、出馆的时间用一个长度为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)算法一:按时间顺序遍历各个时刻的进出馆人数,判断持续的时间之和
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 tm in a:
　mts =int(tm[:2])*60+int(tm[3:5])
　if tm[5:]=="in":
　　　cnt+=1
　else:
　　　②　　　
　if cnt>sp:
　　　if t==-1:
　　　　t=mts
　elif t>-1:
　　　③　　　
　　　t=-1
print("超过指定人数的总时长:" + str(sum) + "分钟")
(3)算法二:采用桶的思想,将每个时间点看成是一个桶。
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(④　　)
print("超过指定人数的总时长:"+str(sumrs)+"分钟")
print("在馆人数最多时刻为:"+itime+",共"+str(imax)+"人")
答案　(1)3　(2)①i[t+1:]或i[t+1:len(i)]
②cnt-=1　③sum+=mts-t
(3)①rs[m2]-=1　②totrs+=rs[i]
③sumrs+=1　④i%60
解析　本题考查枚举算法、多分支选择结构和桶的算法思想。(1)第1分钟5人,第3、4、5分钟分别在馆人数为7,8,3,后面的都没有超过4人,因此总时长为3分钟。(2)①把前后两个时间分开,分别加上in和out来区分。因此要找到“-”的位置t,当条件i[5:]=="in"不成立时,取出出馆的时间。
②当条件tm[5:]=="in"成立时,表示进馆,否则表示出馆,当前人数cnt应减少一个。③处是一个状态编程,当t值为-1时,表示还没有达到目标人数时状态,条件cnt>sp成立,且t值为-1,表示当前cnt值开始大于目标人数,因此t不是-1时,表示开始时间,当elif t>-1意味着cnt>sp不成立,表示这一段的结束时间,这一段的时间差为mts-t,把这些时间段累加起来。(3)①rs存储早上8点至下午5点每分钟的在馆人数,m2表示出馆的时间,rs[m2]表示该时间的在馆人数,当有一个人出馆时,相应的在馆人数减少一人。②从早上8点开始遍历每分钟在馆人数,并进行累加到变量totrs中。③当累加和超过sp时,相应的时刻增加1个。
7.快递投放。快递根据体积从大到小分为A、B、C三种类型,某快递柜有大、中、小三种类型的格口,投放过程中,A类快递只能投进大格口,B类快递可以投进大、中格口,C类快递三类格口均可投进。
现已知大、中、小三类格口的剩余数量和还未投放的快递类型,编写程序判断能否完成所有快递的投放。
(1)若大、中、小三类格口的剩余数量分别为1、2、3,而还未投放的5个快递类型为["B","B","C","B","C"],则　　　　(选填:能/不能)完成所有快递的投放。
(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。
cab=[3,4,8]　#cab[0]、cab[1]、cab[2]分别表示大、中、小三类格口的剩余数量
pac=["A","C","C","B","C","C","B","C","C","B","B","C","B","A","C"]　#需要投放的快递类型
num=[0,0,0]
for i in range(len(pac)):
　d=①　　　
　num[d]+=1
②　　　　
rest=0
for i in range(3):
　if cab[i]+rest>=num[i]:
　　　③　　　　
　else:
　　　flag=False
　　　break
if flag==True:
　print("能完成投放")
else:
　print("不能完成投放")
答案　(1)能　(2)①ord(pac[i])-ord("A")
flag=True　③rest=cab[i]+rest-num[i]
解析　(1)大格口放1个B类,中格口放2个B类,小格口放3个C类,所有快递均可投放。
(2)①遍历pac列表,统计各种类型快递的数量,d是数组num的下标,因此将快递A、B、C类型转为为下标0、1、2。②初始化投放成功标志flag的初值为True。③cab[i]存储当前类型格口的剩余数量,rest表示上一种类型可用剩余量,num[i]存储当前类型的快递数量。如果条件cab[i]+rest>=num[i]成立,表示当前类型的快递可以存放,计算剩余的格子数rest,以便可以存放下一种类型。
8.某地举办菊花展期间,为提升游客观赏体验,举办方将不同品种的菊花穿插摆放,让游客走最少的路,观赏到尽可能多的品种。编写程序,输入菊花品种的摆放序列(用大写字母标识菊花的品种),输出最长连续不重复品种序列的区间,若有多段,输出最前面那段。如某段展区菊花摆放序列为"ABCABE",则最长连续不重复品种序列的区间为2~5。请回答下列问题:
(1)若某段展区菊花摆放序列为"ABCCDB",最长连续不重复品种序列的区间为　　　　。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
s=input()
index=[-1] *26　#保存字符最后出现的位置
mx=left=start=0
①　　　　
for right in range(n):
　c=s[right]
　t=ord(c)-65
　if index[t]>=left:
　　　left=②　　　　　
　index[t]=right
　③　　　　
　if length>mx:
　　　mx=length
　　　start=left
print("最长连续无重复品种序列的区间为:",start,"~",start+mx-1)
答案　(1)0~2　(2)①n=len(s)　②index[t]+1　③length=right-left+1或length=index[t]-left+1
解析　本题考查滑动窗口算法。(1)最长连续不重复子串为"ABC",对应区间表示为0~2。
(2)①获取输入字符串的长度n为len(s)。②当检测到重复字符时,移动左边界至上次该字符出现位置的下一位,避免重复字符出现在当前窗口内。③计算当前窗口的长度,即连续不重复子串的长度length为right-left+1。
9.如图所示,凹槽内放置了n(3≤n≤15)个高度不等的立方柱,立方柱由多个宽度为1的立方块叠加而成,立方柱之间如果有间隔则可以用来注水。编写程序计算立方柱之间的最大注水体积。首先按柱子高度进行排序,以中间最高柱子为左右边界,和第2高度的柱子构成一个盛水的区域,若两个柱子之间还有柱子,则需要减去这些柱子所占体积,计算注水体积。若第2高度的柱子在左边,则将该柱子作为新的左边界,再向左查找比剩余的最高柱子,再次计算注水体积,依此类推,求出左边和右边的注水体积之和。
若柱子从左至右的高度(0表示无立方柱)依次为“3,0,2,5,0,2,0,4”,位置编号依次为0至7,如图所示,最高柱子编号为3,在右侧第2高度为7号柱子,高度值为4,计算右侧注水体积为3*4*1,更新右侧边界位置right1为7;第3高度柱子在最高柱子位置的左侧,计算左侧注水体积为2*3*1,更新左侧边界位置left1;编号为2和5的柱子介于两个比他高的柱子中间,需减去其体积1*2*1,因此总共注水体积为14。
(1)若h=[2,0,0,5,0,2],则注水的体积为 　　　　。
(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。
#读取每个柱子的高度,存储到列表h中,代码略
n=len(h)
b=[i for i in range(n)]
for i in range(n-1):
　for j in range(n-i-1):
　　　if h[b[j]]　　　　b[j],b[j+1]=b[j+1],b[j]
left1, right1=b[0],b[0]
ans=0
①　　　
while i 　if b[i]　　　ans+=h[b[i]]*(left1-b[i]-1)
　　　②　　　
　elif b[i]>right1:
　　　ans+=h[b[i]]*(b[i]-right1-1)
　　　right1=b[i]
　else:
　　　③　　　
　i+=1
答案　(1)6　(2)①i=1　②left1=b[i]
③ans-=h[i]*1*1或 ans-=h[i]
解析　本题考查数据迭代。 求最大注水体积的方法是:找出最高的次高的柱子,注水的高度由次高柱子高度决定,宽度由两根柱子之间的空间决定,即两根柱子位置差减去1的宽度。题目中先按各柱子的高度从高到低排序,b[0]是最高柱子的位置,只需记录最高柱子位置left1和right1。①变量i从1开始遍历各个柱子,后面的柱子肯定比前面高度小,因此注水的高度即决于当前读取的高度h[b[i]]。②若对应的位置b[i]比right1大,说明该柱子位于最高柱子的右边,宽度为b[i]-right1-1,同时该柱子将成右边为下一次的注水区域的最高高度,因此需更新right1的值。若对应的位置b[i]比left1小,说明该柱子位于最高柱子的左边,宽度为left1-b[i]-1,同时该柱子将成左边为下一次的注水区域的最高高度,因此需更新left1的值。③若读取的b[i]比right1小,比left1大,说明该柱子介于最高柱和次高柱子之间,且高度没有前面的大,因此被淹没在两根柱子之间,该柱子不能注水,注水的体积需减去该柱子的体积h[i]*1*1。
10.某物流公司受委托对客户下单的大件货品进行打包发货。现有三种货品A,B,C,每件货品的打包时间均为半小时。下午12:00开始每隔1时接受一次订单,并非每次都有新订单产生。公司安排的打包工作时间为12:00-18:00,假设当日订单在工作时间内就能完成。公司有甲、乙、丙三位师傅对货品进行打包,货品按照甲、乙、丙的顺序分配给各师傅处理,每位师傅一次打包一件货品。打包规则:若下单时间相同,优先级越高(数字越小,优先级越高)的货品,先全部打包完成;若不同,则下单时间更早的货品先处理完成。
订单输入格式示例:7A2B、4B10A(说明:4B10A指订单中有4件B类货品,10件A类货品)。编写程序,输出某天甲、乙、丙货品打包顺序和打包报酬,甲的输出示例:3A5B1C,200元。
货品 优先级 打包报酬(元/件)
A 1 30
B 2 20
C 3 10
表1
下单时间 货品及数量
12:00 2B7A
14:00 7B
15:00 6B5C
表2
(1)若某天货品下单信息如表2所示,则甲的打包顺序为3A5B1C,乙的打包报酬为　　　　元。
(2)定义如下convert(data)函数,参数data为一个订单,包括货品和数量,函数功能将订单转换成货品名称序列,如订单2B1A1C转换成ABBC。请在划线处填上合适的代码。
def convert(data):
　num,q=0, ""
　qsort=["","",""]
　for i in range(len(data)):
　　　if data[i] >= "0" and data[i] < "9":
　　　　　num=　　　
　　　else:
　　　　　for j in range(num):
　　　　　　q+=data[i]
　　　　　qsort[ord(data[i])-ord("A")]=q
　　　　　num,q=0, ""
　s=qsort[0]+qsort[1]+qsort[2]
　return s
(3)实现该功能的 Python 主程序如下,请在划线处填入合适的代码。
goods=[30,20,10]
m=(18-12)*2　#12:00-18:00之间每半个小时为一个时间节点
b=[]
for i in range(m):
　 b.append("")　#append()用于在列表的末尾添加一个元素
a=[["12:00","2B7A"]["14:00","7B"],["15:00","6B3C"]]
for i in range(len(a)):
　 que=convert(①　　　　)
　 x=(int(a[i][0][0:2])-12)*2　#将时间转换为对应的结点
　 while len(b[x])==3:
　　 　x=x+1
　 while len(que)>0:
　　　 t=3-len(b[x])
　　 　if len(que)　　　　　t=len(que)
　　　b[x]=②　　　
　　　if t==len(que):
　　　　　que=""
　　　else:
　　　　　que=que[t:]
　　　x+=1
s1,salary="",0
for i in range(m):　#甲处理顺序和打包报酬输出
　if b[i]!="":
　　　s1+=b[i][0]
　　　salary+=③　　　
#将s1中形如“ABBCC”的格式,转换成“1A2B2C”的格式,代码略
print("甲处理顺序和打包报酬:", s1, str(salary)+"元")
#乙、丙处理顺序和打包报酬输出略
答案　(1)180　(2)num*10+int(data[i])
(3)①a[i][1]　②b[x]+que[0:t]
③goods[ord(b[i][0])-ord("A")] 或goods[ord(b[i][0])-65]
解析　(1) 12:00下单的货品需1.5个小时,在下一个时间点之前能处理完,因此甲乙丙分别处理3A、2A1B、2A1B,后面2个单子可以合并处理,甲乙丙分别处理5B1C、4B2C、4B2C。(2)取出订单data货品的数量,当数量的值大于9时,如字符串“192”转换成数字192时,依次表示为0+1,10+9,190+2。(3)①遍历若干个订单数据,采用convert(data)函数将参数data订单(如2B1A1C)转换成ABBC的形式。②将当前订单写入队列que中,先找到处理的时间节点x。变量m为每半个小时为一个时间节点数量,b列表记录每个节点甲乙丙打包的货品。当b列表长度为3时,表示每个人都有工作,接下来的货品将在下一个节点完成。若货品序列没放完则需要继续按照时间节点放置,t 表示当前第 x 个时间节点还可以存放货品的个数,将新放入的货品从序列中切出来累加到当前节点 b[x]中去。③在列表中找出对应货品的打包报酬累加到总报酬中。(共95张PPT)
必修一　数据与计算
课时8　桶与索引的算法思想
知识点 学业水平等级
1.能依据解决问题的需求来界定关键问题、抽象建模及设计算法,运用三种控制结构和算法描述方法合理地表示算法。 4
2.理解迭代算法的思想,应用迭代算法处理实际的问题。 4
目 录
CONTENTS
真题剖析
01
知识梳理
02
课堂突破
03
当堂检测
04
课后作业
05
真题剖析
1
　　本节课的目的是提取浙江选考真题的填空题(第13、14和15题)中关于桶和索引算法思想的部分,围绕这个算法思想,并加以练习。数据往往存储在数组的某个位置中,这个位置就是桶的名称,可以表示一类数据。2021年1月浙江选考中,用桶来表示可以容纳多少人的分组名称,就少了查找数据的过程,提高了算法效率。当某个数据集合的元素有多个数据项时,用索引来表示元素的位置,如2023年6月卷第15题,把各个任务下标按完成的先后顺序,依次添加到c数组中,如2024年6月浙江选考“重排”处理数据,将不同位置的数据依次复制到新的位置。
(2024年6月浙江选考)某项活动有n个单位(编号1到n)参加,需将员工分成若干个小组,每个小组的人数上限为m,小组编号按新建次序从1开始编号。分组时,首先按单位编号次序依次在各单位内部分分组,每m人分配到一个新建小组中,不足m人的剩余员工暂不分配;然后按剩余员工人数由大到小的顺序,依次为各单位剩余员工分配小组。若某单位剩余员工人数为k,则分配方法为:在已建的小组中查找空位数(该小组还可容纳的人数)大于或等于k的小组,如果找到的小组有多个,则选择空位数最少的小组,将此k人分配到该小组中;如果没有找到,则新建一个小组,将此k人分配到该小组中。设n为5,m为20,各单位员工人数及单位内部的分组过程
#读取小组人数上限存入m;读取1至n号单位的数据,依次存入列表data的data[0]至data[n-1]中。data[i]包含2个数据项,data[i][0],data[i][1]分别存放单位编号及员工人数,代码略
#对各单位内部进行分组,组号依次存储在a[0]至a[n-1]中,共有gnum个分组代码略
bubble_sort(data)　#根据每个单位的剩余员工人数,对data进行降序排序
b=[[] for i in range(m)]
i=0
while i　　①______
　　while j　　　　j+=1
　　if j　　　　v=b[j].pop()
　　else:
　　　　gnum+=1;v=gnum
　　a[data[i][0]].append(v)
　　 ②______
　　i+=1
#输出各单位的分组编号,代码略
答案　①j=data[i][1] 　②b[j-data[i][1]].append(v)
解析　本题考查桶的算法思想。①新建一个大小为m列表b表示各个分组的剩余人数,b[0]至b[m-1]的初值均为0。对每个单位的剩余员工人数降序排序,并遍历n个单位,首先查找是否存在一个大于等于该单位剩余人数最小分组,其方法是用循环while j知识梳理
2
1.桶是数据结构中一个通用的概念,用来描述一种将数据分________或分类的方法,以便有效地进行查找、排序或分析。
2.桶适用的条件是数据分组的数量是________知的,桶用列表来存储数据,列表的下标就是分组的代号。
3.桶应用第一步是创建一定数量的______桶,如a=[0]*n或a=[[]for i in range(n)]。
4.桶中每个元素可以是一个数值,往往表示该分组中数据的数量,可以是一个逻辑值,表示该分组是否存在,还可以是一个________,往往是多个原始数据集合的下标。
组
已
空
列表
5.桶应用的第二步是分配元素到桶,遍历原数据集合,根据特定的规则,将每个元素放入对应的________中。
6.桶应用的第三步是收集结果,依次从每个________中取出元素,返回原数据集合中的数据。
7.索引是一种用来提高数据访问效率的机制。它通过创建一个新的________来指向原始数据中的位置,从而使得查找、插入和删除等操作能够更快地完成。
桶
桶
列表
课堂突破
3
【典例1】 某学校有n位教职员工,对本单位m条(m大于20)新闻进行投票,选出校园十大新闻,并输出头条新闻的投票者。每位教职员工必须在1至m编号的新闻中,选择10条新闻进行投票。实现的Python程序如下,请将空白处填写完整。
#读取教职员工数量,存储变量n中。
#读取参选新闻数量,存储变量m中。
#读取教职员工数量的投票信息,依次存储到data[0]至data[n-1]中,代码略
number=[[]for i in range(m+1)]
for i in range(len(data)):
　for x in data[i]:
　　　①______
order=[i for i in range(m+1)]　#将1至m新闻编号依次存储在order[1]至order[m]
for i in range(10):　#按投票数量降序选出最大的10个新闻编号
　　for j in range(m,i+1,-1):
　　　if ②________ :
　 　　　order[j],order[j-1]=order[j-1],order[j]
s="头条新闻的投票者有:"
for x in ③________ :
　s+=str(x)+","
#输出校园十大新闻以及头条新闻的投票者,代码略。
答案　①number[x].append(i) 　②len(number[order[j]])>len(number[order[j-1]])
③number[order[1]]
思维点拨
明考向 本题考查桶和索引的算法思想
精点拨 ①初始化了一个名为number的桶,作用是存储每个新闻的投票者编号。遍历投票数据data,第i名投票者有10个投票的编号,将投票者i添加到他所投的桶number[x]。②number数组中存储是各个新闻的投票数量,order是新闻的编号,按投票数量降序选出最大的10个新闻编号,因此比较对象为number[order[j]]和number[order[j-1]],他们的长度越大,说明投票数越多。③经过排序后,order[1]是投票数最多的新闻编号,number[order[1]]中存储了该编号的投票者
【变式1】 抢红包游戏:微信抢红包游戏成为了一代人的经典回忆,游戏将总金额为n的“红包”随机分配给m个玩家,红包的分配需同时满足以下规则:①所有人抢到的金额总和跟总金额n相等;
②每个人至少抢到1分钱;③每个人抢到的金额随机;④每个人抢到金额大小的概率平等。
算法为:将总金额n元乘以100,换算成以分为单位。在[1,100*n-1]范围内随机生成m-1个不重复的点,将区间0至100*n划分为m段,每一段可表示一个红包金额。
实现上述功能的Python程序如下,请在划线处填入合适的代码。
import random
n=int(input("输入红包金额:"))*100
m=int(input("输入红包数量:"))
if m>n:
　　print("游戏无法继续,结束!")
else:
　　f=[False]*(n+1)
　　for i in　①________:
　　　　t=random.randint(1, n-1)
　　　　while f[t]:
　　　　　　t=random.randint(1, n-1)
　　　　f[t]=True
　　②______
　　p,amax=0,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))
答案　①range(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。
【典例2】 有m个人结伴旅行(m<=9,每人用整数1~m编号)。期间既有全员参与的集体活动,也有自主参与的小团队活动。每项活动的消费由参与人平均分摊,其中一人先行垫付并记录。记录内容包括该项活动的人均消费金额(元)、参与人。每项活动的参与人用字符串表示,垫付人排在第1位。如"25134"表示2、5、1、3、4号参与该项活动,其中2号是垫付人。旅行活动结束依据所有活动的消费记录进行结算。要求输出转账明细。(编号小的付款人优先转账给编号小收款人)
(1)若有3个人参加3项活动,每项活动的参与人分别是"31","12","123",每项活动的平均消费金额分别为50元,100元,300元,则3号人员应还款项为________ 元。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
#读取参与活动人员数量m;
#读取n项参加活动人员依次存储在a[0]至a[n-1]中;
#读取每项活动平均金额依次存储在x[0]至x[n-1],代码略。
b=[0 for i in range(m+1)]　#保存应还款数据
for i in range(n):　#根据消费记录计算应还款
　 p=int(a[i][0])
①______
　 for j in range(1,len(a[i])):
　　　p=int(a[i][j])
　　　b[p]+=x[i]
pay=[];rec=[]
for i in ②________:
　if b[i]>0:
　　　pay.append(i)
　elif b[i]<0:
　　　rec.append(i)
j=0
for i in range(len(pay)):
　while j　　　print("用户"+str(pay[i])+"向用户"+str(rec[j])+"支付"+str(-b[rec[j]]))
　　　b[pay[i]]+=b[rec[j]]
　　　j+=1
　if b[pay[i]]>0:
　　　print("用户"+str(pay[i])+"向用户"+str(rec[j])+"支付"+str(b[pay[i]]))
　　　④______
答案　(1)250　(2)①b[p]-=(len(a[i])-1)*x[i] 　②range(1,m+1)或range(len(b))
③b[rec[j]]+b[pay[i]]>=0　④b[rec[j]]+=b[pay[i]]
思维点拨
明考向 本题考查桶的算法思想
精点拨 (1)活动1:3号垫付-50元,1号应付50元;活动2:1号垫付-100元,2号应付100元;活动3:1号垫付-600元,2、3号应付300元,因此3号应款项-50+300=250。(2)①p为第i项活动的垫付人,一共垫付len(a[i])-1人,每人平均消费金额为x[i]元。②遍历b数组,统计编号1至m编号的人员的应还款。③支付金额为正,垫付金额为负,当两者之和大于等于0,表示支付的金额大于等于垫付金额(绝对值),应从支付金额中送去垫付者可以接受的金额,同时j向后移动。④循环结束后,支付的金额肯定小于垫付金额,因此垫付者接受了部分金额(b[pay[i]]),需更新b[rec[j]]的值
【变式2】 编排试场。每个试场有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]　#读取班级数量,存储变量n中。
bj=[3, 2, 1, 4, 6, 5, 7]　#读取每个班级的人数并按人数降序排列,依次存储到num[0]至num[n-1]中,将排序后的班级依次存储到bj[0]至bj[n-1],代码略
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)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人,试场数将增加一个。③与后面的数进行比较,如果小于或等于后面的班级人数,进行交换。
　　若已知某个数据范围,可以对这些数据进行分类分组,并创建一个列表,用下标来表示这些类别,每个元素存储一个类别的数量或内容,在处理这些数据时,只要知道这些数据的类别,就不需要进行查找,依次从每个桶中取出元素,返回原数据集合中的数据。索引是一种用来提高数据访问效率的机制,通过创建一个新的列表来指向原始数据中的位置,从而使得查找、插入和删除等操作能够更快地完成。
当堂检测
4
1.有如下Python程序段:
s1=input("请输入字符串:")
a=[0]*128
for item in s1:
　ch=ord(item)
　a[ch]=a[ch]+1
s2=""
for i in range(len(a)):
　 for j in range(a[i]):
　 　　s2=s2+chr(i)
print(s2)
列表a各元素的初始值都为0,s1中输入的内容为"abs54int"。执行该程序后,程序输出的结果中第5个字符为(　　)
A.n B.s
C.4 D.i
D
解析　利用桶统计字符串s1各个字符的个数,字母ch的ASCII码值作为桶的下标。遍历各个桶的下标i,若该桶a[i]不为0,将桶中各个字符chr(i)拼接到字符串s2中。
2.某Python程序实现的功能:运行程序输入一个四位整数,能够判断该四位整数是否存在数字重复的位。程序代码如下:
n=int(input("请输入一个四位正整数:"))
f=[0]*10
while n>0:
　　y=n%10
　　①______
　　n=n∥10
if ②________:
　　print("有重复的位。")
else:
　　print("没有重复的位。")
划线处的代码应填(　　)
A.①f[y]=1　　 ②sum(f)<4
B.①f[y]+=1 ②sum(f)<4
C.①f[y] =1 ②sum(f)==4
D.①f[y]+=1 ②sum(f)==4
A
解析　本题考查桶的算法思想。表达式n%10的功能是取出个位数,语句n=n∥10的功能是去除个位数。语句f[y]=1的功能是y是否出现过,如果出现为1,没有出现为0。语句f[y]+=1的功能是统计y出现的次数。sum(f)是统计f列表元素之和。
3.有如下Python程序:
s1="0312";s2="ABCDEFGH"
m=0;c=""
for i in range(len(s2)) :
　k=int(s1[i%4])
　m=4*(i∥4)
　c+=s2[k+m]
执行该程序段后,变量c的值是(　　)
A."ADBCADBC" B."ABCDEFGH"
C."AHBGCFDE" D."ADBCEHFG"
D
解析　遍历字符串s2各个位置,当i为0至3时,m的值为0,其余m的值为4,即把字符串s2分成"ABCD"和"EFGH"两段,每段分别取出偏移位置为0,3,1,2的字符。
4.某公司在内部设置了一项彩票。该彩票的规则是:每张彩票上印有3个各不相同的数字,每次在兑奖前公布一个由3个各不相同的数字构成的中奖号码。兑奖时不考虑彩票上的数字和中奖号码中的各个数字出现的位置。共设置3个奖项,一等奖至三等奖,兑奖规则如下表所示。现已知某次的中奖号码和小明买的若干张彩票号码,请写程序帮助小明统计他可以获得多少奖金。
奖项 一等奖 二等奖 三等奖
中奖条件 匹配3个数字 匹配2个数字 匹配1个数字
奖金 500元 300元 100元
(1)某次中奖号码为3,1,8,则号码为1,6,3的彩票可以获得奖金________元。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
w=list(map(int,input("输入中奖号码:").split()))　#输入3个数字并保存到列表list
flag=[0]*14
rst=[0]*4
m=[0,500,300,100]
for i in range(3):
　flag[w[i]]=1
n=int(input("输入彩票数量:"))
for i in range(n):
　①______
　tmp=list(map(int,input().split()))　#输入彩票的3个数字并保存到列表tmp
　for j in range(3):
　　　if ②________:
　　　　cnt+=1
　rst[(4-cnt)%4]+=1
mon=0
for i in range(1,4):
　③______
print("总奖金数为:",mon)
答案　(1)300　(2)①cnt=0　②flag[tmp[j]] ==1　③mon+=rst[i]*m[i]
解析　(1)匹配到2个数字,获二等奖。(2)①变量cnt表示匹配到的数字,对cnt赋初值0。②遍历tmp列表,若tmp[j]的值在flag列表中对应值为1,表示匹配到一个数字。③rst[i]存储各个奖项的数量,m[i]存储对应奖项的获奖金额。
5.字母异位词指两个不同的单词由相同的字母组成,且不区分大小写,但字母出现的位置可以不同。比如"Heart"和"earth"是字母异位词,"apple"和"Paper"不是字母异位词。现编写 Python 程,文本文件“words.txt”中保存着若干对单词组,从文件“words.txt”中读取多对单词组,并判断该组中两个单词是否为字母异位词。
def fs(m, n) :
　cnt=[0]*26
　for i in range(len(m)) :
　　　ch=ord(m[i])
　　　②______
　for i in range(len(n)) :
　　　ch=ord(n[i])
　　　cnt[ch-ord("a")]-=1
　return cnt
#读取words.txt文件中的内容,将其中的单词依次保存在列表text中,代码略。
s1=s2=""
num=len(text)
for i in range(num) :
　s1=text[i][0]
　s2=text[i][1]
　c= ③______
　j=0
　while j　　　if c[j]!=0:
　　　　print(sl,"和",s2,"不是字母异位词")
　　　　break
　　　j+=1
　else:　#在循环正常结束后执行
　　　print(s1,"和",s2,"是字母异位词")
(2)下列程序代码中,加框处的语句________ (选填:能/不能)改写成语句 elif "a"<=k<="z":
答案　(1)①k=chr(ord(k)+32)或k=chr(ord(k)+ord("A")- ord("a"))或 k=k.lower()
②cnt[ch-ord("a")]+=1或 cnt[ch-97]+=1
③fs(change(s1),change(s2))或fs(change(s2),change(s1))　(2)不能
解析　(1)①小写字母的ASCII码值是对应大写字母ASCII码值加上32。②语句cnt=[0]*26定义共26个元素的桶,每个桶分别存储每个字母的数量,因此需将其ASCII值减去97得到0至15的位置。③将s1、s2调用fs。(2)略。
6.某路边有一排照明装饰灯,编号依次为1~n。现发现有多个装饰灯不亮,受维修成本的限制,只对其中的一部分进行维修,维修后保证有k个编号连续的装饰灯能够正常照明。编写程序,根据已损坏的装饰灯编号,输出最少需要维修的装饰灯数量。请回答下列问题:
(1)若路边有10个照明装饰灯(编号1~10),其中编号为1、4、8、10的装饰灯不亮,维修后需保证有6个编号连续的装饰灯能正常照明,则最少需要维修的装饰灯数量是________。
(2)请完成下列划线处的代码。
#输入照明装饰灯的总数n、编号连续的正常照明装饰灯数量k,代码略
#读取不亮的装饰灯编号,存入d,代码略
v=[0]*(n+1);c=[0]*(n+1)
ans=n
for i in ①__________:
　v[d[i]]=1
for i in range(1,n+1):
　c[i]=c[i-1]+v[i]
i=1
while i<=n-k+1:
　last= ②________
　num=c[last]-c[i-1]
　if ③__________:
　　 　ans=num
　i=i+1
print(ans)
答案　(1)1　(2)①range(len(d))　②i+k-1　③num解析　(1)修理编号为4的装饰灯,即可保证2到7号这6个装饰灯正常照明。
(2)①语句v[d[i]]=1统计损坏装饰灯数量,损坏的装饰灯存入d中,需遍历d中所有数据。②数组c统计到当前位置共损坏灯的数量。i表示连续亮灯的开始位置,其最大值为n-k+1。last是连续亮灯的结束位置i+k-1。③连续k个灯的区间内的损坏灯的数量为num,找出最小修理数量ans。
7.某公路由于长期没有维修,路上出现了很多个坑。为了尽快填补好这些坑,交通管理部门决定对m处地段采取交通管制。将该公路看成一条直线,坑就是直线上的坐标点,坑所在的路段需要封控管制。例如某管制路段2~4,需封控2、3、4路段。交管部门为了减少管制路段的长度,希望将这n个坑分成m段(一段可以只有一个坑),使得这m段公路的总长度最小。请你根据n个坑的位置(位置已按照从小到大进行排序),计算管制路段最小的总长度。代码运行效果如图所示。
请回答下列问题:
(1)上图所示的例子中,若将路段数量修改为5,则管制路段总长度为________。
路段数量: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
(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)
答案　(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
1.有如下Python程序段:
a=[7,4,9,4,3]
b=[0]*10;c=[0]*10
for i in a:
　 b[i]+=1
pa=0
for j in range(10):
　for k in range(b[j]):
　　　c[pa]=j
　　　pa+=1
执行以上程序,数组c[0]至c[4]数据依次是(　　)
A.7,9,4,4,3 B.3,4,4,7,9
C.4,4,7,9,3 D.9,7,4,4,3
B
解析　本题考查桶排序。第一个for循环中,语句b[i]+=1的功能是:利用桶对数组a中数据进行计数。桶的下标是有序的,对应数的值,按桶的编号输出各个桶中的数。在第二个循环中,当b[j]值大于0时,开始重复地把j的值依次放在c数组中。
2.有如下Python程序段:
a=[0]*10;s="533774"
for i in s:
　 a[int(i)]=1
ans,n=0,0
i=9
while i>=0 and n<3:
　 　if a[i]==1:
　 　　ans=ans*10+i
　　 　n+=1
　i-=1
print(ans)
运行程序段后,显示的内容是(　　)
A.9876 B.754
C.775 D.7754
B
解析　第一个for循环是统计出现的数字,如果出现过,该数对应下标的a数组值为1,否则为0,并没有统计各个数字出现的次数。接着从高位向低位遍历3个数字,将出现过的数字按先后顺序拼接成一个3位整数。
3.有如下Python程序段:
n=6;k=0
a=[8,5,8,6,1,8]
f=[0]*10;b=[0]*n
for i in range(n):
　f[a[i]]+=1
　if f[a[i]]!=1:
　　 　b[n-k-1]=a[i]
　　 　k+=1
　else:
　　 　b[i-k]=a[i]
print(b[2])
执行该程序段后,显示的内容为 (　　)
A.1 B.5
C.6 D.8
C
解析　程序的功能是去重。遍历列表a,统计每次数字出现的次数,若不是第1次出现,用变量k进行计数,并将该数存放在最后。若是第1次出现,将该数赋值给b[i-k]。
4.猜数游戏。游戏规则如下:设定一个秘密数,每猜错一次会得到格式为“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")
答案　(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,说明数字正确而位置不正确。
5.先统计每个分数(0~100分)人数,再将全体学生按成绩划分ABCDE五个等级,各等级比例如表所示,每个等级按比例乘以总人数取整,输出各个等级最低分数线。
等级 A等 B等 C等 D等 E等
比例 15% 30% 30% 20% 5%
累计比例
等级A最低分数线是92,人数822,占比0.16
等级B最低分数线是75,人数1560,占比0.31
等级C最低分数线是60,人数1530,占比0.3
等级D最低分数线是51,人数912,占比0.18
等级E最低分数线是10,人数246,占比0.05
思考:A等是分数最高的前0.15,若总人数为500人,则A等人数为多少 那么B等多少人呢 怎么计算 完成上面表格中人数的计算表达式 程序运行结果如图所示。
(1)实现上述功能的Python程序如下,请在划线处填入合适的代码。
(2)程序中加框处代码有错,请改正。
#读取学生成绩到数组a中,代码略
n=len(a)
b=[0]*101
c=[0]*102
dj=[0.15,0.30,0.30,0.20,0.05]
for i in a:
　b[i]+=1
for i in range(100,1,-1):
　①______
for i in range(1,len(dj)):
　dj[i]=dj[i]+dj[i-1]
djfs=[0]*5
j=100
p=101
for i in range(len(djfs)):
　　　j-=1
　②______
　print("等级"+chr(65+i)+"最低分数线是"+str(j)+",人数"+str(t)+",占比"+str(round(t/n,2)))
　p=③______
答案　(1)①c[i]=c[i+1]+b[i]　②t=c[j]-c[p] 　③j　(2)c[j]解析　本题考查计数语句与前缀和。(1)①将统计100分到当前分数的各个分数的人数之和,如a[99]表示99分和100分的人数之和。②在print语句中有个人数t未赋值,最低分数线是j,p的初值为101,而c[101]的人数为0,因此该等级的人数和为当前分数人数和减去上一档次的人数和,同时得到 ③答案为j。(2)在语句for i in range(len(djfs))中,变量i表示第i个等级,因此第i个等级为dj[i]*n,j的初值为100,每次减去1,表示分数,显然c[j]小于int(dj[i]*n)要继续,等于时表示已经达到要求,退出循环。
6.根据某场馆一天中每位参观者的进馆和出馆时间,可统计该场馆当天人流量的分布情况。每个人进、出馆的时间用一个长度为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)算法一:按时间顺序遍历各个时刻的进出馆人数,判断持续的时间之和
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 tm in a:
　mts =int(tm[:2])*60+int(tm[3:5])
　if tm[5:]=="in":
　　　cnt+=1
　else:
　　　②______
　if cnt>sp:
　　　if t==-1:
　　　　t=mts
　elif t>-1:
　　　③______
　　　t=-1
print("超过指定人数的总时长:" + str(sum) + "分钟")
(3)算法二:采用桶的思想,将每个时间点看成是一个桶。
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(④____)
print("超过指定人数的总时长:"+str(sumrs)+"分钟")
print("在馆人数最多时刻为:"+itime+",共"+str(imax)+"人")
答案　(1)3　(2)①i[t+1:]或i[t+1:len(i)] 　②cnt-=1　③sum+=mts-t
(3)①rs[m2]-=1　②totrs+=rs[i] 　③sumrs+=1　④i%60
解析　本题考查枚举算法、多分支选择结构和桶的算法思想。(1)第1分钟5人,第3、4、5分钟分别在馆人数为7,8,3,后面的都没有超过4人,因此总时长为3分钟。(2)①把前后两个时间分开,分别加上in和out来区分。因此要找到“-”的位置t,当条件i[5:]=="in"不成立时,取出出馆的时间。②当条件tm[5:]=="in"成立时,表示进馆,否则表示出馆,当前人数cnt应减少一个。③处是一个状态编程,当t值为-1时,表示还没有达到目标人数时状态,条件cnt>sp成立,且t值为-1,表示当前cnt值开始大于目标人数,因此t不是-1时,表示开始时间,当elif t>-1意味着cnt>sp不成立,表示这一段的结束时间,这一段的时间差为mts-t,把这些时间段累加起来。(3)①rs存储早上8点至下午5点每分钟的在馆人数,m2表示出馆的时间,rs[m2]表示该时间的在馆人数,当有一个人出馆时,相应的在馆人数减少一人。②从早上8点开始遍历每分钟在馆人数,并进行累加到变量totrs中。③当累加和超过sp时,相应的时刻增加1个。
7.快递投放。快递根据体积从大到小分为A、B、C三种类型,某快递柜有大、中、小三种类型的格口,投放过程中,A类快递只能投进大格口,B类快递可以投进大、中格口,C类快递三类格口均可投进。
现已知大、中、小三类格口的剩余数量和还未投放的快递类型,编写程序判断能否完成所有快递的投放。
(1)若大、中、小三类格口的剩余数量分别为1、2、3,而还未投放的5个快递类型为["B","B","C","B","C"],则________(选填:能/不能)完成所有快递的投放。
(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。
cab=[3,4,8]　#cab[0]、cab[1]、cab[2]分别表示大、中、小三类格口的剩余数量
pac=["A","C","C","B","C","C","B","C","C","B","B","C","B","A","C"]　#需要投放的快递类型
num=[0,0,0]
for i in range(len(pac)):
　d=①______
　num[d]+=1
②________
rest=0
for i in range(3):
　if cab[i]+rest>=num[i]:
　　　③________
　else:
　　　flag=False
　　　break
if flag==True:
　print("能完成投放")
else:
　print("不能完成投放")
答案　(1)能　(2)①ord(pac[i])-ord("A")　②flag=True　③rest=cab[i]+rest-num[i]
解析　(1)大格口放1个B类,中格口放2个B类,小格口放3个C类,所有快递均可投放。(2)①遍历pac列表,统计各种类型快递的数量,d是数组num的下标,因此将快递A、B、C类型转为为下标0、1、2。②初始化投放成功标志flag的初值为True。③cab[i]存储当前类型格口的剩余数量,rest表示上一种类型可用剩余量,num[i]存储当前类型的快递数量。如果条件cab[i]+rest>=num[i]成立,表示当前类型的快递可以存放,计算剩余的格子数rest,以便可以存放下一种类型。
8.某地举办菊花展期间,为提升游客观赏体验,举办方将不同品种的菊花穿插摆放,让游客走最少的路,观赏到尽可能多的品种。编写程序,输入菊花品种的摆放序列(用大写字母标识菊花的品种),输出最长连续不重复品种序列的区间,若有多段,输出最前面那段。如某段展区菊花摆放序列为"ABCABE",则最长连续不重复品种序列的区间为2~5。请回答下列问题:
(1)若某段展区菊花摆放序列为"ABCCDB",最长连续不重复品种序列的区间为________。
(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
s=input()
index=[-1] *26　#保存字符最后出现的位置
mx=left=start=0
①________
for right in range(n):
　c=s[right]
　t=ord(c)-65
　if index[t]>=left:
　　　left=②__________
　index[t]=right
　③________
　if length>mx:
　　　mx=length
　　　start=left
print("最长连续无重复品种序列的区间为:",start,"~",start+mx-1)
答案　(1)0~2　(2)①n=len(s)　②index[t]+1　
③length=right-left+1或length=index[t]-left+1
解析　本题考查滑动窗口算法。(1)最长连续不重复子串为"ABC",对应区间表示为0~2。(2)①获取输入字符串的长度n为len(s)。②当检测到重复字符时,移动左边界至上次该字符出现位置的下一位,避免重复字符出现在当前窗口内。③计算当前窗口的长度,即连续不重复子串的长度length为right-left+1。
9.如图所示,凹槽内放置了n(3≤n≤15)个高度不等的立方柱,立方柱由多个宽度为1的立方块叠加而成,立方柱之间如果有间隔则可以用来注水。编写程序计算立方柱之间的最大注水体积。首先按柱子高度进行排序,以中间最高柱子为左右边界,和第2高度的柱子构成一个盛水的区域,若两个柱子之间还有柱子,则需要减去这些柱子所占体积,计算注水体积。若第2高度的柱子在左边,则将该柱子作为新的左边界,再向左查找比剩余的最高柱子,再次计算注水体积,依此类推,求出左边和右边的注水体积之和。
若柱子从左至右的高度(0表示无立方柱)依次为“3,0,2,5,0,2,0,4”,位置编号依次为0至7,如图所示,最高柱子编号为3,在右侧第2高度为7号柱子,高度值为4,计算右侧注水体积为3*4*1,更新右侧边界位置right1为7;第3高度柱子在最高柱子位置的左侧,计算左侧注水体积为2*3*1,更新左侧边界位置left1;编号为2和5的柱子介于两个比他高的柱子中间,需减去其体积1*2*1,因此总共注水体积为14。
(1)若h=[2,0,0,5,0,2],则注水的体积为 ________。
(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。
#读取每个柱子的高度,存储到列表h中,代码略
n=len(h)
b=[i for i in range(n)]
for i in range(n-1):
　for j in range(n-i-1):
　　　if h[b[j]]　　　　b[j],b[j+1]=b[j+1],b[j]
left1, right1=b[0],b[0]
ans=0
①______
while i 　if b[i]　　　ans+=h[b[i]]*(left1-b[i]-1)
　　　②______
　elif b[i]>right1:
　　　ans+=h[b[i]]*(b[i]-right1-1)
　　　right1=b[i]
　else:
　　　③______
　i+=1
答案　(1)6　(2)①i=1　②left1=b[i] 　③ans-=h[i]*1*1或 ans-=h[i]
解析　本题考查数据迭代。 求最大注水体积的方法是:找出最高的次高的柱子,注水的高度由次高柱子高度决定,宽度由两根柱子之间的空间决定,即两根柱子位置差减去1的宽度。题目中先按各柱子的高度从高到低排序,b[0]是最高柱子的位置,只需记录最高柱子位置left1和right1。①变量i从1开始遍历各个柱子,后面的柱子肯定比前面高度小,因此注水的高度即决于当前读取的高度h[b[i]]。②若对应的位置b[i]比right1大,说明该柱子位于最高柱子的右边,宽度为b[i]-right1-1,同时该柱子将成右边为下一次的注水区域的最高高度,因此需更新right1的值。若对应的位置b[i]比left1小,说明该柱子位于最高柱子的左边,宽度为left1-b[i]-1,同时该柱子将成左边为下一次的注水区域的最高高度,因此需更新left1的值。③若读取的b[i]比right1小,比left1大,说明该柱子介于最高柱和次高柱子之间,且高度没有前面的大,因此被淹没在两根柱子之间,该柱子不能注水,注水的体积需减去该柱子的体积h[i]*1*1。
10.某物流公司受委托对客户下单的大件货品进行打包发货。现有三种货品A,B,C,每件货品的打包时间均为半小时。下午12:00开始每隔1时接受一次订单,并非每次都有新订单产生。公司安排的打包工作时间为12:00-18:00,假设当日订单在工作时间内就能完成。公司有甲、乙、丙三位师傅对货品进行打包,货品按照甲、乙、丙的顺序分配给各师傅处理,每位师傅一次打包一件货品。打包规则:若下单时间相同,优先级越高(数字越小,优先级越高)的货品,先全部打包完成;若不同,则下单时间更早的货品先处理完成。
订单输入格式示例:7A2B、4B10A(说明:4B10A指订单中有4件B类货品,10件A类货品)。编写程序,输出某天甲、乙、丙货品打包顺序和打包报酬,甲的输出示例:3A5B1C,200元。
表1
货品 优先级 打包报酬(元/件)
A 1 30
B 2 20
C 3 10
下单时间 货品及数量
12:00 2B7A
14:00 7B
15:00 6B5C
表2
(1)若某天货品下单信息如表2所示,则甲的打包顺序为3A5B1C,乙的打包报酬为________元。
(2)定义如下convert(data)函数,参数data为一个订单,包括货品和数量,函数功能将订单转换成货品名称序列,如订单2B1A1C转换成ABBC。请在划线处填上合适的代码。
def convert(data):
　num,q=0, ""
　qsort=["","",""]
　for i in range(len(data)):
　　　if data[i] >= "0" and data[i] < "9":
　　　　　num=______
　　　else:
　　　　　for j in range(num):
　　　　　　q+=data[i]
　　　　　qsort[ord(data[i])-ord("A")]=q
　　　　　num,q=0, ""
　s=qsort[0]+qsort[1]+qsort[2]
　return s
(3)实现该功能的 Python 主程序如下,请在划线处填入合适的代码。
goods=[30,20,10]
m=(18-12)*2　#12:00-18:00之间每半个小时为一个时间节点
b=[]
for i in range(m):
　 b.append("")　#append()用于在列表的末尾添加一个元素
a=[["12:00","2B7A"]["14:00","7B"],["15:00","6B3C"]]
for i in range(len(a)):
　 que=convert(①________)
　 x=(int(a[i][0][0:2])-12)*2　#将时间转换为对应的结点
　 while len(b[x])==3:
　　 　x=x+1
　 while len(que)>0:
　　　 t=3-len(b[x])
　　 　if len(que)　　　　　t=len(que)
　　　b[x]=②______
　　　if t==len(que):
　　　　　que=""
　　　else:
　　　　　que=que[t:]
　　　x+=1
s1,salary="",0
for i in range(m):　#甲处理顺序和打包报酬输出
　if b[i]!="":
　　　s1+=b[i][0]
　　　salary+=③______
#将s1中形如“ABBCC”的格式,转换成“1A2B2C”的格式,代码略
print("甲处理顺序和打包报酬:", s1, str(salary)+"元")
#乙、丙处理顺序和打包报酬输出略
答案　(1)180　(2)num*10+int(data[i]) 　(3)①a[i][1]　②b[x]+que[0:t]
③goods[ord(b[i][0])-ord("A")] 或goods[ord(b[i][0])-65]
解析　(1) 12:00下单的货品需1.5个小时,在下一个时间点之前能处理完,因此甲乙丙分别处理3A、2A1B、2A1B,后面2个单子可以合并处理,甲乙丙分别处理5B1C、4B2C、4B2C。(2)取出订单data货品的数量,当数量的值大于9时,如字符串“192”转换成数字192时,依次表示为0+1,10+9,190+2。(3)①遍历若干个订单数据,采用convert(data)函数将参数data订单(如2B1A1C)转换成ABBC的形式。②将当前订单写入队列que中,先找到处理的时间节点x。变量m为每半个小时为一个时间节点数量,b列表记录每个节点甲乙丙打包的货品。当b列表长度为3时,表示每个人都有工作,接下来的货品将在下一个节点完成。若货品序列没放完则需要继续按照时间节点放置,t 表示当前第 x 个时间节点还可以存放货品的个数,将新放入的货品从序列中切出来累加到当前节点 b[x]中去。③在列表中找出对应货品的打包报酬累加到总报酬中。

展开更多......

收起↑