算法与程序实践2

《算法与程序实践 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 的阶乘是%d\n”, 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以上递推过程...