Python编程四级 题库
要求:设计一个算法,如果一个数从左边读和从右边读都是同一个数,就称为回文数。例如9889就是一个回文数,求对于用户输入的一个非零正整数判断是否为回文数。
根据上述算法思想,补全下列代码。
示例:输入9889,返回9889是回文数;输入34542,返回34542不是回文数。
i=input("请输入一个非零正整数:")
n=len(i)
if ① :
for j in range(int((n+1)/2)):
if ② :
if n==2*j+1:
print("{}是回文数".format(i))
else:
print("{}不是回文数".format(i))
break
else:
for j in ③ :
if i[j]==i[n-j-1]:
if ④ :
print("{}是回文数".format(i))
else:
print("{}不是回文数".format(i))
break
参考答案:
i=input("请输入一个非零正整数:")
n=len(i)
if n%2!=0:
for j in range(int((n+1)/2)):
if i[j]==i[n-j-1]:
if n==2*j+1:
print("{}是回文数".format(i))
else:
print("{}不是回文数".format(i))
break
else:
for j in range(int(n/2)):
if i[j]==i[n-j-1]:
if n==2*(j+1):
print("{}是回文数".format(i))
else:
print("{}不是回文数".format(i))
break评分标准:
① n%2!=0: 或等效答案;(3分)
② i[j]==i[n-j-1]: 或等效答案;(3分)
③ range(int(n/2)) 或等效答案;(2分)
④ n==2*(j+1) 或等效答案;(2分)
任务:利用分治思想,在50个同学成绩(成绩不重复)中查找指定成绩的同学的编号,学生成绩存储在列表cj中;待查找的成绩由键盘输入到变量key中。根据上述算法思想,编写自定义函数完成程序功能,完善空白处代码。
"""
函数名def search(lft,rgt,key)
参数表:整数lft,rgt表示待查找列表的左右边界,key是待查找的成绩
返回值:找到返回key所在编号,否则返回-1.
"""
def search(lft,rgt,key):
if lft>rgt:
return -1
mid = ①
if cj[mid] == key:
return mid
elif ② :
lft = mid + 1
else:
rgt = mid - 1
③
import random
cj = [random.randint(1,100) for i in range(50)]
cj.sort()
key = int(input("输入待查找的成绩"))
pos = search(0,49,key)
print(pos)
参考答案:
def search(lft,rgt,key): if lft>rgt: return -1 mid = (lft+rgt)//2 print(data[mid]) if data[mid] == key: return mid elif data[mid] < key: lft = mid + 1 else: rgt = mid - 1 return search(lft,rgt,key) import random data = [random.randint(1,100) for i in range(50)] data.sort() key = int(input(“输入待查找的成绩”)) pos = search(0,49,key) print(pos)
评分标准:
① (lft+rgt)//2 (2分)
② cj[mid] < key (3分)
③ return search(lft,rgt,key) (3分)
要求:设计一个算法,对于给定两个正整数,求它们的最大公约数。
根据上述算法思想,补全下列代码。
函数名:gcd(x,y)
参数表:x-- 整数x,y-- 整数y。
返回值:它们的最大公约数。
示例:当x=6,y=9时,返回3。
def gcd(x,y):
if ① :
return y
else:
return ②
sums = 0
m = int(input('请输入第一个正整数m = '))
n = int(input('请输入第二个正整数n = '))
sums= ③
print("m和n两个正整数的最大公约数是:%d"% sums)
def gcd(x,y):
if x%y== 0:
return y
else:
return gcd(y,x%y)
sums = 0
m = int(input('请输入第一个正整数m = '))
n = int(input('请输入第二个正整数n = '))
sums=gcd(m,n)
print("m和n两个正整数的最大公约数是:%d"% sums)评分标准:
① x%y== 0或等效答案;(4分)
② gcd(y,x%y) 或等效答案;(4分)
③ gcd(m,n) 或等效答案;(4分)
验证哥德巴赫猜想:任意一个大于等于4的偶数总可以分解为两个素数之和。请在下面的横线上补全代码,使得通过键盘输入一个偶数x(x<1000,输出这两个素数。如果有多组解,只需要输出一组,并且第一个素数要尽可能地小。例如,输入“10”,输出“3 7“;输入“18”,输出“5 13”。
def prime(x):
for i in range(2, x):
if x%i == 0:
return ①
return 1
x=int(input("输入一个偶数x:"))
for k in range( ② ,x//2+1):
if prime(k) and prime( ③ ):
print( ④ )
break
参考程序:
def prime(x):
for i in range(2, x):
if x%i == 0:
return 0
return 1
x=int(input("输入一个数x:"))
for k in range(2,x//2+1):
if prime(k) and prime(x-k):
print(k,x-k)
break评分标准:
(1) 0 或等效答案 ;(3分)
(2) 2 或等效答案 ;(3分)
(3) x-k 或等效答案 ; (3分)
(4) k,x-k 或等效答案 。 (3分)
回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数,例如12321、765567就是回文数。请补全下列代码,编程实现用分治的方法判断一个整数是否是回文数。
def ispel(s):
num = len( ① )
if num == 0:
return False
if num == 1:
return True
if num == 2:
return s[0] == ②
else:
return s[0] == s[num - 1] and ispel(s[1: ③ ])
st = input("请输入一个整数:")
if ④ == True:
print("输入的是回文数")
else:
print("输入的不是回文数")
参考程序:
def ispel(s):
num = len(s)
if num == 0:
return False
if num == 1:
return True
if num == 2:
return s[0] == s[1]
else:
return s[0] == s[num - 1] and ispel(s[1:num - 1])
st = input("请输入一个整数:")
if ispel(st) == True:
print("输入的是回文数")
else:
print("输入的不是回文数")评分标准:
① s或等效答案 ; (2分)
② s[1]或等效答案 ; (2分)
③ num-1或等效答案 ; (2分)
④ ispel(st) 或等效答案。(2分)
小青蛙爬楼梯。楼梯有n级。小青蛙每次只能爬1级或2级。
当楼梯只有1级时,青蛙只有1种爬法。
当楼梯有2级时,青蛙有2种爬法:一次爬2级;一次爬1级,爬2次。
请从键盘上接收楼梯级数n,输出青蛙有几种爬法。
示例输入
请输入楼梯级数:8
示例输出
8级楼梯共有34种爬法。
程序如下:
def Climb(n):
if ① :
return 1
elif n==2:
②
else:
return ③
n=int(input("请输入楼梯级数:"))
if n>0:
print("%d级楼梯共有%d种爬法。"%( ④ , ⑤ ))
参考程序:
def Climb(n):
if n==1:
return 1
elif n==2:
return 2
else:
return Climb(n-1)+Climb(n-2)
n=int(input("请输入楼梯级数:"))
if n>0:
print("%d级楼梯共有%d种爬法。"%(n,Climb(n)))评分标准:
(1)n==1; (2分)
(2)return 2; (2分)
(3)Climb(n-1)+Climb(n-2); (2分)
(4)n; (2分)
(5)Climb(n).(2分)
字符加密。将大写字母逐个按其ASCII值转换为7位二进制数,并在最左边补0,使得每个字母转换为8位二进制数,然后将8位二进制数每四位转为十六进制数。如明文是"CIE",加密后的密文是"434945"。编写的python程序如下,完善划线处的代码。
def xtob(n): #将整数转为二进制数
if n <= 1:
return str(n)
return xtob(n//2)+ ①
mingwen = "CIE"
he = '0123456789ABCDEF'
rst = ''
for c in mingwen:
s = "0" + xtob(ord(c)) #将明文转为8位二进制数
i = 0
data = 0
while i < 8:
data =data * 2 + ②
if (i + 1) % 4 == 0:
rst = rst + he[data]
data = 0
③
print('密文是:',rst)
参考程序:
def xtob(n): #将整数转为二进制数
if n <= 1:
return str(n)
return xtob(n//2)+str(n%2)
mingwen = "CIE"
he = '0123456789ABCDEF'
rst = ''
for c in mingwen:
s = "0" + xtob(ord(c)) #将明文转为8位二进制数
i = 0
data = 0
while i < 8:
data = data * 2 + int(s[i])
if (i + 1) % 4 == 0:
rst = rst + he[data]
data = 0
i += 1
print('密文是:',rst)说明:本题将每个大写字母转换为二进制数,①处代码是递归的方法将十进制转二进制,若整数不是0或1的时候,继续整除2,因此①处代码是xtob(n//2)+str(n%2);8位二进制数每4位二进制数转十六进制数,因此②处的代码是data * 2 + int(s[i]) ;③处的代码是循环变量i自增1,因此该处代码是i=i+1。
评分标准:
(1)str(n%2) ; (4分)
(2)int(s[i]) ; (4分)
(3)i += 1 或i=i+1。 (4分)
辗转相除法求最大公约数,下列函数是用递归算法实现的,请完善横线处的代码。
def gcd(a,b):
m=a%b
if m==0:
return ①
else:
a=b
②
return ③
print(gcd(12,18))
参考程序:
def gcd(a,b): m=a%b if m==0: return b else: a=b b=m return gcd(a,b) print(gcd(12,18))
评分标准:
(1)b; (3分)
(2)b=m;(3分)
(3)gcd(a,b)。(4)
下面的程序运用分治算法寻找列表中的最大值。请将空格补全代码。
#子问题规模小于或等于2时
def zui_da_zhi(a_list):
if ① :
if a_list[0]>=a_list[1]:
most=a_list[0]
else:
most=a_list[1]
else:
most=a_list[0]
return most
# 分治算法排序
def fen_zhi(init_list):
n=len(init_list)
if n<=2: #若问题规模小于或等于2,解决
return zui_da_zhi(init_list)
#分解(子问题规模为n/2)
left_list,right_list= ②
#递归,分治
left_max,right_max= ③
#合并
return zui_da_zhi([left_max,right_max])
#测试数据
test_data=[12,25,4,47,69,5,4,6,37,89,21]
print('最大值为:',fen_zhi(test_data))
参考程序:
#子问题规模小于或等于2时
def zui_da_zhi(a_list):
if len(a_list) == 2:
if a_list[0]>=a_list[1]:
most=a_list[0]
else:
most=a_list[1]
else:
most=a_list[0]
return most
# 分治算法排序
def fen_zhi(init_list):
n=len(init_list)
if n<=2: #若问题规模小于或等于2,解决
return zui_da_zhi(init_list)
#分解(子问题规模为n/2)
left_list,right_list=init_list[:n//2],init_list[n//2:]
#递归,分治
left_max,right_max=fen_zhi(left_list),fen_zhi(right_list)
#合并
return zui_da_zhi([left_max,right_max])
#测试数据
test_data=[12,25,4,47,69,5,4,6,37,89,21]
print('最大值为:',fen_zhi(test_data))评分标准:
(1)len(a_list) == 2; (2分)
(2)init_list[:n//2],init_list[n//2:]; (3分)
(3)fen_zhi(left_list),fen_zhi(right_list)。 (3分)
从键盘接收一组不重复整数,并将这组整数按从小到大的顺序排列。
以下程序采取快速排序法对这组整数进行排序。
快速排序法的原理是:
(1)取这组数据中间那个数为锚定值mid;
(2)从这组数据开头往右找,遇到比mid大的数则停下,位置记为i;
(3)从这组数据末尾往左找,遇到比mid小的数则停下,位置记为j;
(4)如果此时i仍在j左边,即i<=j,则交换这两个数;
(5)重复(2)~(4)直到i、j重合;
(6)对i左边的数进行快速排序;
(7)对右边的数进行快速排序。
输入示例:
请输入需要排序的一组整数,数与数之间用空格隔开:6 10 11 8 4 1 9 7
输出示例:
排序结果:1 4 6 7 8 9 10 11
程序模板:
def QuickSort(left,right):
if ① :
return
mid=Numbers[left+(right-left)//2]
i=left
j=right
while i<j:
while Numbers[i]<mid:
i+=1
while Numbers[j]>mid:
j-=1
if i<=j:
②
QuickSort(left,j-1)
QuickSort(i+1,right)
Numbers=list(map(int,input("请输入需要排序的一组整数,数与数之间用空格隔开:").
③ ))
QuickSort(0, ④ )
print("排序结果:",end="")
for i in Numbers:
print(i,end=" ")
def QuickSort(left,right):
if left>=right:
return
mid=Numbers[left+(right-left)//2]
i=left
j=right
while i<j:
while Numbers[i]<mid:
i+=1
while Numbers[j]>mid:
j-=1
if i<=j:
Numbers[i],Numbers[j]=Numbers[j],Numbers[i]
QuickSort(left,j-1)
QuickSort(i+1,right)
Numbers=list(map(int,input("请输入需要排序的一组整数,数与数之间用空格隔开:").split()))
QuickSort(0,len(Numbers)-1)
print("排序结果:",end="")
for i in Numbers:
print(i,end=" ")评分标准:
(1)left>=right;(2分)
(2)Numbers[i],Numbers[j]=Numbers[j],Numbers[i];(2分)
(3)split();(2分)
(4)len(Numbers)-1。(2分)
鸡兔同笼是中国古代的数学名题之一。大约在1500年前,《孙子算经》中就记载了这个有趣的问题。书中是这样叙述的:
今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何?
意思是:有若干只鸡兔同在一个笼子里(笼中最少有一只鸡和一只兔),从上面数,有35个头,从下面数,有94只脚。问笼中各有多少只鸡和兔?
今天我们用编程的方法来求解一下这道数学命题吧。
def ji_tu(head,leg):
j=0
t=0
while j<head:
j += 1
t = ①
if (leg== ② ):
print('有鸡{}只,有兔子{}只。'.format( ③ ))
return (j,t)
while True:
try:
sum_head=int(input('请输入总头数:'))
sum_leg=int(input('请输入总脚数:'))
if ④ :
print('输入鸡和兔子的总头数或总脚数错误,请重新输入!')
else:
ji_tu( ⑤ )
except:
print('能不能正常输入数据?')
def ji_tu(head,leg):
j=0
t=0
while j<head:
j += 1
t = head-j
if (leg==(j*2+t*4)):
print('有鸡{}只,有兔子{}只。'.format(j,t))
return (j,t)
while True:
try:
sum_head=int(input('请输入总头数:'))
sum_leg=int(input('请输入总脚数:'))
if sum_head<2 or sum_leg<6:
print('输入鸡和兔子的总头数或总脚数错误,请重新输入!')
else:
ji_tu(sum_head,sum_leg)
except:
print('能不能正常输入数据?')评分标准:
(1)head-j; (2分)
(2)(j*2+t*4);(3分)
(3)j,t;(2分)
(4)sum_head<2 or sum_leg<6 ;(3分)
(5)sum_head,sum_leg。(2分)
有一个游戏:有两个人,第一个人先从1和2中挑一个数字,第二个人可以在对方的基础上选择加1或者加2,然后又轮到第一个人,他也可以选择加1或者加2,之后再把选择权交给对方,就这样双方交替地选择加1或者加2,谁先加到20,谁就赢了。
在不考虑谁输谁赢的情况下,从一开始(以1或2为起点)加到20,有多少种不同的递加过程?比如1,4,7,10,12,15,18,20算一种;2,5,8,11,14,17,20又是一种。那么一共会有多少种这样的过程呢?我们可以用递归算法来解决这个问题,请补全代码。
def guo_cheng(n):
if ① :
return 1
return ②
# 输出所有过程的个数
print (guo_cheng( ③ ))
def guo_cheng(n): if n==1 or n==2: return 1 return guo_cheng(n-1)+guo_cheng(n-2) # 输出所有过程的个数 print (guo_cheng(20))
评分标准:
(1)n==1 or n==2; (3分)
(2)guo_cheng(n-1)+guo_cheng(n-2); (4分)
(3)20。(3分)
换位密码法是将明文中的字符位置通过一定的规则重新排列从而得到密文的一种加密方法。某换位密码法加密方法如下:先把明文按照固定长度(4位一组)进行分组,然后对每一组的字符进行换位操作,从而得到密文。例如, 字符串"ceit",使用密钥1432进行加密时,首先将字符串以 4 个字符为一组进行分组,然后对每组的字符进行换位,第1个和第3个字符位置不变,把第2个字符和第4个字符交换位置,从而得到密文"ctie"。小张编写的程序如下,请完善划线处的代码:
def jiami(yw,key):
result = ''
for i in range(0, ① ,len(key)):
s1=yw[i:i+ len(key) ]
for j in range( ② ):
result = result + ③
return result
yw= input('请输入待加密的明文:')
key= input('请输入密钥:')
mw= ④
print(mw)
运行结果如下图所示:
![]()
def jiami(yw,key):
result = ''
for i in range(0,len(yw),len(key)):
s1=yw[i:i+len(key)]
for j in range(len(key)):
result = result + s1[int(key[j])-1]
return result
yw= input('请输入待加密的明文:')
key= input('请输入密钥:')
mw= jiami(yw,key)
print(mw)评分标准:
(1)len(yw);(2分)
(2)len(key);(3分)
(3)s1[int(key[j])-1];(4分)
(4)jiami(yw,key)。(3分)
一张长方形的纸,长m米,宽n米(长宽均为整数),现在要把它刚好裁成一些正方形(边长是整数),有几种裁法,如果要使裁得的正方形面积最大,可以裁多少块。小明学习了递归后,编写程序如下,首先输入长方形的长和宽,计算出结果。请完善划线处的代码:
def tj(a,b):
c = 0
minn = ①
if a > b:
minn = b
for i in range(1,minn+1):
if a % i == 0 and b % i == 0:
c = ②
return c
def gcd(a,b):
if b == 0:
return a
return ③
chang = int(input('输入长方形的长 (单位cm)'))
kuan = int(input('输入长方形的宽 (单位cm)'))
bianchang = gcd(chang,kuan)
total = ④
num = tj(chang,kuan)
print('------------结果如下-------------')
print('有{}种裁法'.format(num))
print('裁得的正方形面积最大边长是{}cm,可以裁{}块'.format(bianchang,total))
运行后的结果如下图所示:


评分标准:
(1)a;(2分)
(2)c + 1;(2分)
(3)gcd(b,a%b);(3分)
(4)(chang // bianchang) * (kuan // bianchang)或等价答案。(3分)
商超采用会员制,客户的消费信息如会员号、姓名和积分如下表所示,小方的爸爸想编写一个客户信息管理系统,其中有一个功能是:输入会员号,查询该会员的积分。

小方知道后,就跃跃欲试,他首先从数据库读取客户信息到列表data中,其中data[i][0]存储第i条记录的会员号,data[i][1]存储第i条记录的姓名,data[i][2]存储第i条记录的积分;他首先将数组data中数据按会员号升序排序,然后用二分查找算法查找会员号对应的积分信息。代码如下,完善划线处的代码:
def bubble_sort(d):
for i in range(len(d)-2):
for j in range(len(d)-1, ① ,-1):
if d[j][0] < d[j-1][0]:
d[j],d[j-1] = d[j-1],d[j]
def bin_ search(d, key):
i,j = 0, len(d)-1
while i <= j:
m=(i +j)//2
if ② :
return m
if key > d[m][0]:
i = m+1
else:
j = m-1
return -1
#从数据库读取会员信息存列表data中,代码略
data=[[8011,'张飞',12345],[8012,'李强',34512],[7812,'李好',45321]]
bubble_sort(data)
key = int(input('输入会员号:'))
m = ③
if m!=-1:
print (data[m][1],'先生/女士:您的积分是:',data[m][2])
else:
print('该会员号不正确')
def bubble_sort(d):
for i in range(len(d)-2):
for j in range(len(d)-1, i,-1):
if d[j][0] < d[j-1][0]:
d[j],d[j-1] = d[j-1],d[j]
def bin_search(d, key):
i,j = 0, len(d)-1
while i <= j:
m=(i +j)//2
if d[m][0] == key:
return m
if key > d[m][0]:
i = m+1
else:
j = m-1
return -1
#从数据库读取会员信息存列表data中,代码略
data=[[8011,'张飞',12345],[8012,'李强',34512],[7812,'李好',45321]]
bubble_sort(data)
key = int(input('输入会员号:'))
m = bin_search(data,key)
if m!=-1:
print (data[m][1],'先生/女士:您的积分是:',data[m][2])
else:
print('该会员号不正确')评分标准:
(1)i;(2分)
(2)d[m][0] == key;(3分)
(3)bin_search(data,key)。(3分)
已知某c的第n项计算步骤如下:

小明编写程序计算第n项的结果。首先从键盘输入n,然后利用上述递推关系计算结果,请完善划线处的代码。
def fc(n):
if n ==1:
①
else:
a=6*n-1
b=8*n+3
return ②
m=int(input("请输入一个整数:"))
if not isinstance(m,int): #判断输入的m是否为整数
print('请输入一个整数')
else:
print( ③ )
#参考程序:
def fc(n):
if n ==1:
return 1
else:
a=6*n-1
b=8*n+3
return a*fc(n-1)/b
m=int(input("请输入一个整数:"))
if not isinstance(m,int): #判断输入的m是否为整数
print('请输入一个整数')
else:
print(fc(m))评分标准:
(1)return 1;(3分)
(2)a*fc(n-1)/b;(3分)
(3)fc(m)。(2分)
说明:本题中已知c的第n项计算公式,第1项时c的值为1,第2项可以由第1项的基础上用公式计算,程序中编写了函数fc实现计算c的结果,在函数fc中,第1项时返回1,故①处代码是return 1 ;函数fc中②处代码是计算第n的数据,由递推公式可知该处代码是a*fc(n-1)/b ,③处代码是将输入的第m项调用函数fc计算结果,故该处的代码是fc(m)。
请补全下列代码,编程实现用递归的方法输出九九乘法表。

def get_result(num):
if num == 1:
print(" ① ")
else:
get_result( ② )
for i in range(1, ③ ):
print("%d * %d = %d" % (i, num, i * num), end=" ")
print()
get_result( ④ )
#参考程序:
def get_result(num):
if num == 1:
print("1 * 1 = 1")
else:
get_result(num - 1)
for i in range(1,num + 1):
print("%d * %d = %d" % (i, num, i * num), end=" ")
print()
get_result(9)评分标准:
(1)1*1=1;(3分)
(2)num-1;(3分)
(3)num+1;(2分)
(4)9。(2分)
有一只蜗牛在井底,井深n米。蜗牛每天往上爬a米,又会往回滑b米。
请从键盘接收输入整数n,a,b,用空格隔开。
并完成下列程序,计算蜗牛爬出这口井需要几天。
n,a,b=input("请输入井深,蜗牛每天往上爬几米,蜗牛滑下几米:"). ①
n,a,b= ②
pos=0
i=0
while ③ :
④
⑤
print("第%d天,蜗牛距离井口%d米;"%(i,n-pos))
print("第%d天,蜗牛成功离开了深井!!"%( ⑥ ))
#参考程序:
n,a,b=input("请输入井深,蜗牛每天往上爬几米,蜗牛滑下几米:").split()
n,a,b=int(n),int(a),int(b)
pos=0
i=0
while pos+a<n:
i+=1
pos+=(a-b)
print("第%d天,蜗牛距离井口%d米;"%(i,n-pos))
print("第%d天,蜗牛成功离开了深井!!"%(i+1))评分标准:
(1)split();(2分)
(2)int(n),int(a),int(b);(2分)
(3)pos+a<n;(2分)
(4)i+=1;(2分)
(5)pos+=(a-b);(2分)
(6)i+1。(2分)
从键盘上分别输入要查找和替换的字符串,对文本文件进行查找与替换,替换后保存到新的文本文件中。
思路:输入待查找字符串s,需查找子字符串key和替换字符串new,通过调用自定义函数replace实现替换。完善划线处代码。
s = input("请输入待查找的字符串:")
key = input("请输入需查找的子字符串:")
new = input("请输入要替换的字符串:")
def findstr(key, s, begin):
for i in range(begin,len(s) - len(key) + 1):
if s[i: ① ]== key:
return i
return -1
def replace(key, new, s):
begin = 0
while begin < ② :
pos = findstr(key,s, begin)
if pos ==-1:
break
else:
s = s[0:pos]+ new + s[pos + len(key): ③ ]
begin = pos + len(key)
return s
rst = ④ #调用函数替换字符
print(rst)
#参考程序:
s = input("请输入待查找的字符串:")
key = input("请输入需查找的子字符串:")
new = input("请输入要替换的字符串:")
def findstr(key, s, begin):
for i in range(begin,len(s) - len(key) + 1):
if s[i:i+len(key)]== key:
return i
return -1
def replace(key, new, s):
begin = 0
while begin < len(s)-len(key)+ 1:
pos = findstr(key,s, begin)
if pos ==-1:
break
else:
s = s[0:pos]+ new + s[pos + len(key):len(s)]
begin = pos + len(key)
return s
rst = replace(key,new,s) #调用函数替换字符
print(rst)评分标准:
(1)i+len(key) 或等价答案;(3分)
(2)len(s)-len(key)+ 1 或等价答案;(3分)
(3)len(s) 或等价答案;(3分)
(4)replace(key,new,s) 或等价答案。(3分)
一个列表中存在n个数据,可以用分治算法来找到其中的最小值。具体过程如下:如果列表元素的个数小于等于2的时候,经过一个判断就找到其中的最小值,所以可以先把数据从中间划分为左右两部分,然后通过递归把每一部分再划分为左右两部分,直到数据规模小于等于2的时候,返回结果,然后通过递归到最后为两个数据对比,我们就可以找到最小值。
请根据以上算法过程,补全代码。
# 求列表中小于两个元素的最小值
def get_min(number):
if len(number) == 1:
return ①
else:
if number[1] > number[0]:
return number[0]
else:
return number[1]
def solve(number):
n = len(number)
if n <= 2:
return get_min(number)
else:
# 将整个列表分为左右两部分
left_list, right_list = ② , number[n//2:]
# 递归(树),分治
left_min, right_min = solve(left_list), ③
return get_min([left_min, right_min])
test_list = [5, 11, 3, 2, 7, 9]
print(solve(test_list))
#参考程序: # 求列表中小于两个元素的最小值 def get_min(number): if len(number) == 1: return number[0] else: if number[1] > number[0]: return number[0] else: return number[1] def solve(number): n = len(number) if n <= 2: return get_min(number) else: # 将整个列表分为左右两部分 left_list, right_list = number[:n//2], number[n//2:] # 递归(树),分治 left_min, right_min = solve(left_list), solve(right_list) return get_min([left_min, right_min]) test_list = [5, 11, 3, 2, 7, 9] print(solve(test_list))
评分标准:
(1)number[0];(2分)
(2)number[:n//2];(3分)
(3)solve(right_list)。(3分)