简答题
偏难
#4467
下面的程序运用分治算法寻找列表中的最大值。请将空格补全代码。 #子问题规模小于或等于2时 def zui_da_zhi(a_list): if ① : if a…
下面的程序运用分治算法寻找列表中的最大值。请将空格补全代码。
#子问题规模小于或等于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))
答案与解析
正确答案:<p>参考程序:</p><pre class="brush:python;toolbar:false">#子问题规模小于或等于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))</pre><p><br/></p>
解析
评分标准:
(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分)