第4章--递归算法(C--版).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 递归算法,前面已经介绍了关于递归调用这样一种操作，而递归程序设计是,C+,语言程序设计中的一种重要的方法，它使许多复杂的问题变得简单，容易解决了。递归特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。,【例1】,给定,n,（,n,=1）,用递归的方法计算1+2+3+4+.+(n-1)+n。,【算法分析】,本题可以用递归方法求解，其原因在于它符合递归的三个条件：,(1)本题是累加问题：当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同s(n)=s(n-1)+n;,(2)给定n,所以是有限次的递归调用；,(3)结束条件是当,n,=1，则,s,=1。,【参考程序】,#include,using namespace std;,int fac(int);/递归函数,int main(),int t;,cint;/输入t的值,couts=fac(t)endl;/计算1到t的累加和，输出结果,int fac(int n),if(n=1)return 1;,return,(fac(n-1)+n);,/调用下一层递归,运行程序，当,T=5,时，输出结果：,S=15,，其递归调用执行过程是：（设,T=3,）,递归调用过程，实质上是不断调用过程或函数的过程，由于递归调用一次，所有子程序的变量（局部变量、变参等）、地址在计算机内部都有用特殊的管理方法,栈（先进后出）来管理，一旦递归调用结束，计算机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。,【例2】,设有N个数已经按从大到小的顺序排列，现在输入X，判断它是否在这N个数中，如果存在则输出：“YES”否则输出“NO”。,【算法分析】,该问题属于数据的查找问题，数据查找有多种方法，通常方法是：顺序查找和二分查找，当N个数排好序时，用二分查找方法速度大大加快。二分查找算法：,（1）设有N个数，存放在A数组中，待查找数为X，用,L,指向数据的高端，用R指向数据的低端，MID指向中间：,（2）若X=AMID 输出“YES”；,（3）若XAMID则到数据前半段查找：,L,不变，R=MID-1，计算新的MID值，并进行新的一段查找；,（5）若,L,R都没有查找到，则输出“NO”。,该算法符合递归程序设计的基本规律，可以用递归方法设计。,【参考程序】,#include,#include,using namespace std;,int a11;,void search(int,int,int);,int main(),/主程序,int k,x,L,=1,R,=10;,cout输入10个从大到小顺序的数：endl;,for(k=1;kak;,cinx;,search(x,L,R,);,system(pause);,void search(int x,int top,int bot)/二分查找递归过程,int mid;,if(top=bot),mid=(top+bot)/2;/求中间数的位置,if(x=amid)cout“YES”endl;/找到就输出,else,if(xamid)search(x,mid+1,bot);/判断在前半段还是后半段查找,else search(x,top,mid-1);,else coutNOC;,(2),当,N=2,时，则需要移动三次：,A-1-B,A-2-C,B-1-C.,(3),如果,N=3,，则具体移动步骤为：,假设把第,3,步，第,4,步，第,7,步抽出来就相当于,N=2,的情况（把上面,2,片捆在一起，视为一片）：,所以可按“N=2”的移动步骤设计：,如果N=0，则退出，即结束程序;否则继续往下执行;,用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程mov(n-1,a,b,c);,将A柱上剩下的一片直接移到C柱上;,用A柱作为协助过渡，将B柱上的（N-1）移到C柱上，调用过程mov(n-1,b,c,a)。,【参考程序】,#include,using namespace std;,int k=0,n;,void mov(int n,char a,char c,char b),/用b柱作为协助过渡，将a柱上的（n）移到c柱上,if(n=0)return;/如果n=0，则退出，即结束程序,mov(n-1,a,b,c);/用c柱作为协助过渡，将a柱上的（n-1）片移到b柱上,k+;,cout cendl;,/,超时改,scanf,和,printf,mov(n-1,b,c,a);,/用a柱作为协助过渡，将b柱上的（n-1）移到c柱上,int main(),coutn;,mov(n,a,c,b);,程序定义了把,n,片从,A,柱移到,C,柱的过程,mov,(,n,a,c,b,),，这个过程把移动分为以下三步来进行：,先调用过程,mov(n-1,a,b,c),，把,(n-1),片从,A,柱移到,B,柱,C,柱作为过渡柱,;,直接执行,cout(a,-,c),，把,A,柱上剩下的一片直接移到,C,柱上，,;,调用,mov(n-1,b,c,a,),，把,B,柱上的,(n-1),片从,B,移到,C,柱上，,A,柱是过渡柱。,对于,B,柱上的,(n-1),片如何移到,C,柱，仍然调用上述的三步。只是把,(n-1),当成了,n,，每调用一次，要移到目标柱上的片数,N,就减少了一片，直至减少到,n=0,时就退出，不再调用。,exit,是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。,mov,过程中出现了自己调用自己的情况，在,C+,中称为递归调用，这是,C+,语言的一个特色。对于没有递归调用功能的程序设计语言，则需要将递归过程重新设计为非递归过程的程序。,【,例,4】,用递归的方法求斐波那契数列中的第,N,个数,【参考程序】,#include,using namespace std;,int a11;,int fib(int);,int main(),int m;,cinm;,coutfib(m)=k,，,k0),。,下面，我们来确定,S(n,，,k),的边界条件,首先不能把,n,个元素不放进任何一个集合中去，即,k=0,时，,S(n,，,k),0,；也不可能在不允许空盒的情况下把,n,个元素放进多于,n,的,k,个集合中去，即,k,n,时,S(n,，,k),0,；再者，把,n,个元素放进一个集合或把,n,个元素放进,n,个集合，方案数显然都是,1,，即,k=1,或,k=n,时，,S(n,k)=1,。,因此，我们可以得出划分数,S(n,，,k),的递归关系式为：,S(n,，,k),S(n,1,，,k,1)+k*S(n,1,，,k)(nk,，,k0),S(n,，,k),0 (nk),或,(k,0),S(n,，,k),1 (k=1),或,(k,n),【参考程序】,#include,using namespace std;,int s(int n,int k)/数据还有可能越界，请用高精度计算,if(n n k;,cout s(n,k);,return 0;,【,例,6】,数的计数,(Noip2001),【,问题描述,】,我们要求找出具有下列性质数的个数（包括输入的自然数,n,）。先输入一个自然数,n,（,n1000,），然后对此自然数按照如下方法进行处理：,不作任何处理；,在它的左边加上一个自然数，但该自然数不能超过原数的一半；,加上数后，继续按此规则进行处理，直到不能再加自然数为止。,输入：,自然数,n,（,n1000,）,输出：,满足条件的数,【,输入样例,】,6,满足条件的数为,6 (,此部分不必输出,),16,26,126,36,136,【,输出样例,】,6,【方法一】,用递归，f(,n,)=1+f(1)+f(2)+f(div/2)，当,n,较大时会超时，时间应该为指数级。,【参考程序】,#include,using namespace std;,int ans;,void dfs(int m)/统计m所扩展出的数据个数,int i;,ans+;,/每出现一个原数，累加器加1；,for(i=1;i n;,dfs(n);,cout ans;,return 0;,【方法二】,：,用记忆化搜索，实际上是对方法一的改进。设hi表示自然数i满足题意三个条件的数的个数。如果用递归求解，会重复来求一些子问题。例如在求h4时，需要再求h1和h2的值。现在我们用h数组记录在记忆求解过程中得出的所有子问题的解，当遇到重叠子问题时，直接使用前面记忆的结果。,【参考程序】,#include,using namespace std;,int h1001;,void dfs(int m),int i;,if(hm!=-1)return;,/说明前面已经求得hm的值，直接引用即可，不需要再递归,hm=1;,/将hm置为1，表示m本身为一种情况,for(i=1;i n;,for(int i=1;i=n;i+),hi=-1;,/h数组初始化为-1,dfs(n);/由顶到下记忆化递归求解,cout n;,for(int i=1;i=n;i+),/按照递增顺序计算扩展出的自然数的个数,hi=1;/扩展出的自然数包括i本身,for(int j=1;j=i/2;j+),/i左边分别加上1自然数 按规则扩展出的自然数,hi+=hj;,cout n;,for(int i=1;i=n;i+),hi=1+si/2;,si=si-1+hi;/s,是,h,的前缀累加和,cout n;,h1=1;,for(int i=2;i=n;i+),hi=hi-1;,if(i%2=0)hi=hi-1+hi/2;,cout 0,，,n0),【,输入格式,】,输入二个数，即,m,和,n,的值。,【,输出格式,】,输出最大公约数。,【,输入样例,】,8 6,【,输出样例,】,gcd=2,6,、双色,Hanoi,塔问题,【,问题描述,】,设,A,、,B,、,C,是,3,个塔座。开始时，在塔座,A,上有一叠共,n,个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为,1,，,2,，,，,n,，奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座,A,上的这一叠圆盘移到塔座,B,上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：,规则,(1),：每次只能移动,1,个圆盘；,规则,(2),：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；,规则,(3),：任何时刻都不允许将同色圆盘叠在一起；,规则,(4),：在满足移动规则,(1)-(3),的前提下，可将圆盘移至,A,，,B,，,C,中任一塔座上。,试设计一个算法，用最少的移动次数将塔座,A,上的,n,个圆盘移到塔座,B,上，并仍按同样顺序叠置。,【,编程任务,】,对于给定的正整数,n,，编程计算最优移动方案。,【,输入格式,】,由文件,hanoi.in,给出输入数据。第,1,行是给定的正整数,n,。,【,输出格式,】,将计算出的最优移动方案输出到文件,hanoi.out,。文件的每一行由一个正整数,k,和,2,个字符,c1,和,c2,组成，表示将第,k,个圆盘从塔座,c1,移到塔座,c2,上。,【,输入样例,】,3,【,输出样例,】,1 A B,2 A C,1 B C,3 A B,1 C A,2 C B,1 A B,7,、背包问题,【,问题描述,】,简单的背包问题。设有一个背包，可以放入的重量为,s,。现有,n,件物品，重量分别为,w,1,w,2,，,w,n,，（,1in,）均为正整数，从,n,件物品中挑选若干件，使得放入背包的重量之和正好为,s,。找到一组解即可。,【,输入格式,】,第一行是物品总件数和背包的载重量，第二行为各物品的重量。,【,输出格式,】,各所选物品重量。,【,输入样例,】,5 10,1 2 3 4 5,【,输出样例,】,number:1 weight:1,number:4 weight:4,number:5 weight:5,8,、,2,的幂次方（,Noip1998,）,【,问题描述,】,任何一个正整数都可以用,2,的幂次方表示。例如：,137=2,7,+2,3,+2,0,同时约定方次用括号来表示，即,ab,可表示为,a,（,b,）。,由此可知，,137,可表示为：,2,（,7,）,+2,（,3,）,+2,（,0,）,进一步：,7=2,2,+2+2,0,（,21,用,2,表示）,3=2+20,所以最后,137,可表示为：,2,（,2,（,2,）,+2+2,（,0,）,+2,（,2+2,（,0,）,+2,（,0,）,又如：,1315=2,10,+2,8,+2,5,+2+1,所以,1315,最后可表示为：,2,（,2,（,2+2,（,0,）,+2,）,+2,（,2,（,2+2,（,0,）,+2,（,2,（,2,）,+2,（,0,）,+2+2,（,0,）,【,输入格式,】,正整数（,n20000,）,【,输出格式,】,符合约定的,n,的,0,，,2,表示（在表示中不能有空格）,【,输入样例,】,137,【,输出样例,】,2(2(2)+2+2(0)+2(2+2(0)+2(0),9,、数的计数（,Noip2001,）,【,问题描述,】,我们要求找出具有下列性质数的个数,(,包含输入的自然数,n):,先输入一个自然数,n,（,n1000,）,然后对此自然数按照如下方法进行处理：,1,不作任何处理；,2,在它的左边加上一个自然数，但该自然数不能超过原数,(,输入的,n),的一半；,3,加上数后，继续按此规则进行处理，直到不能再加自然数为止。,【,输入样例,】,6,满足条件的数为,6 (,此部分不必输出,),16,26,126,36,136,【,输出样例,】,6,【,编程任务,】,给定正整数,n,和,m,，计算出,n,个元素的集合,1,2,n,可以划分为多少个不同的由,m,个非空子集组成的集合。,【,输入格式,】,由文件,stir.in,提供输入数据。文件的第,1,行是元素个数,n,和非空子集数,m,。,【,输出格式,】,程序运行结束时，将计算出的不同的由,m,个非空子集组成的集合数输出到文件,stir.out,中。,【,输入样例,】,4 3,【,输出样例,】,6,【,算法分析,】,所求的是第,2,类,Stirling,数，通过可递推出如下递归式：,S(n,m)=m,*,S(n-1,m)+S(n-1,m-1);,S(n,n+1)=0,，,S(n,0)=0,，,S(0,0)=1,10,、集合划分问题,【,问题描述,】,n,个元素的集合,1,2,n,可以划分为若干个非空子集。例如，当,n=4,时，集合,1,，,2,，,3,，,4,可以划分为,15,个不同的非空子集如下：,1,，,2,，,3,，,4,，,1,，,2,，,3,，,4,，,1,，,3,，,2,，,4,，,1,，,4,，,2,，,3,，,2,，,3,，,1,，,4,，,2,，,4,，,1,，,3,，,3,，,4,，,1,，,2,，,1,，,2,，,3,，,4,，,1,，,3,，,2,，,4,，,1,，,4,，,2,，,3,，,1,，,2,，,3,，,4,，,1,，,2,，,4,，,3,，,1,，,3,，,4,，,2,，,2,，,3,，,4,，,1,，,1,，,2,，,3,，,4,其中，集合,1,，,2,，,3,，,4,由,1,个子集组成；集合,1,，,2,，,3,，,4,，,1,，,3,，,2,，,4,，,1,，,4,，,2,，,3,，,1,，,2,，,3,，,4,，,1,，,2,，,4,，,3,，,1,，,3,，,4,，,2,，,2,，,3,，,4,，,1,由,2,个子集组成；集合,1,，,2,，,3,，,4,，,1,，,3,，,2,，,4,，,1,，,4,，,2,，,3,，,2,，,3,，,1,，,4,，,2,，,4,，,1,，,3,，,3,，,4,，,1,，,2,由,3,个子集组成；集合,1,，,2,，,3,，,4,由,4,个子集组成。,