C语言递归算法.ppt

《C语言递归算法.ppt》由会员分享，可在线阅读，更多相关《C语言递归算法.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 递归算法递归算法前面已经介绍了关于递归调用这样一种操作，而递归程序设计是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,所以是有限次的递归调用；

2、(3)结束条件是当n=1，则s=1。【参考程序】#includeusingnamespacestd;intfac(int);/递归函数intmain()intt;cint;/输入t的值couts=fac(t)endl;/计算1到t的累加和，输出结果intfac(intn)if(n=1)return1;return(fac(n-1)+n);/调用下一层递归运行程序，当T=5时，输出结果：S=15，其递归调用执行过程是：（设T=3）递归调用过程，实质上是不断调用过程或函数的过程，由于递归调用一次，所有子程序的变量（局部变量、变参等）、地址在计算机内部都有用特殊的管理方法栈（先进后出）来管理，一旦递

3、归调用结束，计算机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。【例【例2】设有设有N个数已经按从大到小的顺序排列，现在输入个数已经按从大到小的顺序排列，现在输入X，判断它是，判断它是否在这否在这N个数中，如果存在则输出：个数中，如果存在则输出：“YES”否则输出否则输出“NO”。【算法分析】该问题属于数据的查找问题，数据查找有多种方法，通常方法是：顺序查找和二分查找，当N个数排好序时，用二分查找方法速度大大加快。二分查找算法：（1）设有N个数，存放在A数组中，待查找数为X，用L指向数据的高端，用R指向数据的低端，MID指向中间：（2）若X=AMID输出“YES”；（3）若XA

4、MID则到数据前半段查找：L不变，R=MID-1，计算新的MID值，并进行新的一段查找；（5）若LR都没有查找到，则输出“NO”。该算法符合递归程序设计的基本规律，可以用递归方法设计。【参考程序】【参考程序】#include#includeusing 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(i

5、nt x,int top,int bot)/二分查找递归过程二分查找递归过程int mid;if(top=bot)mid=(top+bot)/2;/求中间数的位置求中间数的位置 if(x=amid)coutYESendl;/找到就输出找到就输出 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

6、的情况（把上面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)。【参考程序】【参考程序】#includeusing namespace std;int k=0,n;void mov(int n,char a,char c,char b)/用用b柱作为协助过渡，将柱作为协助过渡，将a柱上的（柱上的（n）移到）移到c柱上柱上i

7、f(n=0)return;/如果如果n=0，则退出，即结束程序，则退出，即结束程序mov(n-1,a,b,c);/用用c柱作为协助过渡，将柱作为协助过渡，将a柱上的（柱上的（n-1）片移到）片移到b柱上柱上k+;cout k:from a cendl;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柱

