Python分治法 Python分治法定义与应用实例详解
罗兵 人气:0想了解Python分治法定义与应用实例详解的相关内容吗,罗兵在本文为您仔细讲解Python分治法的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点: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程序设计有所帮助。
加载全部内容