python——分治策略求最大值和最小值
程序员文章站
2022-05-12 17:27:20
...
最近在学算法,刚入手分治,这是自己的一些心得,记录一下。
分治就是把一个大的问题分成很多小的子问题,不断调用递归将问题分解成多个小问题。以下是个人解题的一些想法:
- 分治其实就是递归的一种用途,必须要有递归出口,就是当问题小到一定程度我们可以解决了,可以每次考虑从出口入手问题。
- 分治是先分再合,分完后记得还要将问题的解和起来
代码实现
def maxmin(l, low, high):
# 判断列表分到最后只剩下一个或者两个数时就比较
# 返回的是一个列表[max,min],第一个最大值,第二个最小值
if high - low <= 1:
if l[low] < l[high]:
return [l[high], l[low]]
else:
return [l[low], l[high]]
# 选取分治的中点
mid = (low + high) // 2
# 调用递归
left_list = maxmin(l, low, mid)
right_list = maxmin(l, mid + 1, high)
# 将左边的最大值和右边的最大值比较
if left_list[0] > right_list[0]:
# 将左边的最小值和右边最小值比较
if left_list[1] > right_list[1]:
# 返回列表[max,min]
return [left_list[0], right_list[1]]
else:
return [left_list[0], left_list[1]]
else:
if left_list[1] > right_list[1]:
return [right_list[0], right_list[1]]
else:
return [right_list[0], left_list[1]]
test_list = [1, 5, 7, 15, 8, 6, 4, 2, 0, 20]
num = maxmin(test_list, 0, len(test_list) - 1)
print("最大值:%d,最小值%d" % (num[0], num[1]))
上一篇: sort排序
下一篇: P1271 【深基9.例1】选举学生会
推荐阅读