分治法递归求列表最小值
题目说明
一个列表中存在n个数据,可以用分治算法来找到其中的最小值。具体过程如下:如果列表元素的个数小于等于2的时候,经过一个判断就找到其中的最小值,所以可以先把数据从中间划分为左右两部分,然后通过递归把每一部分再划分为左右两部分,直到数据规模小于等于2的时候,返回结果,然后通过递归到最后为两个数据对比,我们就可以找到最小值。
请根据以上算法过程,补全代码。
# 求列表中小于两个元素的最小值
def get_min(number):
if len(number) == 1:
return ①
else:
if number[1] > number[0]:
return number[0]
else:
return number[1]
def solve(number):
n = len(number)
if n <= 2:
return get_min(number)
else:
# 将整个列表分为左右两部分
left_list, right_list = ② , number[n//2:]
# 递归(树),分治
left_min, right_min = solve(left_list), ③
return get_min([left_min, right_min])
test_list = [5, 11, 3, 2, 7, 9]
print(solve(test_list))
评分标准
-
number[0](2分) -
number[:n//2](3分) -
solve(right_list)(3分)
本题为编程题,提交代码并运行通过测试点后判分。
正在加载题目数据…
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析