《算法设计方法》ppt课件

《《算法设计方法》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章算法设计方法11.1分治法11.2动态规划11.3贪心法11.4回朔法11.5分枝限界法11.1分治法对于一个输入规模为n的问题，用某种方法把输入分割成k个子集（11T(n)=T(n)=O(n2)归

2、并排序voidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){//将SR[s..t]归并排序为TR1[s..t]if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1..t]Msort(SR,TR2,s,m,);//递归地将SR[s..m]归并为有序的TR2[s..m]Msort(SR,TR2,m+1,t);//递归地将SR[m+1..t]归并为有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2

3、[m+1..t]归并到TR1[s..t]}}//Msort1n=22T(n/2)+n-1n>2T(n)=T(n)=nlogn-n+1快速排序从输入序列中随机的抽取一个元素a，以a为界，把全体元素分成：S1S2S3{小于a}{等于a}{大于a}若S1、S3排好序了，则全体元素就有序了，而S1、S3的排序又可以用这种方法voidQsort(SqList&L,intlow,inthigh){//对顺序表L中的子表L.r[low..high]作快速排序if(low

4、low..high]一分为二Qsort(L,low,pivotloc-1);//对低子表递归排序，pivotloc是枢轴位置Qsort(L,pivotloc+1,high);//对高子表递归排序}}//QsortT(n)=O(nlog2n)该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题;分治法选用11.2动态规划历史不会重演10F(n)=1ifn=0or1F(n-1)+F(n-2)ifn>1n012

5、345678910F(n)1123581321345589递归算法的伪代码:F(n)1ifn=0orn=1thenreturn12elsereturnF(n-1)+F(n-2)考虑Fibonacci序列F(n)11计算F(7)F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F112计算F(7)计算F(2)重复8次!F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0

6、F2F1F0F1F1F1F113TheexecutionofF(7)计算F(3)重复5次!F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F114计算F(7)多次重复计算!!如何避免?F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F115改进的想法备忘录当F1(i)被计算后,保存它的值当再次计算F1(i)时,只需要从内存中取出即可F1(

7、n)1ifv[n]<0then2v[n]←F1(n-1)+F1(n-2)3returnv[n]Main()1v[0]=v[1]←12fori←2tondo3v[i]=-14outputF1(n)16再计算F(7)11-1-1-1-1-1-1v[0]v[1]v[2]v[3]v[4]v[5]v[6]v[7]F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1F(i)=Fi17再计算F(7)11-1-1-1-1-1-1v[0]v[1]v[2]v[3]v[

8、4]v[5]v[6]v[7]F7F6F5F5F4F3