算法及程序实践习题解答8(递归).doc

《算法与程序实践》习 题 解 答8——递归 让我们来看看计算n 的阶乘的计算机程序的写法,很直接地我们会用一个循环语句将n 以下的数都乘起来: int n,m = 1; for(int i = 2; i = n; i++) m *= i; printf(“%d 的阶乘是%d\n”, n, m); 因为n 的阶乘定义为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，只要递归朝着出口的方向走就可以了。 CS81：菲波那契数列 （来源：poj.grids.cn 2753，程序设计导引及在线实践（李文新）例9.2 P198） 问题描述： 菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。 给出一个正整数a，要求菲波那契数列中第a个数是多少。 输入： 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 = a = 20)。 输出： 输出有n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数的大小。 样例输入： 4 5 2 19 1 样例输出： 5 1 4181 1 解题思路： 这个题目要求很明确，因为a的规模很小，所以递归调用不会产生栈溢出的问题。设第n 项值为f(n)，则f(n) = f(n-1)+f(n-2)。已知f(1)=1，f(2)=1 ，则从第３项开始，可以用公式求。 参考程序： #includestdio.h int f(int a) { if(a==1 || a==2) return 1; return f(a-1)+f(a-2); } int main() { int n; int i; scanf(%d,n); for(i=1;i=n;i++) { int a; scanf(%d,a); printf(%d\n,f(a)); } return 0; } CS82：二叉树 （来源：poj.grids.cn 2756，程序设计导引及在线实践（李文新）例9.3 P199） 问题描述： 图8-1 满二叉树 如图8-1所示，由正整数1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点（编号是1的结点）都有一条唯一的路径，比如从10到根结点的路径是(10, 5, 2, 1)，从4到根结点的路径是(4, 2, 1)，从根结点1到根结点的路径上只包含一个结点1，因此路径就是(1)。对于两个结点x和y，假设他们到根结点的路径分别是(x1, x2, ... ,1)和(y1, y2, ... ,1)（这里显然有x = x1，y = y1），那么必然存在两个正整数i和j，使得从xi 和 yj开始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,... 现在的问题就是，给定x和y，要求xi（也就是yj）。 输入： 输入只有一行，包括两个正整数x和y，这两个正整数都不大于1000。 输出： 输出只有一个正整数xi。 样例输入： 10 4 样例输出： 2 解题思路： 这个题目要求树上任意两个节点的最近公共子节点。分析这棵树的结构不难看出，不论奇数偶数，每个数对2做整数除法，就走到它的上层结点。 我们可以每次让较大的一个数（也就是在树上位于较低层次的节点）向上走一个结点，直到两个结点相遇。如果两个节点位于同一层，并且它们不相等，可以让其中任何一个先往上走，然后另一个再往上走，直到它们相遇。设common(x, y) 表示整数x 和y 的最近公共子节点，那么，根据比较x 和y 的值，我们得到三种情况：1) x 与y 相等，则common(x