3.3.2 实践演练——求顺序表中的最大值

为了说明分治算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解分治算法思想在编程中的基本应用。

下面的实例文件zuida.py演示了使用分治算法求顺序表中最大值的过程。

源码路径：daima\第3章\zuida.py

# 基本子算法（子问题规模小于或等于2 时）
def get_max(max_list):
     return max(max_list)  # 这里偷个懒！
# 分治法 版本二
def solve2(init_list):
     n = len(init_list)
     if n <= 2:  # 若问题规模小于或等于2，解决
          return get_max(init_list)
     # 分解（子问题规模为n/2）
     left_list, right_list = init_list[:n // 2], init_list[n // 2:]
     # 递归（树），分治
     left_max, right_max = solve2(left_list), solve2(right_list)
     # 合并
     return get_max([left_max, right_max])
if __name__ == "__main__":
     # 测试数据
     test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
     # 求最大值
     print(solve2(test_list))  # 67

执行后会输出：

67
上一章目录下一章