简答题 偏难
#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]&gt;=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&lt;=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分)