简单递归题目分析与解答

1.放苹果：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法（用K表示）？注意：5，1，1和1，5，1 是同一种分法。

输入：
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

输出：
对输入的每组数据M和N，用一行输出相应的K。

样例输入：
1
7 3
样例输出：
8

int ways (int m,int n) //m：苹果数 n: 盘子数
{
	if (n == 1 || m == 0)  return 1; //递归出口：如果盘子数为1或苹果数为0 则返回1；
	if (n > m) return ways(m,m);//否则 如果n>m,总有n-m个盘子总也没有苹果，则对方法数没有影响，即等价于m个苹果放进m个盘子里。
	else
	return ways(m,n - 1) + ways(m - n,n);//如果n<=m，则方法总数为至少一个盘子空着所需的方法（有空盘）+ 所有盘子都不空方法数（无空盘）。
}

2.二叉树：
简单递归题目分析与解答

图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

int f (int x,int y)
{
	if (x > y) //如果x大于y，则查找x的双亲。
	return f(x / 2,y);
	else if (x < y)//如果y大于x，则查找yde双亲。
	return f(x,y / 2);
	else if (x == y)//递归出口，如果x == y，则说明找到，返回x或y值即可。
	return x;	
}

3.爬楼梯：小明决定从今天开始通过爬楼梯来锻炼身体。楼梯共有N级台阶，上楼的时候可以一步上一级台阶，也可以一步上两级台阶。请你帮她编个程序，计算共有多少种不同的走法。

输入文件中有很多行，每行是一个测试数据，只包含一个正整数N。要求计算出对应的走法并输出，每个结果占一行。

Sample Input
1
3
12
Sample Output
1
3
233

int W(int n)
{
	if (n == 0 || n == 1) //如果台阶数为0或1，则返回1
	return 1;
	else
	return W(n - 1) + W(n - 2); //我们知道，从第n - 1阶和n - 2阶都能上到第n阶，则上到第n阶台阶的方法数 = 前n - 1阶的走法 + 前 n - 2阶的走法.
}

未完待续…

简单递归题目分析与解答

相关推荐