A48756. 在编写抽奖程序时， 为了保证一个人只有一次中奖机会， 要检查新抽出来的数字是不是已经被抽中过了。一种办法是将已经中过奖的人员编号存放在 test_list 里面， 然后每抽出一个新的人员编号， 判断它是否在中奖人员列表中。如果没有在中奖人员列表中， 说明中奖号码有效， 并将它保存进中奖人员列表； 如果已经在里面了， 就再生成一个新的人员编号。请你补全下面的代码， 实现判断一个数字是否在列表中的功…
填空题
较难
知识点
题目描述
在编写抽奖程序时， 为了保证一个人只有一次中奖机会， 要检查新抽出来的数字是不是
已经被抽中过了。
一种办法是将已经中过奖的人员编号存放在 test_list 里面， 然后每抽出一个新的人员编
号， 判断它是否在中奖人员列表中。
如果没有在中奖人员列表中， 说明中奖号码有效， 并将它保存进中奖人员列表； 如果已
经在里面了， 就再生成一个新的人员编号。
请你补全下面的代码， 实现判断一个数字是否在列表中的功能。
#子问题算法（子问题规模为 1）
def is_in_list(init_list,num):
if init_list[0] == num:
return True
else:
return False
#分治法
def find_out(init_list,num):
n = len(init_list)
if ____①______ ;#如果问题的规模等于1，直接解决
return is_in_list(init_list,num)
#分解（子问题规模为 n/2）
left_list,right_list = _________②____________
#递归， 分治， 合并
res=find_out(left_list,num) __③__ find_out(right_list,num)
return res
if __name__ == "__main__":
#测试数据
test_list = [18,43,21,3,28,2,46,25,32,40,14,36]
#查找
print(_____④_____)
程序运行结果：
True
参考答案
#子问题算法（子问题规模为 1）
def is_in_list(init_list,num):
if init_list[0] == num:
return True
else:
return False
#分治法
def find_out(init_list,num):
n = len(init_list)
if n == 1: #如果问题的规模等于 1， 直接解决
return is_in_list(init_list,num)
#分解（子问题规模为 n/2）
left_list,right_list = init_list[:n//2],init_list[n//2:]
#递归（树）， 分治， 合并
res=find_out(left_list,num) or find_out(right_list,num)
return res
if __name__ == "__main__":
#测试数据
test_list = [18,43,21,3,28,2,46,25,32,40,14,36]
#查找
print(find_out(test_list,25)) #True
上一题
下一题