资源描述：
《ACM递归例题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1/38二叉树1、问题描述图1满二叉树2/38问题描述如上图所示，由正整数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
2、,xi+2=yj+2,...现在的问题就是，给定x和y，要求xi（也就是yj）。3/38问题描述输入格式输入只有一行，包括两个正整数x和y，这两个正整数都不大于1000。输出要求输出只有一个正整数xi。输入样例104输出样例24/38这个题目要求树上任意两个节点的最近公共子节点。分析这棵树的结构不难看出，不论奇数偶数，每个数对2做整数除法，就走到它的上层结点。我们可以每次让较大的一个数（也就是在树上位于较低层次的节点）向上走一个结点，直到两个结点相遇。如果两个节点位于同一层，并且它们不相等，可以让其中任何一个先往上走，然后另一个再往上走，
3、直到它们相遇。设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(xy/2)；2、解题思路5/383、参考程序#includeintcommon(intx,inty){if(x==y)returnx;if(x>y)returncommon(x/2,y);returncommon(x,y/
4、2);}intmain(void){intm,n;scanf("%d%d",&m,&n);printf("%d",common(m,n));return0;}6/38波兰表达式1、问题描述波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2+3的波兰表示法为+23。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2+3)*4的波兰表示法为*+234。本题求解波兰表达式的值，其中运算符包括+-*/四个。7/38问题描述输入数据输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数输出要求输出
5、为一行，表达式的值。输入样例*+11.012.0+24.035.0输出样例1357.0000008/38这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太容易想清楚，但是如果用递归的思想就非常容易想清楚。让我们根据逆波兰表达式的定义进行递归求解。在递归函数中，针对当前的输入，有五种情况：(1)输入是常数，则表达式的值就是这个常数；(2)输入是’+’，则表达式的值是再继续读入两个表达式并计算出它们的值，然后将它们的值相加；(3)输入是’-’；(4)输入是’*’；(5)输入是’/’；后几种情况与2）相同，只是计算从’+’变成’-’，’*’
6、，’/’。2、解题思路9/383、参考程序#include#includedoubleexp(void){chara[10];scanf("%s",a);switch(a[0]){case'+':returnexp()+exp();case'-':returnexp()-exp();case'*':returnexp()*exp();case'/':returnexp()/exp();default:returnatof(a);}}10/38intmain(void){doubleans;ans=exp(
7、);printf("%f",ans);return0;}11/38放苹果1、问题描述把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）注意：5，1，1和1，5，1是同一种分法。12/38问题描述输入数据第一行是测试数据的数目t（0<=t<=20）。以下每行均包含两个整数M和N，以空格分开。1<=M，N<=10。输出要求对输入的每组数据M和N，用一行输出相应的K。输入样例173输出样例813/38所有不同的摆放方法可以分为两类：至少有一个盘子为空和所有盘子都不空。对于至少空着一个盘子的情况，则N
8、个盘子摆放M个苹果的摆放方法数目与N-1个盘子摆放M个苹果的摆放方法数目相同。对于所有盘子都不空的情况，则N个盘子摆放M个苹果的摆放方法数目等于N个盘子摆放M-N个苹果的摆放方法数目。我们可以
