第2章递归与分治(new)ppt课件.ppt

《第2章递归与分治(new)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、书籍推荐Mooc推荐北大张铭老师《数据结构》coursera清华邓俊辉《数据结构》学堂再线stanfordanintroductiontoalgorithmcoursera内容补充voidswap(inta,intb){inttemp;temp=a;a=b;b=temp;}voidswap(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}第2章递归与分治策略学习要点:理解递归的概念。掌握分治法的设计思想。通过范例学习分治策略设计的技巧。分治法的设计思想任何利用计算机求解问题的计算时

2、间都与输入数据的规模有关。问题的规模较小，一般求解较容易。但有时直接解决一个较大问题，是相当困难的。分治法的设计思想将一个难以直接解决的大问题，分割成一些规模较小的相同子问题。分而治之，以便各个击破。然后再利用这些子问题的解，求出原问题的解。§2.1递归的概念递归函数用函数自身给出定义的函数。递归算法直接或间接调用自身的算法。递归技术十分有用，使用递归技术往往使函数的定义和算法的描述简捷且易于理解。例如Fibonacci数列Hanoi塔问题二叉树的定义、遍历算法等例一：整数划分问题将正整数n表示成一系列正整数之和。n=n

3、1+n2+……+nk正整数n的不同划分个数称为正整数n的划分数，记作P(n)整数划分问题就是求出P(n)。分析：求正整数6的划分数n=6n=3+3n=5+1n=3+2+1n=4+2n=3+1+1n=4+1+1…..P(6)=11如何来表示递归关系？记q(n,m)为在n的所有不同划分中，最大加数ni不大于m的划分数。例如：q(6,1)=1即6=1+1+1+1+1+1q(6,2)=4即6=2+2+26=2+2+1+16=2+1+1+1+16=1+1+1+1+1+1q(6,6)=11如何来表示q(n,m)？q(n,1)=1n>

4、=1q(n,m)=q(n,n)m>=n(最大加数不能大于n)q(n,n)=1+q(n,n-1)(n的划分由n1=n的一种划分和ni<=n-1的划分组成)q(n,m)=q(n,m-1)+q(n-m,m)(n的划分由ni<=m-1的划分和n1=m,其余加数ni<=m的划分组成由此，设计计算q(n,m)的递归函数。P(n)=q(n,n)intq(intn,intm){if((n<1)

5、

6、(m<1))return0;if((n==1)

7、

8、(m==1))return1;if(m>n)returnq(n,n);if(m==n)ret

9、urn1+q(n,m-1);returnq(n,m-1)+q(n-m,m);}例二：排列问题字符串的全排序问题描述：给定字符串S[0…N-1],设计算法，枚举该字符串的全排序。如何设计该问题的递归算法？例二：排列问题递归算法：以字符串abcd为例：a–bcdb–acdc–abdd–abc注意：保证每次递归前abcd顺序不变例二：排列问题charstr[]=“abcd”;voidPermutation(intfrom,intto){if(from==to){inti;for(i=0;i<=to;i++){printf("%

10、c",str[i]);}printf("");return;}inti;for(i=from;i<=to;i++){swap(&str[i],&str[from]);Permutation(from+1,to);swap(&str[i],&str[from]);}}intmain(){Permutation(0,strlen(str));return0;}例二：排列问题结果：例二：排列问题如何处理有重复的排列?例如：abbca-bbcb-abcc-bba注意：带重复字符的全排列就是每个字符分别与他后面非重复出现的字符

11、交换。§2.2分治法的基本思想将一个规模为n的问题分解为k个规模较小的相同子问题，这些子问题相互独立且与原问题相同。递归地这些子问题，然后将子问题地解合并得到原问题的解。问题一：把原问题分为多少个子问题才较合适？问题二：子问题的规模是否相同最适当？一般的算法设计模式:Divide-and-conquer(P){if(

12、P

13、

14、rnmerge(y1,y2,…,yk);}分治法的所需的计算时间O(1)n=1T(n)=kT(n/m)+f(n)n>1O(1)n=1T(n)=2T(n/2)+O(n)n>1T(n)=O(nlogn)O(1)n=1T(n)=3T(n/2)+O(n)n>1T(n)=O(nlog3)O(1)n=1T(n)=4T(n/2)+