简答题
偏难
#15429
求最小值 利用分治算法,求一个非空整数列表中的最小值。补全以下代码。 算法说明:将列表不断二分,直到子列表长度小于等于2,直接比较得出最小值,然后合并结果(返回…
求最小值
利用分治算法,求一个非空整数列表中的最小值。补全以下代码。
算法说明:将列表不断二分,直到子列表长度小于等于2,直接比较得出最小值,然后合并结果(返回两个子列表最小值中的较小者)。
def find_min(nums):
n = len(nums)
# 基线条件:问题规模足够小,直接求解
if n == 1:
return ①
elif n == 2:
return ②
# 分解:将大问题分成两个子问题
mid = n // 2
left_part = nums[:mid]
right_part = nums[mid:]
# 解决:递归求解子问题
left_min = find_min(left_part)
right_min = find_min(right_part)
# 合并:合并子问题的解
return ③
# 测试
test_list = [34, 12, 5, 78, 3, 56, 91, 23]
print('列表中的最小值是:', find_min(test_list))
答案与解析
正确答案:<pre class="brush:python;toolbar:false;">def find_min(nums):
n = len(nums)
# 基线条件:问题规模足够小,直接求解
if n == 1:
return nums[0]
elif n == 2:
return nums[0] if nums[0] < nums[1] else nums[1]
# 分解:将大问题分成两个子问题
mid = n // 2
left_part = nums[:mid]
right_part = nums[mid:]
# 解决:递归求解子问题
left_min = find_min(left_part)
right_min = find_min(right_part)
# 合并:合并子问题的解
return left_min if left_min < right_min else right_min
# 测试
test_list = [34, 12, 5, 78, 3, 56, 91, 23]
print('列表中的最小值是:',find_min(test_list))</pre>
解析
① 返回列表唯一元素;
② 比较两个元素并返回较小者;
③ 比较左右两部分的最小值并返回较小者。
递归将原问题分解为规模更小的相同子问题,基线条件处理长度为1或2的情况,避免无限递归。
通过切片将列表分为左右两部分,分别求最小值后合并结果。