简答题 偏难
#6607

在编写抽奖程序时,为了保证一个人只有一次中奖机会,要检查新抽出来的数字是不是已经被抽中过了。 一种办法是将已经中过奖的人员编号存放在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

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p>(1) n==1:   或其他正确答案; (2分)</p><p>(2) init_list[:n//2],init_list[n//2:]    或其他正确答案; (2分)</p><p>(3) or    或其他正确答案; (2分)</p><p>(4) find_out(test_list,25)    或其他正确答案。 (2分)  </p>
解析

参考程序:

#子问题算法(子问题规模为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