A17883. 求最小值利用分治算法，求一个非空整数列表中的最小值。补全以下代码。算法说明：将列表不断二分，直到子列表长度小于等于2，直接比较得出最小值，然后合并结果（返回两个子列表最小值中的较小者）。def find_min(nums): n = len(nums) # 基线条件：问题规模足够小，直接求解 if n == 1: return ① elif n == 2: return ② # 分解：将大问题分…
填空题
较难
知识点
题目描述
求最小值
利用分治算法，求一个非空整数列表中的最小值。补全以下代码。
算法说明：将列表不断二分，直到子列表长度小于等于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))参考答案
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))
上一题
下一题