Python编程四级 题库
递归算法必须确保,需要解决的问题可以转化为一个或多个子问题来求解,这些子问题的求解方法与原问题相同,只是在数量和规模上不同,而且每次递归调用时,问题规模都能够缩小。
递归的核心思想就是自己调用自己,能够用递归解决问题的条件之一,是需要解决的问题可以转化为一个或多个子问题来求解,而这些子问题的求解方法与原问题相同,只是在数量和规模上不同。
Python中自定义函数的函数体中必须要有return语句。( )
递归思想是一种直接或间接地调用自身的算法设计方法,通常用于解决那些问题本身可以被分解为更小的相同类型问题的情况。( )
递归思想是一种直接或间接地调用自身的算法设计方法。
运行以下代码:
def fun(x, y, z): return x + y - z print(fun(1, y=10, 3)
运行结果为:8。( )
混用位置实参和关键字实参,位置实参必须放在关键字实参之前,否则运行程序会报错。
在Python中,函数体return语句之后的代码行都不会被执行,return语句结束整个函数。( )
在Python自定义函数中,一旦执行到return语句,后面的语句就不再执行了。
验证哥德巴赫猜想:任意一个大于等于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分)
下面的程序运用分治算法寻找列表中的最大值。请将空格补全代码。
#子问题规模小于或等于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分)