简答题 偏难
#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] &lt; 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 &lt; right_min else right_min # 测试 test_list = [34, 12, 5, 78, 3, 56, 91, 23] print('列表中的最小值是:',find_min(test_list))</pre>
解析

① 返回列表唯一元素;
② 比较两个元素并返回较小者;
③ 比较左右两部分的最小值并返回较小者。
递归将原问题分解为规模更小的相同子问题,基线条件处理长度为1或2的情况,避免无限递归。
通过切片将列表分为左右两部分,分别求最小值后合并结果。