算法与程序实践2(递归1).doc

. . . .算法与程序实践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-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的阶乘的递推关系，通过这种递推关系把原来问题缩小成一个更小规模的同类问题，并延续这一缩小规模的过程，直到在某一规模上，问题的解是已知的。这样一种解决问题的思想我们称为递归的思想。递归方法的总体思想是将待求解问题的解看作输入变量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天又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第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次，则可求第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。这种递推关系可以用递归函数实现，代码如下：#include 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的最大公约数，否则执行第（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个盘子时，至少需要移动多少步？现按如下思路进行思考：将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-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代入。代码如下：#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,char 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 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 return (f(n-1)+f(n-2)%3;int main()for(int i=0;i30;i+)printf(“%d”,f(i);前30项对3取余得到的余数分别为：1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1。分析这些余数，我们不难发现该Fibonacci数列各项对3取余的余数每8项构成一个循环：1 2 0 2 2 1 0 1。如果我们把这8个余数存放到一个数组f0，对输入的任意整数n，则有：f(n)%3=f0n%8。按照这种方法可以很快判断f(n)是否能被3整除。参考程序：#includeint f(int n) if(n=0) return 1; else if(n=1) return 2; else return (f(n-1)+f(n-2)%3;int main() int f08; for(int i=0;i8;i+) f0i=f(i); int n; while(scanf(%d,&n)!=EOF) if(f0n%8=0) printf(yesn); else printf(non); return 0;CS822：分形（Fractal）（来源：POJ 2083 ZOJ 2423，程序设计方法及在线实践指导（王衍等） P274）问题描述：分形是存在“自相似”的一个物体或一种量，从某种技术角度来说，这种“自相似”是全方位的。盒形分形定义如下：度数为1的分形很简单，为：X度数为2的分形为：X X XX X如果用B(n-1)代表度数为n-1的盒形分形，则度数为n的盒形分形可以递归地定义为：B(n-1) B(n-1) B(n-1)B(n-1) B(n-1)你的任务是输出度数为n的盒形分形。输入：输入文件包含多个测试数据，每个测试数据占一行，包含一个正整数n，n7。输入文件的最后一行为-1，代表输入结束输出：对每个测试数据，用符号“X”表示输出盒形分形。在每个测试数据对应的输出之后输出一个短划线符号“-”，在每行的末尾不要输出任何多余的空格，否则得到的是“格式错误”的结果。样例输入：123-1样例输出：X-X X XX X-X X X X X XX X X X X X X X XX X X X X XX X X X-解题分析：首先注意到度数为n的盒形分形，其大小是3n-1*3n-1。可以用字符数组来存储盒形分形中各个字符。因为n7，而36=729，因此可以定义一个字符数组Fractal730730来存储度数不超过7的盒形分形。其次，度数为n的盒形分形可以由以下递推式子表示： B(n-1) B(n-1)B(n)= B(n-1)B(n-1) B(n-1)因此，可以用一个递归函数来设置度数为n的盒形分形。假设需要在（startX,startY）位置开始设置度数为n的盒形分形，它由5个度数为n-1的盒形分形组成，其起始位置分别为：(startX+0,startY+0)、(startX+2*L0,startY+0)、(startX+L0,startY+L0)、(startX+0,startY+2*L0)和(startX+2*L0,startY+2*L0)，其中L0=3n-2。该递归函数的结束条件是：当n=1时（即度数为1的盒形分形），只需要在(startX,startY)位置设置一个“X”字符。另外，题目中提到“在每行的末尾不要输出任何多余的空格”，因此在字符数组Fractal每行最后一个“X”字符之后，应该设置串结束符标志0。参考程序：#include#include#define MAXSCALE 730 /n为最大值7，分形的大小是36*36，而36=729/函数功能：从(startX,startY)位置开始设置度数为n的盒形分形 /即对盒形分形中的每个X，在字符数组Frac的相应 位置设置字符X /其中第1个形参为一个二维数组名，其第2维不能省略 void SetFractal(char Frac730,int startX,int startY,int n) if(n=1) FracstartXstartY=X; else int L0=(int)pow(3,n-2); SetFractal(Frac,startX+0,startY+0,n-1); SetFractal(Frac,startX+2*L0,startY+0,n-1); SetFractal(Frac,startX+L0,startY+L0,n-1); SetFractal(Frac,startX+0,startY+2*L0,n-1); SetFractal(Frac,startX+2*L0,startY+2*L0,n-1); int main() int n; /分形的大小 int i,j; /循环变量 char FractalMAXSCA