Python编程四级 题库
利用分治思想,给定一个顺序表,编写一个求出其最大值的程序。
根据上述算法思想,补全下列代码。
输入输出示例:当顺序表是 [22,13,34,4,68,15,5,58,36],输出:68
def fun_max(num=list):
return max(num)
def fun(num):
n = ①
if n <= 2:
return ②
l_list, r_list = num[:n//2], num[n//2:]
l_max, r_max = ③
return fun_max( ④ )
if __name__ == "__main__":
alist = [22,13,34,4,68,15,5,58,36]
print(fun(alist))
参考程序:
def fun_max(num=list): return max(num) def fun(num): n = len(num) if n <= 2: return fun_max(num) l_list, r_list = num[:n//2], num[n//2:] l_max, r_max = fun(l_list), fun(r_list) return fun_max([l_max, r_max]) if __name__ == "__main__": alist = [22,13,34,4,68,15,5,58,36] print(fun(alist))
评分标准:
① len(num) 或等效答案; (2分)
② fun_max(num) 或等效答案; (2分)
③ fun(l_list), fun(r_list) 或等效答案; (2分)
④ [l_max, r_max] 或等效答案;(2分)
现有n个人依次围成一圈玩游戏,从第1个人开始报数,数到第m个人出局,然后从出局的下一个人开始报数,数到第m个人又出局,...,如此反复到只剩下最后一个是胜利者。设n个人的编号分别为1,2,...,n,打印出局的顺序。
根据上述算法思想,补全下列代码。
输入输出示例:当n=10,m=4,输出如下:
出局的人是: 4
出局的人是: 8
出局的人是: 2
出局的人是: 7
出局的人是: 3
出局的人是: 10
出局的人是: 9
出局的人是: 1
出局的人是: 6
最后胜利者是: 5
def fun(n,k):
L = list( ① )
if n == 1:
return
else:
x = 0
for i in ②
x = ③ - 1
print('出局的人是:',L[x])
del L[x]
if x < 0:
x = 0
print('最后胜利者是:', ④ )
fun(10,4)
参考程序:
def fun(n,k):
L = list(range(1,n+1))
if n == 1:
return
else:
x = 0
for i in range(n-1):
x = (x + k) % len(L) - 1
print('出局的人是:',L[x])
del L[x]
if x < 0:
x = 0
print('最后胜利者是:',L[0])
fun(10,4)评分标准:
① range(1,n+1) 或等效答案;(3分)
② range(n-1): 或等效答案;(3分)
③ (x + k) % len(L) 或等效答案;(3分)
④ L[0] 或等效答案;(3分)
求最小值
利用分治算法,求一个非空整数列表中的最小值。补全以下代码。
算法说明:将列表不断二分,直到子列表长度小于等于2,直接比较得出最小值,然后合并结果(返回两个子列表最小值中的较小者)。
def find_min(nums):
n = len(nums)
# 基线条件:问题规模足够小,直接求解
if n == 1:
return ①
elif n == 2:
return ②
# 分解:将大问题分成两个子问题
mid = n // 2
left_part = nums[:mid]
right_part = nums[mid:]
# 解决:递归求解子问题
left_min = find_min(left_part)
right_min = find_min(right_part)
# 合并:合并子问题的解
return ③
# 测试
test_list = [34, 12, 5, 78, 3, 56, 91, 23]
print('列表中的最小值是:', find_min(test_list))
def find_min(nums):
n = len(nums)
# 基线条件:问题规模足够小,直接求解
if n == 1:
return nums[0]
elif n == 2:
return nums[0] if nums[0] < nums[1] else nums[1]
# 分解:将大问题分成两个子问题
mid = n // 2
left_part = nums[:mid]
right_part = nums[mid:]
# 解决:递归求解子问题
left_min = find_min(left_part)
right_min = find_min(right_part)
# 合并:合并子问题的解
return left_min if left_min < right_min else right_min
# 测试
test_list = [34, 12, 5, 78, 3, 56, 91, 23]
print('列表中的最小值是:',find_min(test_list))① 返回列表唯一元素;
② 比较两个元素并返回较小者;
③ 比较左右两部分的最小值并返回较小者。
递归将原问题分解为规模更小的相同子问题,基线条件处理长度为1或2的情况,避免无限递归。
通过切片将列表分为左右两部分,分别求最小值后合并结果。
二分查找
小明在学习二分查找后,编写程序实现查找key所遍历的过程。如有原始数据是 12, 18, 27, 31, 46, 68, 75, 80, 90, 92,待查找的数据是90,打印输出key所遍历数分别是:
46,80,90。他编写的程序如下,完善划线处的代码。
def dfsearch(data,key): #二分法在data中查找key
p = [] #存放key所遍历数
flag = False
i,j = 0,len(data) - 1
while i <= j:
m = (i+j)//2
p.append(data[m])
if ① :
flag = True
return p,flag
elif data[m] > key:
j = ②
else:
i = ③
return p,flag
data = [12,18,27,31,46,68,75,80,90,92]
key = int(input())
rst,flag = ④
if flag:
print('原始数据是',data,'待查找的数据是',key,'\n找到,查找的数分别是:')
for i in rst:
print(i,end = ',')
else:
print('原始数据是',data,'待查找的数据是',key,'\n没有找到,查找的数分别是:')
for i in rst:
print(i,end = ',')
def dfsearch(data,key):#二分法在data中查找key
p = []#存放key所遍历数
flag = False
i,j = 0,len(data) - 1
while i <= j:
m = (i+j)//2
p.append(data[m])
if data[m] == key:
flag = True
return p,flag
elif data[m] > key:
j = m - 1
else:
i = m + 1
return p,flag
data = [12,18,27,31,46,68,75,80,90,92]
key = int(input())
rst,flag = dfsearch(data, key)
if flag:
print('原始数据是',data,'待查找的数据是',key,'\n找到,查找的数分别是:')
for i in rst:
print(i,end = ',')
else:
print('原始数据是',data,'待查找的数据是',key,'\n没有找到,查找的数分别是:')
for i in rst:
print(i,end = ',')确定二分查找的中间索引计算方式;每次循环计算中点位置并将该位置值加入遍历记录;比较中点值与目标值决定搜索区间:若相等则查找成功并返回;若中点值大于目标值则调整右边界;若中点值小于目标值则调整左边界;循环直到区间无效;最后根据返回标志判断是否找到目标。输入目标值后调用函数获取遍历序列和查找结果,按格式输出过程数据。
密码安全性
密码离不开大家的生活,各类APP中密码设置简单了,就容易造成损失。为此小明编写程序检测密码是否安全。安全密码的两个条件:①密码长度至少8位,②密码中数字、大写字母、小写字母和特殊符号(!@#$%^&*())这四类符号中必须有3项以上。比如,密码是 "ADa%9"(不包括双引号),运行程序后输出"密码不符合安全要求"。利用Python编写程序如下,完善划线处的代码。
def checkpwd(pwd):
c = [0] * 4
flag = False
if len(pwd) >= 8:
①
for i in pwd:
if ② :
c[0] = 1
elif i >='A' and i <= 'Z':
c[1] = 1
elif i >='a' and i <= 'z':
c[2] = 1
elif i in '!@#$%^&*()':
③
if ④ and flag:
return True
else:
return False
pwd = input('请输入密码')
if checkpwd(pwd):
print('密码符合安全要求')
else:
print('密码不符合安全要求')
def checkpwd(pwd):
c = [0] * 4
flag = False
if len(pwd) >= 8:
flag = True
for i in pwd:
if i in '0123456789':
c[0] = 1
elif i >='A' and i <= 'Z':
c[1] = 1
elif i >='a' and i <= 'z':
c[2] = 1
elif i in '!@#$%^&*()':
c[3] = 1
if sum(c) >=3 and flag:
return True
else:
return False
pwd = input('请输入密码')
if checkpwd(pwd):
print('密码符合安全要求')
else:
print('密码不符合安全要求')智能家居系统
在智能家居系统中,我们可以通过中央控制系统来管理各个房间的智能灯。为了简化问题,假设每个房间有一个智能灯,其状态用1表示开,0表示关。我们的任务是计算家里所有开着的灯的数量。我们将采用分治算法的思想来解决这个问题。
请补全以下代码,使用分治算法实现统计列表中开着的灯(值为1)数量的功能。
def count_lights_on(rooms):
# 如果列表为空,直接返回0
if not rooms:
return 0
# 如果列表只有一个元素,直接判断是否为开着的灯
if len(rooms) == 1:
return rooms[0]
# 将列表分为两部分
mid = ①
left_rooms = rooms[:mid]
right_rooms = rooms[mid:]
# 使用分治递归统计每部分开着的灯的数量
count_left = ②
count_right = count_lights_on(right_rooms)
# 返回总开着的灯的数量
return ③
# 示例测试
rooms = [1, 0, 1, 0, 1, 0, 1] # 1代表灯开着,0代表灯关着
print(count_lights_on(rooms)) # 输出应为4
def count_lights_on(rooms): # 如果列表为空,直接返回0 if not rooms: return 0 # 如果列表只有一个元素,直接判断是否为开着的灯 if len(rooms) == 1: return rooms[0] # 将列表分为两部分 mid = len(rooms) // 2 left_rooms = rooms[:mid] right_rooms = rooms[mid:] # 使用分治递归统计每部分开着的灯的数量 count_left = count_lights_on(left_rooms) count_right = count_lights_on(right_rooms) # 返回总开着的灯的数量 return count_left + count_right # 示例测试 rooms = [1, 0, 1, 0, 1, 0, 1] # 1代表灯开着,0代表灯关着 print(count_lights_on(rooms)) # 输出应为4
回文单词
某同学收集了很多单词,不同的单词之间用'-'拼接在一起,如'refer-level-face-',他发现有些单词如level,从左往右读和从右往左读该单词是一样的,称之为回文单词。他想统计他收集的单词中有多少个回文单词。步骤如下:(1)首先将单词按'-'分割出所有单词,(2)统计这些单词中回文单词的数量。编写的Python代码如下,完善划线处的代码。
def revstr(str):
if len(str) == 1:
return ①
else:
return ②
word = 'refer-level-face-'
wordlst = []
s = ''
for t in word:
if t !='-':
③
else:
wordlst.append(s)
s = ''
c = 0
for w in wordlst:
rev = revstr(w)
if ④ :
c += 1
print('对称的字符串个数有',c)def revstr(str):
if len(str) == 1:
return str
else:
return revstr(str[1:]) + str[0]
word = 'refer-level-face-'
wordlst = []
s = ''
for t in word:
if t !='-':
s += t
else:
wordlst.append(s)
s = ''
c = 0
for w in wordlst:
rev = revstr(w)
if w == rev:
c += 1
print('对称的字符串个数有',c)评分标准:
(1)str(或等效答案); (2分)
(2)revstr(str[1:]) + str[0](或等效答案);(3分)
(3)s += t 或 s = s + t(或等效答案); (2分)
(4)w == rev(或等效答案)。(3分)
素数是指大于1的自然数,且只能被1和它本身整除的数。孪生素数是指差值为2的两个素数,例如 (3, 5)、(11, 13) 等。问题:给定一个整数 n,请编写程序输出所有小于等于 n 的孪生素数对,按升序排列。 补全下列程序代码。
def is_prime(num): if ① : return False for i in range(2, num): if ② : return False return ③ def find(n): for i in range(2,n-1): if is_prime(i) and ④ : print(i, i + 2) n = int(input()) find(n)
def is_prime(num): if num < 2: # ① 小于2的数非素数 return False for i in range(2, num): if num % i == 0: # ② 存在因数则非素数 return False return True # ③ 通过所有检查则为素数 def find(n): for i in range(2, n - 1): if is_prime(i) and is_prime(i + 2): # ④ 检查孪生素数对 print(i, i + 2) n = int(input()) find(n)
评分标准:
(1)num < 2 (或等效答案);(3分)
(2)num % i == 0 (或等效答案);(3分)
(3)True (或等效答案);(3分)
(4)is_prime(i+2) (或等效答案)。(3分)
猜价格
爸爸五一旅游回来给小明购买了一文创礼物,问能否用最少的次数猜出礼物的价格。提示该礼物的价格在1-200之间,且是整数。小明编写如下Python程序解决该问题,输出结果中包含猜价格的过程以及猜的次数。请完善划线处的代码。
price = int(input()) #存礼物的实际价格
def sear(p,pmin,pmax):
i = pmin
j = pmax
s = ''
c = 0
while ① :
c = c + 1
m = (i + j)//2
if m == p:
s = s + str(m) + ','
②
elif m < p:
i = m + 1
else:
③
s = s + str(m) + ','
return s,c
pmin = 1
pmax = 200
rst , c = sear(price,pmin,pmax)
print('猜价格的过程是',rst)
print('一共猜了',c,'次就猜对价格')
price = int(input())#存礼物的实际价格
def sear(p,pmin,pmax):
i = pmin
j = pmax
s = ''
c = 0
while i <= j:
c = c + 1
m = (i + j)//2
if m == p:
s = s + str(m) + ','
break
elif m < p:
i = m + 1
else:
j = m - 1
s = s + str(m) + ','
return s,c
pmin = 1
pmax = 200
rst , c = sear(price,pmin,pmax)
print('猜价格的过程是',rst)
print('一共猜了',c,'次就猜对价格')评分标准:
(1)i <= j 或等效答案;(3分)
(2)break 或等效答案;(3分)
(3)j = m - 1 或等效答案。(2分)
垃圾分类
为了响应国家“绿色环保,健康生活”的号召,某小区安装了智能垃圾桶,能自动识别垃圾类型并分类。请你完善以下程序,实现垃圾自动分类功能。recycle = ["纸", "塑料瓶", "玻璃", "金属"]
harmfull = ["电池", "药品", "灯泡", "油漆"]
category = {1: "可回收垃圾", 2: "有害垃圾", 3: "其他垃圾"}
trash_lst = ["烟蒂", "药品", "金属"]
def judge(item):
if ① :
return 1
elif item in harmfull:
return 2
else:
return ②
def classify(trash):#通过字典键获取垃圾类型
i = judge(trash)
return ③
for trash_name in trash_lst:#判断垃圾类型
cate_name = ④ (trash_name)
print(f"{trash_name} 属于: {cate_name}")
输出效果:
烟蒂 属于: 其他垃圾
药品 属于: 有害垃圾
金属 属于: 可回收垃圾
recycle = ["纸", "塑料瓶", "玻璃", "金属"]
harmfull = ["电池", "药品", "灯泡", "油漆"]
category = {1: "可回收垃圾", 2: "有害垃圾", 3: "其他垃圾"}
trash_lst = ["烟蒂", "药品", "金属"]
def judge(item):
if item in recycle:
return 1
elif item in harmfull:
return 2
else:
return 3
def classify(trash):
i = judge(trash)
return category.get(i)
for trash_name in trash_lst:
cate_name = classify(trash_name)
print(f"{trash_name} 属于: {cate_name}")评分标准:
(1)item in recycle 或等效答案;(2分)
(2)3 或等效答案;(4分)
(3)category[i] 或category.get(i) 或等效答案;(4分)
(4)classify或等效答案。(2分)
无人机社团
小明参加了一个无人机社团,现有n架无人机,编号为1, 2, 3, ..., n,依照规则出队执行任务。规则:从队列中按顺序出队第 k 架无人机,直到剩下最后一架无人机时,它将完成最终任务。现在需要计算第m架被出队的无人机的编号,请补充完成该程序。
def solve(n, k, m): if ① : #递归终止条件:当排除第1架时 return (n + k - 1) % ② #计算首轮被排除的位置 else: return (solve( ③ ) + k) % n n, k, m = map(int, input().split()) print( ④ )
参考程序:
def solve(n, k, m): if m == 1: # ① 递归终止条件:当排除第1架时 return (n + k - 1) % n # ② 计算首轮被排除的位置 else: return (solve(n-1, k, m-1) + k) % n # ③ 递归缩小问题规模 n, k, m = map(int, input().split()) print(solve(n, k, m) + 1) # ④ 调整索引偏移(从1开始)
评分标准:
(1)m == 1 (或等效答案);(2分)
(2)n (或等效答案);(2分)
(3)n-1, k, m-1(或等效答案);(2分)
(4)solve(n, k, m) + 1(或等效答案)。(2分)说明:solve(n, k, m)给1分
岩浆活动
2024年,我国科学家通过对嫦娥六号月壤样品的分析研究,发现月球背面某区域的岩浆活动层数呈现递减规律:最上层有n层岩浆活动,下一层岩浆活动层数是上一层的三分之一(向下取整),直到层数小于等于1时停止。
此外,每层岩浆活动有一个厚度值,最上层厚度为t,下一层厚度为上一层的0.5倍。
请完善以下程序,计算该区域的总岩浆活动层数和总厚度。
def moon(n, t):
"""
计算月球某区域的总岩浆活动层数和总厚度
n: 最上层的岩浆活动层数
t: 最上层的岩浆活动厚度
return: (总层数, 总厚度)
"""
if ① :
return 1, t
else:
sub_layers, sub_thickness = moon(n // 3, ② )
return ③ , t + sub_thickness
# 测试代码
n = int(input("请输入最上层的岩浆活动层数:"))
t = float(input("请输入最上层的岩浆活动厚度:"))
total_layers, total_thickness = ④
print(f"该区域的总岩浆活动层数为:{total_layers}")
print(f"该区域的总岩浆活动厚度为:{total_thickness}")参考程序:
def moon(n, t):
"""
计算月球某区域的总岩浆活动层数和总厚度
n: 最上层的岩浆活动层数
t: 最上层的岩浆活动厚度
return: (总层数, 总厚度)
"""
if n <= 1:
return 1, t
else:
sub_layers, sub_thickness = moon(n // 3, t * 0.5)
return n + sub_layers, t + sub_thickness
# 测试代码
n = int(input("请输入最上层的岩浆活动层数:"))
t = float(input("请输入最上层的岩浆活动厚度:"))
total_layers, total_thickness = moon(n, t)
print(f"该区域的总岩浆活动层数为:{total_layers}")
print(f"该区域的总岩浆活动厚度为:{total_thickness}")评分标准:
(1)n <= 1(或等效答案);(2分)
(2)t * 0.5 (或等效答案);(3分)
(3)n + sub_layers (或等效答案);(3分)
(4)moon(n, t)(或等效答案)。(2分)
收费标准
某快递公司对于不同重量的包裹和不同的寄送距离有不同的收费标准。该公司将寄送距离分为两个区间:
在距离 distance 小于或等于 1000 公里时,如果包裹重量weight小于等于 2 千克,收费 base_near 元;如果重量大于 2 千克,超出 2 千克的部分每千克收费 extra_near 元。
在距离大于 1000 公里时,如果包裹重量小于等于 2 千克,收费 base_far 元;如果重量大于 2 千克,超出 2 千克的部分每千克收费 extra_far 元。编写一个函数来计算包裹的快递费用,完善空白处代码。
def courier_fee(weight, distance, base_near, extra__near, base_far, extra_far): if distance <= 1000: if ① : fee = base_near else: ② fee = base_near + extra_charge else: if weight <= 2: fee = ③ else: ④ fee = base_far + extra_charge return fee # 调用函数计算快递费用 result = courier_fee(5, 1500, 10, 3, 15, 5) print(result)
参考程序:
def courier_fee(weight, distance, base_near, extra_near, base_far, extra_far): if distance <= 1000: if weight <= 2: fee = base_near else: extra_charge = (weight-2) * extra_near fee = base_near + extra_charge else: if weight <= 2: fee = base_far else: extra_charge = (weight - 2) * extra_far fee = base_far + extra_charge return fee # 调用函数计算快递费用 result = courier_fee(5, 1500, 10, 3, 15, 5) print(result)
评分标准:
(1)weight <= 2(或等效答案); (2分)
(2)extra_charge = (weight-2) * extra_near(或等效答案); (4分)
(3)base_far(或等效答案); (2分)
(4)extra_charge = (weight - 2) * extra_far (或等效答案)。(4分)
米粒问题
阿凡提与国王比赛下棋,国王说要是自己输了的话阿凡提想要什么他都可以拿得出来。阿凡提说那就要点米吧,棋盘一共64个小格子,在第一个格子里放1粒米,第二个格子里放2粒米,第三个格子里放4粒米,第四个格子里放8粒米,以此类推,后面每个格子里的米都是前一个格子里的2倍,一直把64个格子都放满。需要多少粒米呢?根据题意,请完善划线处的代码。
def fun(n):
x = ①
for i in range(n):
②
return x
s = ③
for i in range(64):
s += fun( ④ )
print(s)
def fun(n): x = 1 for i in range(n): x *= 2 return x s = 0 for i in range(64): s += fun(i) print(s)
评分标准:
(1)1 或等效答案;(3分)
(2)x *= 2 或等效答案;(4分)
(3)0 或等效答案;(3分)
(4)i 或等效答案。(2分)
蜗牛爬行
一只蜗牛在如下图所示的数字方格上移动,已知它只能从标号小的方格移动到标号大的相邻方格。现在请你计算:蜗牛从方格M开始爬到方格N,1<=M<N<=1000,有多少种移动路线?以下用Python编程实现,请你补全代码。

def woniu(m , n):
k = ①
a = [0] * (k+1)
a[1]= 1
a[2]= ②
for i in range(3, ③ ):
a[i]= ④
return a[k]
m = int(input())
n = int(input())
print(woniu(m,n))
def woniu(m , n): k = n - m a = [0] * (k+1) a[1]=1 a[2]=2 for i in range(3,k+1): a[i]=a[i-1]+a[i-2] return a[k] m = int(input()) n = int(input()) print(woniu(m,n))
评分标准:
(1)n – m 或等效答案;(3分)
(2)2 或等效答案;(2分)
(3)k+1 或等效答案;(2分)
(4)a[i-1]+a[i-2] 或等效答案。(3分)