|
本文实例讲述了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. 合并排序（二分排序）
| 
转播
