Python分治法定义与应用实例详解

本文实例讲述了Python分治法定义与应用。分享给大家供大家参考，具体如下：

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

题目1. 给定一个顺序表，编写一个求出其最大值的分治算法。

# 基本子算法（子问题规模小于等于 2 时）def get_max(max_list):  return max(max_list) # 这里偷个懒！# 分治法 版本一def solve(init_list):  n = len(init_list)  if n <= 2: # 若问题规模小于等于 2，最终解决    return get_max(init_list)  # 分解（子问题规模为 2，最后一个可能为 1）  temp_list=(init_list[i:i+2] for i in range(0, n, 2))  # 分治，合并  max_list = list(map(get_max, temp_list))  # 递归（树）  solve(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(solve(test_list)) # 67  print(solve2(test_list)) # 67

题目2. 给定一个顺序表，判断某个元素是否在其中。

# 子问题算法（子问题规模为 1）def is_in_list(init_list, el):  return [False, True][init_list[0] == el]# 分治法def solve(init_list, el):  n = len(init_list)  if n == 1: # 若问题规模等于 1，直接解决    return is_in_list(init_list, el)  # 分解（子问题规模为 n/2）  left_list, right_list = init_list[:n//2], init_list[n//2:]  # 递归（树），分治，合并  res = solve(left_list, el) or solve(right_list, el)  return resif __name__ == "__main__":  # 测试数据  test_list = [12,2,23,45,67,3,2,4,45,63,24,23]  # 查找  print(solve2(test_list, 45)) # True  print(solve2(test_list, 5)) # False