欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

python——分治策略求最大值和最小值

程序员文章站 2022-05-12 17:27:20
...

最近在学算法,刚入手分治,这是自己的一些心得,记录一下。

分治就是把一个大的问题分成很多小的子问题,不断调用递归将问题分解成多个小问题。以下是个人解题的一些想法:

  1. 分治其实就是递归的一种用途,必须要有递归出口,就是当问题小到一定程度我们可以解决了,可以每次考虑从出口入手问题。
  2. 分治是先分再合,分完后记得还要将问题的解和起来

代码实现

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]))