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

2023-09-27 11:22:17 47

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

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

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

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

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

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

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

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

#基本子算法（子问题规模小于等于2时）
defget_max(max_list):
returnmax(max_list)#这里偷个懒！
#分治法版本一
defsolve(init_list):
n=len(init_list)
ifn<=2:#若问题规模小于等于2，最终解决
returnget_max(init_list)
#分解（子问题规模为2，最后一个可能为1）
temp_list=(init_list[i:i+2]foriinrange(0,n,2))
#分治，合并
max_list=list(map(get_max,temp_list))
#递归（树）
solve(max_list)
#分治法版本二
defsolve2(init_list):
n=len(init_list)
ifn<=2:#若问题规模小于等于2，解决
returnget_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)
#合并
returnget_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）
defis_in_list(init_list,el):
return[False,True][init_list[0]==el]
#分治法
defsolve(init_list,el):
n=len(init_list)
ifn==1:#若问题规模等于1，直接解决
returnis_in_list(init_list,el)
#分解（子问题规模为n/2）
left_list,right_list=init_list[:n//2],init_list[n//2:]
#递归（树），分治，合并
res=solve(left_list,el)orsolve(right_list,el)
returnres
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），注意：非就地划分
defpartition(seq):
pi=seq[0]#挑选主元
lo=[xforxinseq[1:]ifx<=pi]#所有小的元素
hi=[xforxinseq[1:]ifx>pi]#所有大的元素
returnlo,pi,hi
#查找第k小的元素
defselect(seq,k):
#分解
lo,pi,hi=partition(seq)
m=len(lo)
ifm==k:
returnpi#解决！
elifm
题目4.快速排序
#划分（基于主元pivot），注意：非就地划分
defpartition(seq):
pi=seq[0]#挑选主元
lo=[xforxinseq[1:]ifx<=pi]#所有小的元素
hi=[xforxinseq[1:]ifx>pi]#所有大的元素
returnlo,pi,hi
#快速排序
defquicksort(seq):
#若问题规模小于等于1，解决
iflen(seq)<=1:returnseq
#分解
lo,pi,hi=partition(seq)
#递归（树），分治，合并
returnquicksort(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.合并排序（二分排序）
#合并排序
defmergesort(seq):
#分解（基于中点）
mid=len(seq)//2
left_seq,right_seq=seq[:mid],seq[mid:]
#递归（树），分治
iflen(left_seq)>1:left_seq=mergesort(left_seq)
iflen(right_seq)>1:right_seq=mergesort(right_seq)
#合并
res=[]
whileleft_seqandright_seq:#只要两者皆非空
ifleft_seq[-1]>=right_seq[-1]:#两者尾部较大者，弹出
res.append(left_seq.pop())
else:
res.append(right_seq.pop())
res.reverse()#倒序
return(left_seqorright_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.汉诺塔
#汉诺塔
defmove(n,a,buffer,c):
ifn==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步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
#爬楼梯
defclimb(n=7):
ifn<=2:
returnn
returnclimb(n-1)+climb(n-2)#等价于斐波那契数列！
print(climb(5))#8
print(climb(7))#21


问题8.给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。（最近点对问题）
frommathimportsqrt
#蛮力法
defsolve(points):
n=len(points)
min_d=float("inf")#最小距离：无穷大
min_ps=None#最近点对
foriinrange(n-1):
forjinrange(i+1,n):
d=sqrt((points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2)#两点距离
ifd2]#左侧最近点对
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(lambdap:mid_x-p[0]<=d,left))#中间线左侧的距离<=d的点
right=list(filter(lambdap:p[0]-mid_x<=d,right))#中间线右侧的距离<=d的点
mid_min=[]
forpinleft:
forqinright:
ifabs(p[0]-q[0])<=dandabs(p[1]-q[1])<=d:#如果右侧部分点在p点的(d,2d)之间
td=get_distance((p,q))
iftd<=d:
mid_min=[p,q]#记录p，q点对
d=td#修改最小距离
ifmid_min:
returnmid_min
elifdis_l>dis_r:
returnrmin
else:
returnlmin
#两点距离
defget_distance(min):
returnsqrt((min[0][0]-min[1][0])**2+(min[0][1]-min[1][1])**2)
defdivide_conquer(seq):
seq.sort(key=lambdax:x[0])
res=nearest_dot(seq)
returnres
#测试
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种
'''
#版本一（纯计数）
deffind(seq,s):
n=len(seq)
ifn==1:
return[0,1][seq[0]==s]
ifseq[0]==s:
return1+find(seq[1:],s)
else:
returnfind(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
#版本二（打印）
deffind2(seq,s,tmp=''):
iflen(seq)==0:#终止条件
return
ifseq[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数据结构与算法教程》、《PythonSocket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。

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

热门推荐

随机推荐