8、作为过渡柱;直接执行writeln(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过程中出现了自己调用自己的情况，在Pascal中称为递归调用，这是Pascal语言的一个特色。对于没有递归调用功能的程序设计语言，则需要将递归过程重新设计为非递归过程的程序。【例【例

9、4】用递归的方法求斐波那契数列中的第用递归的方法求斐波那契数列中的第N个数个数【参考程序】【参考程序】#includeusing namespace std;int a11;int fib(int);int main()int m;cinm;coutfib(m)=k，k0)。w下面，我们来确定S(n，k)的边界条件,首先不能把n个元素不放进任何一个集合中去，即k=0时，S(n，k)0；也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即kn时,S(n，k)0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是1，即k=1或k=n时，S(n,k)=1。w因此，我们

10、可以得出划分数S(n，k)的递归关系式为：wS(n，k)S(n1，k1)+k*S(n1，k)(nk，k0)wS(n，k)0(nk)或(k0)wS(n，k)1(k=1)或(kn)w【参考程序】【参考程序】w#includewusingnamespacestd;wwints(intn,intk)/数据还有可能越界，请用高精度计算wwif(nnk;wcouts(n,k);wreturn0;ww【例例6 6】数的计数数的计数(Noip2001)(Noip2001)w【问题描述问题描述】w我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n1000），然后对此自然数按照如下方法

11、进行处理：w不作任何处理；w在它的左边加上一个自然数，但该自然数不能超过原数的一半；w加上数后，继续按此规则进行处理，直到不能再加自然数为止。w输入：输入：自然数n（n1000）w输出：输出：满足条件的数w【输入样例输入样例】w6满足条件的数为6(此部分不必输出)w16w26w126w36w136w【输出样例输出样例】w6【方法一】【方法一】w用递归，f(n)=1+f(1)+f(2)+f(div/2)，当n较大时会超时，时间应该为指数级。【参考程序】【参考程序】w#includewusingnamespacestd;wintans;wvoiddfs(intm)/统计m所扩展出的数据个数wwin

12、ti;wans+;/每出现一个原数，累加器加1；wfor(i=1;in;wdfs(n);wcoutans;wreturn0;ww【方法二】【方法二】：用记忆化搜索，实际上是对方法一的改进。设hi表示自然数i满足题意三个条件的数的个数。如果用递归求解，会重复来求一些子问题。例如在求h4时，需要再求h1和h2的值。现在我们用h数组记录在记忆求解过程中得出的所有子问题的解，当遇到重叠子问题时，直接使用前面记忆的结果。w【参考程序】【参考程序】w#includewusingnamespacestd;winth1001;wvoiddfs(intm)wwinti;wif(hm!=-1)return;/说明

13、前面已经求得hm的值，直接引用即可，不需要再递归whm=1;/将hm置为1，表示m本身为一种情况wfor(i=1;in;wfor(inti=1;i=n;i+)whi=-1;/h数组初始化为-1wdfs(n);/由顶到下记忆化递归求解wcouthn;wreturn0;w【方法三】【方法三】用递推，用h(n)表示自然数n所能扩展的数据个数，则h(1)=1,h(2)=2,h(3)=2,h(4)=4,h(5)=4,h(6)=6,h(7)=6,h(8)=10,h(9)=10.分析以上数据，可得递推公式：h(i)=1+h(1)+h(2)+h(i/2)。此算法的时间度为O(n*n)。w设hi-i按照规则扩展

14、出的自然数个数(1in)。下表列出了hi值及其方案：w【参考程序】【参考程序】w#includewusingnamespacestd;winth10001;wintmain()wwintn;wcinn;wfor(inti=1;i=n;i+)/按照递增顺序计算扩展出的自然数的个数wwhi=1;/扩展出的自然数包括i本身wfor(intj=1;j=i/2;j+)w/i左边分别加上1自然数按规则扩展出的自然数whi+=hj;wwcouthn;wreturn0;w【方法四方法四】w是对方法三的改进，我们定义数组s，s(x)=h(1)+h(2)+h(x),h(x)=s(x)-s(x-1)，此算法的时间复

15、杂度可降到O(n)。w【参考程序参考程序】w#includewusingnamespacestd;winth1001,s1001;wintmain()wwintn;wcinn;wfor(inti=1;i=n;i+)wwhi=1+si/2;wsi=si-1+hi;/s是h的前缀累加和wwcouthn;wreturn0;w【方法五方法五】w还是用递推，只要作仔细分析，其实我们还可以得到以下的递推公式:(1)当i为奇数时，h(i)=h(i-1);w(2)当i为偶数时,h(i)=h(i-1)+h(i/2).w【参考程序参考程序】w#includewusingnamespacestd;winth1001

16、;wintmain()wwintn;wcinn;wh1=1;wfor(inti=2;i=n;i+)wwhi=hi-1;wif(i%2=0)hi=hi-1+hi/2;wwcout0(m0，n0)n0)【输入格式】输入二个数，即m和n的值。【输出格式】输出最大公约数。【输入样例】86【输出样例】gcd=26、双色、双色Hanoi塔问题塔问题【问题描述】【问题描述】设A、B、C是3个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1，2，n，奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座A上的这一叠圆盘移到塔座B上，并仍按同样顺序叠置。

17、在移动圆盘时应遵守以下移动规则：规则(1)：每次只能移动1个圆盘；规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则(3)：任何时刻都不允许将同色圆盘叠在一起；规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C中任一塔座上。试设计一个算法，用最少的移动次数将塔座A上的n个圆盘移到塔座B上，并仍按同样顺序叠置。【编程任务】【编程任务】对于给定的正整数n，编程计算最优移动方案。【输入格式】【输入格式】由文件hanoi.in给出输入数据。第1行是给定的正整数n。【输出格式】【输出格式】将计算出的最优移动方案输出到文件hanoi.out。文件的每一行由一个正整数k和

18、2个字符c1和c2组成，表示将第k个圆盘从塔座c1移到塔座c2上。【输入样例】【输入样例】3【输出样例】【输出样例】1AB2AC1BC3AB1CA2CB1AB7、背包问题、背包问题【问题描述】【问题描述】简单的背包问题。设有一个背包，可以放入的重量为s。现有n件物品，重量分别为w1,w2，wn，（1in）均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。找到一组解即可。【输入格式】【输入格式】第一行是物品总件数和背包的载重量，第二行为各物品的重量。【输出格式】【输出格式】各所选物品重量。【输入样例】【输入样例】51012345【输出样例】【输出样例】number:1weigh

19、t:1number:4weight:4number:5weight:58、2的幂次方（的幂次方（Noip1998）【问题描述】【问题描述】任何一个正整数都可以用2的幂次方表示。例如：137=27+23+20同时约定方次用括号来表示，即ab可表示为a（b）。由此可知，137可表示为：2（7）+2（3）+2（0）进一步：7=22+2+20（21用2表示）3=2+20所以最后137可表示为：2（2（2）+2+2（0）+2（2+2（0）+2（0）又如：1315=210+28+25+2+1所以1315最后可表示为：2（2（2+2（0）+2）+2（2（2+2（0）+2（2（2）+2（0）+2+2（0）【输

20、入格式】【输入格式】正整数（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

21、(此部分不必输出)162612636136【输出样例】【输出样例】6【编程任务】【编程任务】给定正整数n和m，计算出n个元素的集合1,2,n 可以划分为多少个不同的由m个非空子集组成的集合。【输入格式】【输入格式】由文件stir.in提供输入数据。文件的第1行是元素个数n和非空子集数m。【输出格式】【输出格式】程序运行结束时，将计算出的不同的由m个非空子集组成的集合数输出到文件stir.out中。【输入样例】【输入样例】43【输出样例】【输出样例】6【算法分析】【算法分析】所求的是第2类Stirling数，通过可递推出如下递归式：S(n,m)=mS(n-1,m)+S(n-1,m-1);S(n,

22、n+1)=0，S(n,0)=0，S(0,0)=110、集合划分问题、集合划分问题【问题描述】【问题描述】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个子集组成。