《算法与程序实践2》习 题 解 答8——递归2
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 ，则从第３项开始，可以用公式求。
参考程序：
#include
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(\ for(i=1;i<=n;i++) { int a; scanf(\ printf(\ } return 0; }
#include
if(fi[n]!=-1) return fi[n]; if(n==0) return 0; else if(n==1) return 1; else {
fi[n]=f(n-1)+f(n-2); return fi[n]; } }
int main() { int n; int i; scanf(\ for(i=0;i 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, y) 等于x 并且等于y；2）x 大于y，则common(x, y) 等于common(x/2, y)； 3）x 小于y，则common(x, y) 等于common(x,y/2)； 参考程序： #include int common(int x,int y) { if(x==y) return x; if(x>y) return common(x/2,y); return common(x,y/2); } int main() { int m,n; scanf(\ printf(\ return 0; } 注意事项： 问题一：有一种比较直观的解法是对于两个给定的数，分别求出它们到根节点的通路上的所有节点的值，然后再在两个数组中寻找数码最大的公共节点。这种做法的代码比较繁琐，容易在实现中出错； 问题二：代码实现逻辑不明晰，造成死循环等错误，例如，有人只将其中一个数不停地除以2，而不理会另外一个数。 CS83：波兰表达式 （来源：poj.grids.cn 2694，程序设计导引及在线实践（李文新）例9.4 P201） 问题描述： 波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值，其中运算符包括+ - * /四个。 输入： 输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。 输出： 输出为一行，表达式的值。 可直接用printf(\输出表达式的值v。 样例输入： * + 11.0 12.0 + 24.0 35.0 样例输出： 1357.000000 预备知识: 逆波兰表达式的用途: 它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下： 按顺序扫描逆波兰表达式，如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。 中序表达式转换为逆波兰表达式: 1、建立运算符栈stackOperator用于运算符的存储，此运算符在栈内遵循越往栈顶优先级越高的原则。 2、预处理表达式，正、负号前加0（如果一个加号（减号）出现在最前面或左括号后面，则该加号（减号）为正负号）。 3、顺序扫描表达式，如果当前字符是数字（优先级为0的符号），则直接输出该数字；如果当前字符为运算符或括号（优先级不为0的符号），则判断第4点 。 4、若当前运算符为'('，直接入栈； ? 若为')'，出栈并顺序输出运算符直到遇到第一个'('，遇到的第一个'('出栈但不 输出； ? 若为其它，比较stackOperator栈顶元素与当前元素的优先级： ? 如果栈顶元素是'('，当前元素入栈； ? 如果栈顶元素 >= 当前元素，出栈并顺序输出运算符直到栈顶元素 < 当 前元素，然后当前元素入栈；] ? 如果栈顶元素 < 当前元素，直接入栈。 5、重复第3点直到表达式扫描完毕。 6、顺序出栈并输出运算符直到栈元素为空。 举例说明： 表达式\，将中缀表达式转换为逆波兰表达式。 1)建立一个运算符栈stackOperator用来存放运算符；建立一个字符串链表reversePolishExpression用来存放逆波兰表达式 2)顺序扫描\+ ((1 + 2) * 4) ? 3\，根据算法可以得出stackOperator及reversePolishExpression值的变化过程： 扫描 操作 stackOperator值 reversePolishExpression值 注释 5 输出 空 5 当前字符是数字直接输出该数字 + 入栈 + 5 栈顶元素为空，不用比较，入栈 ( 入栈 ( 5 当前运算符为'('，直接入栈 ( 入栈 ( ( 5 当前运算符为'('，直接入栈 1 输出 ( ( 5 1 当前字符是数字直接输出该数字 + 入栈 ( ( + 5 1 + 优先级< 栈顶元素 ( ,入栈 2 输出 ( ( + 5 1 2 当前字符是数字直接输出该数字