《算法与程序实践2(递归1)》由会员分享，可在线阅读，更多相关《算法与程序实践2(递归1)（10页珍藏版）》请在金锄头文库上搜索。
1、算法与程序实践2习 题 解 答8递归1让我们来看看计算n的阶乘的计算机程序的写法。在数学上，求n的阶乘，有两种表示方法：（1）n!=n*(n-1)*(n-2)*2*1（2）n!=n*(n-1)! （0！=1）这两种表示方法实际上对应到两种不同的算法思想。在第（1）种表示方法中，求n!要反复把1、2、3、（n-2）、（n-1）和n累乘起来，是循环的思想，很直接地我们会用一个循环语句将n以下的数都乘起来: int n,m = 1; for(int i = 2; i = n; i+) m *= i; printf(“%d 的阶乘是%dn”, n, m); 在第（2）种表示方法中，求n！时需要用到（n
2、-1）！，所以可以用下面的方法来求n的阶乘： int factorial(int n) if(n = 0) return(-1); if(n = 1) return 1; else return n*factorial(n - 1); 上面这两种实现方式体现了两种不同的解决问题的思想方法。第一种通过一个循环语句来计算阶乘，其前提是了解阶乘的计算过程，并用语句把这个计算过程模拟出来。第二种解决问题的思想是不直接找到计算n的阶乘的方法，而是试图找到n的阶乘和n-1的阶乘的递推关系，通过这种递推关系把原来问题缩小成一个更小规模的同类问题，并延续这一缩小规模的过程，直到在某一规模上，问题的解是已知的。
3、这样一种解决问题的思想我们称为递归的思想。递归方法的总体思想是将待求解问题的解看作输入变量x的函数f(x)，通过寻找函数g，使得f(x) = g(f(x-1)，并且已知f(0)的值，就可以通过f(0)和g求出f(x)的值。这样一个思想也可以推广到多个输入变量x，y，z等，x-1也可以推广到x - x1，只要递归朝着出口的方向走就可以了。用递归的方法可以求解具有递推关系的问题，此外，还可以广泛应用在搜索领域和排列组合领域。CS801：猴子吃桃（来源：程序设计方法及在线实践指导（王衍等） P263）问题描述：猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天又将剩下的桃子吃掉一
4、半，又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第10天早上想再吃时，就只剩下一个桃子了。求第1天共摘了多少个桃子。分析：假设Ai为第i天吃完后剩下的桃子的个数，A0表示第一天共摘下的桃子，本题要求的是A0.有以下递推式子：A0=2*（A1+1） A1：第1天吃完后剩下的桃子数A1=2*（A2+1） A2：第2天吃完后剩下的桃子数A8=2*（A9+1） A9：第9天吃完后剩下的桃子数A9=1以上递推过程可分别用非递归思想（循环结构）和递归思想实现。用循环结构实现：如果x1、x2表示前后两天吃完剩下的桃子数，则有递推关系：x1=（x2+1）*2。从第9天剩下1个桃子，反复递推9次
5、，则可求第1天共摘下的桃子数。这里包含了反复的思想，可以用循环结构来实现，代码如下：#include int main() int day,x1,x2; day=9; x2=1; while(day0) x1=(x2+1)*2; x2=x1; day-; printf(total= %dn,x1); / system(pause); return 0;用递归思想实现：前面所述的递推关系也可以采用下面的方式描述。假设第n天吃完后剩下的桃子数为 A（n），第n+1天吃完后剩下的桃子数为A（n+1），则存在的递推关系：A(n)=(A(n+1)+1)*2。这种递推关系可以用递归函数实现，代码如下：#i
6、nclude int A(int n) if(n=9) return 1; else return (2*(A(n+1)+1);int main() printf(total= %dn,A(0);/ system(pause); return 0;CS802：最大公约数（来源：程序设计方法及在线实践指导（王衍等） P265）问题描述：输入两个正整数，求其最大公约数。数论中有一个求最大公约数的算法称为辗转相除法，又称欧几里德算法。其基本思想及执行过程为（设m为两正整数中较大者，n为较小者）：（1）令u=m,v=n；（2）取u对v的余数，即r=u%v，如果r的值为0，则此时v的值就是m和n的最大公
7、约数，否则执行第（3）步；（3）u=v，v=r，即u的值为v的值，而v的值为余数r。并转向第（2）步。用循环结构实现，代码如下：#includeint gcd(int u,int v) int r; while(r=u%v)!=0) u=v; v=r; return (v);int main() int m,n,t; printf(Please input two positive integers:); scanf(%d%d,&m,&n); if(mBACBC又如，移动3个盘子的情况，需要7步：ACABCBACBABCAC现在的问题是，当A柱上有n个盘子时，至少需要移动多少步？现按如下思路进
8、行思考：将n个盘子从A柱移到C柱可以分解为以下3个步骤：（1）将A柱上n-1个盘子借助C柱先移到B柱上；（2）将A柱上剩下的1个盘子移到C柱上；（3）将B柱上的n-1个盘子借助A柱移到C柱上。而n-1个盘子的移动又可以分解为两次n-2个盘子的移动和一次1个盘子的移动。依次类推。设移动n个盘子至少需要A(n)步，则存在递推式子：A(n)=2*A(n-1)+1。这个递推式子结束条件是：当n=1时，只有一个盘子，只需一次移动即可。因此移动n个盘子至少需要：A(n)=2n-1步。这样我们可以描述为：将n个盘子从one柱上借助two柱子移动到three柱上。这样，以上3个步骤可以表示为：第（1）步：将n
9、-1个盘子从one柱子上借助three柱子移动到two柱子上；第（2）步：将one柱子上的盘子（只有一个）移动到three柱子上；第（3）步：将n-1个盘子从two柱子上借助one柱子移动到three柱子上。n个盘子的移动分解成两次n-1个盘子的移动和一次1个盘子的移动，因此可以用递归函数实现：（1）hanoi函数：函数调用hanoi(n,one,two,three)实现将n个盘子从one柱子上借助two柱子移到three柱子的过程。（2）move函数：函数调用move(x,y)实现把1个盘子从x柱子上移到y柱子上的过程。x和y代表A、B、C柱子之一，根据不同情况分别以A、B、C代入。代码如下
10、：#includeint main() void hanoi(int m,char one,char two,char three); /函数声明 int m; /盘子个数 printf(input the number of disks:); scanf(%d,&m); printf(The steps of moving %d disks:n,m); hanoi(m,A,B,C); /调用hanoi函数实现将m个盘子从A柱移动到C柱（借助B柱） return 0;/将n个盘子从one柱移到three柱（借助two柱）void hanoi(int n,char one,char two,ch
11、ar three) void move(char x,char y); /函数声明 if(n=1) move(one,three); else hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); void move(char x,char y) /将1个盘子从x柱移动到y柱 printf(%c - %cn,x,y); *递归存在的问题*用递归思想的代价是十分巨大，它会消耗大量的内存。对于Fibonacci数列，调用到第20项时，递归次数达到21891次。CS804：另一个Fibonacci数列（来源：ZOJ
12、2060，程序设计方法及在线实践指导（王衍等） P272）问题描述：定义另外一个Fibonacci数列：F(0)=7,F(1)=11,F(n)=F(n-1)+F(n-2)，（n2）。输入：输入文件中包含多行，每行为一个整数n，n1000000。输出：对输入文件中的每个整数n，如果F(n)能被3整除，输出yes，否则输出no。样例输入：0123样例输出：nonoyesno解题分析：如果利用递归思想求Fibonacci数列的各项，本题中如果直接采用递归方法求F(n)对3取余得到的余数，则会超时。我们可以尝试利用程序输出前30项对3取余的结果：#includeint f(int n)if(n=0) return 1;else if(n=1) return2;else
