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 res
if __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

题目3. 找出一组序列中的第 k 小的元素，要求线性时间

# 划分（基于主元 pivot），注意：非就地划分
def partition(seq):
  pi = seq[0]              # 挑选主元
  lo = [x for x in seq[1:] if x <= pi] # 所有小的元素
  hi = [x for x in seq[1:] if x > pi]  # 所有大的元素
  return lo, pi, hi
# 查找第 k 小的元素
def select(seq, k):
  # 分解
  lo, pi, hi = partition(seq)
  m = len(lo)
  if m == k:
    return pi        # 解决！
  elif m < k:
    return select(hi, k-m-1) # 递归（树），分治
  else:
    return select(lo, k)   # 递归（树），分治
if __name__ == '__main__':
  seq = [3, 4, 1, 6, 3, 7, 9, 13, 93, 0, 100, 1, 2, 2, 3, 3, 2]
  print(select(seq, 3)) #2
  print(select(seq, 5)) #2

题目4. 快速排序

# 划分（基于主元 pivot），注意：非就地划分
def partition(seq):
  pi = seq[0]              # 挑选主元
  lo = [x for x in seq[1:] if x <= pi] # 所有小的元素
  hi = [x for x in seq[1:] if x > pi]  # 所有大的元素
  return lo, pi, hi
# 快速排序
def quicksort(seq):
  # 若问题规模小于等于1，解决
  if len(seq) <= 1: return seq
  # 分解
  lo, pi, hi = partition(seq)
  # 递归（树），分治，合并
  return quicksort(lo) + [pi] + quicksort(hi)
seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(quicksort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

题目5. 合并排序（二分排序）

# 合并排序
def mergesort(seq):
  # 分解（基于中点）
  mid = len(seq) // 2
  left_seq, right_seq = seq[:mid], seq[mid:]
  # 递归（树），分治
  if len(left_seq) > 1: left_seq = mergesort(left_seq)
  if len(right_seq) > 1: right_seq = mergesort(right_seq)
  # 合并
  res = []
  while left_seq and right_seq:     # 只要两者皆非空
    if left_seq[-1] >= right_seq[-1]: # 两者尾部较大者，弹出
      res.append(left_seq.pop())
    else:
      res.append(right_seq.pop())
  res.reverse()             # 倒序
  return (left_seq or right_seq) + res  # 前面加上剩下的非空的seq
seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(mergesort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

题目6. 汉诺塔

# 汉诺塔
def move(n, a, buffer, c):
  if n == 1:
    print(a,"->",c)
    #return
  else:
    # 递归（线性）
    move(n-1, a, c, buffer)
    move(1, a, buffer, c) # 或者：print(a,"->",c)
    move(n-1, buffer, a, c)
move(3, "a", "b", "c")

问题7. 爬楼梯

假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

# 爬楼梯
def climb(n=7):
  if n <= 2:
    return n
  return climb(n-1) + climb(n-2) # 等价于斐波那契数列！
print(climb(5)) # 8
print(climb(7)) # 21

问题8. 给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。（最近点对问题）

from math import sqrt
# 蛮力法
def solve(points):
  n = len(points)
  min_d = float("inf") # 最小距离：无穷大
  min_ps = None    # 最近点对
  for i in range(n-1):
    for j in range(i+1, n):
      d = sqrt((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2) # 两点距离
      if d < min_d:
        min_d = d            # 修改最小距离
        min_ps = [points[i], points[j]] # 保存最近点对
  return min_ps
# 最接近点对（报错！）
def nearest_dot(seq):
  # 注意：seq事先已对x坐标排序
  n = len(seq)
  if n <= 2: return seq # 若问题规模等于 2，直接解决
  # 分解（子问题规模n/2）
  left, right = seq[0:n//2], seq[n//2:]
  print(left, right)
  mid_x = (left[-1][0] + right[0][0])/2.0
  # 递归，分治
  lmin = (left, nearest_dot(left))[len(left) > 2]  # 左侧最近点对
  rmin = (right, nearest_dot(right))[len(right) > 2] # 右侧最近点对
  # 合并
  dis_l = (float("inf"), get_distance(lmin))[len(lmin) > 1]
  dis_r = (float("inf"), get_distance(rmin))[len(rmin) > 1]
  d = min(dis_l, dis_r)  # 最近点对距离
  # 处理中线附近的带状区域（近似蛮力）
  left = list(filter(lambda p:mid_x - p[0] <= d, left))  #中间线左侧的距离<=d的点
  right = list(filter(lambda p:p[0] - mid_x <= d, right)) #中间线右侧的距离<=d的点
  mid_min = []
  for p in left:
    for q in right:
      if abs(p[0]-q[0])<=d and abs(p[1]-q[1]) <= d:   #如果右侧部分点在p点的(d,2d)之间
        td = get_distance((p,q))
        if td <= d:
          mid_min = [p,q]  # 记录p，q点对
          d = td      # 修改最小距离
  if mid_min:
    return mid_min
  elif dis_l>dis_r:
    return rmin
  else:
    return lmin
# 两点距离
def get_distance(min):
  return sqrt((min[0][0]-min[1][0])**2 + (min[0][1]-min[1][1])**2)
def divide_conquer(seq):
  seq.sort(key=lambda x:x[0])
  res = nearest_dot(seq)
  return res
# 测试
seq=[(0,1),(3,2),(4,3),(5,1),(1,2),(2,1),(6,2),(7,2),(8,3),(4,5),(9,0),(6,4)]
print(solve(seq)) # [(6, 2), (7, 2)]
#print(divide_conquer(seq)) # [(6, 2), (7, 2)]

问题9. 从数组 seq 中找出和为 s 的数值组合，有多少种可能

'''
求一个算法：N个数，用其中M个任意组合相加等于一个已知数X。得出这M个数是哪些数。
比如：
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 # 和
全部可能的数字组合有：
5+9, 6+8
1+4+9, 1+5+8, 1+6+7, 2+3+9, 2+4+8, 2+5+7, 3+4+7, 3+5+6
1+2+5+6, 1+3+4+6, 1+2+4+7, 1+2+3+8, 2+3+4+5
共计15种
'''
# 版本一（纯计数）
def find(seq, s):
  n = len(seq)
  if n==1:
    return [0, 1][seq[0]==s]
  if seq[0]==s:
    return 1 + find(seq[1:], s)
  else:
    return find(seq[1:], s-seq[0]) + find(seq[1:], s)
# 测试
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 # 和
print(find(seq, s)) # 15
seq = [11,23,6,31,8,9,15,20,24,14]
s = 40 # 和
print(find(seq, s)) #8
# 版本二 （打印）
def find2(seq, s, tmp=''):
  if len(seq)==0:  # 终止条件
    return
  if seq[0] == s:        # 找到一种，则
    print(tmp + str(seq[0])) # 打印
  find2(seq[1:], s, tmp)               # 尾递归 ---不含 seq[0] 的情况
  find2(seq[1:], s-seq[0], str(seq[0]) + '+' + tmp)  # 尾递归 ---含 seq[0] 的情况
# 测试
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 # 和
find2(seq, s)
print()
seq = [11,23,6,31,8,9,15,20,24,14]
s = 40 # 和
find2(seq, s)

更多关于Python相关内容可查看本站专题：《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

# Python  # 分治法  # python使用分治法实现求解最大值的方法  # python使用rsa加密算法模块模拟新浪微博登录  # Python算法之栈（stack）的实现  # Python实现的Kmeans++算法实例  # 朴素贝叶斯算法的python实现方法  # python k-近邻算法实例分享  # python实现RSA加密(解密)算法  # 用Python实现通过哈希算法检测图片重复的教程  # python编写的最短路径算法  # python实现simhash算法实例  # Python聚类算法之凝聚层次聚类实例分析  # Python基于DES算法加密解密实例  # 递归  # 点对  # 治法  # 第三条  # 有多少  # 问题是  # 爬楼梯  # 求出  # 第一条  # 第二条  # 两点  # 进阶  # 操作技巧  # 测试数据  # 几个  # 汉诺  # 中间线  # 相关内容  # 你能  # 而不 

相关文章： 金*站制作公司有哪些,金华教育集团官网？  c++如何打印函数堆栈信息_c++ backtrace函数与符号名解析【方法】  制作旅游网站html,怎样注册旅游网站？  开心动漫网站制作软件下载,十分开心动画为何停播？  网站微信制作软件,如何制作微信链接？  建站上市公司网站建设方案与SEO优化服务定制指南  济南网站建设制作公司,室内设计网站一般都有哪些功能？  建站VPS推荐：2025年高性能服务器配置指南  专业公司网站制作公司,用什么语言做企业网站比较好？  制作宣传网站的软件,小红书可以宣传网站吗？  非常酷的网站设计制作软件,酷培ai教育官方网站？  营销式网站制作方案,销售哪个网站招聘效果最好？  宁波免费建站如何选择可靠模板与平台？  存储型VPS适合搭建中小型网站吗？  网站制作报价单模板图片,小松挖机官方网站报价？  相册网站制作软件,图片上的网址怎么复制？  ppt在线制作免费网站推荐,有什么下载免费的ppt模板网站？  网站网页制作专业公司,怎样制作自己的网页？  专业网站建设制作报价,网页设计制作要考什么证？  c# 在ASP.NET Core中管理和取消后台任务  ,巨量百应是干嘛的？  如何快速辨别茅台真假？关键步骤解析  Swift中swift中的switch 语句  如何用AWS免费套餐快速搭建高效网站？  沈阳个人网站制作公司,哪个网站能考到沈阳事业编招聘的信息？  免费制作统计图的网站有哪些,如何看待现如今年轻人买房难的情况？  网站制作公司哪里好做,成都网站制作公司哪家做得比较好，更正规？  建站之星如何优化SEO以实现高效排名？  公司网站的制作公司,企业网站制作基本流程有哪些？  如何在阿里云高效完成企业建站全流程？  建站主机与服务器功能差异如何区分？  Android自定义listview布局实现上拉加载下拉刷新功能  如何在IIS管理器中快速创建并配置网站？  网站制作多少钱一个,建一个论坛网站大约需要多少钱？  建站之星体验版：智能建站系统+响应式设计，多端适配快速建站  网站制作难吗安全吗,做一个网站需要多久时间？  可靠的网站设计制作软件,做网站设计需要什么样的电脑配置？  如何通过虚拟机搭建网站？详细步骤解析  高防网站服务器：DDoS防御与BGP线路的AI智能防护方案  网站制作和推广的区别,想自己建立一个网站做推广，有什么快捷方法马上做好一个网站？  招贴海报怎么做,什么是海报招贴？  如何快速重置建站主机并恢复默认配置？  建站168自助建站系统：快速模板定制与SEO优化指南  惠州网站建设制作推广,惠州市华视达文化传媒有限公司怎么样？  韩国代理服务器如何选？解析IP设置技巧与跨境访问优化指南  广东企业建站网站优化与SEO营销核心策略指南  制作证书网站有哪些,全国城建培训中心证书查询官网？  常州自助建站费用包含哪些项目？  网站制作的方法有哪些,如何将自己制作的网站发布到网上？  桂林网站制作公司有哪些,桂林马拉松怎么报名？