Python分治法核心原理与九大实战案例解析
发布时间：2026-10-13 |
2人浏览过
本文深入解析Python中的分治法，阐述其四大核心特征及适用场景，并对比贪心与动态规划策略。通过最大值查找、元素检索、第k小元素、快排、归并排序、汉诺塔、爬楼梯、最近点对及组合求和等9个经典案例，提供完整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程序设计有所帮助。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
