（C语言递归)汉诺塔问题，青蛙跳台阶问题

• 汉诺塔问题
• 青蛙跳台阶问题

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

我们可以先画图理解一下。

⭐当只有1个圆盘时


A—>C，一步就可以实现

⭐当有2个圆盘时




先将最上面的圆盘挪到B，再把底下的圆盘挪到C，再把B上的圆盘挪到C
A—>B,A—>C,B—>C,三步完成。

⭐当有3个圆盘时








A—>C,A—>B,C—>B,A—>C,B—>A,B—>C,A—>C，共7步实现。

我们可以发现以下规律:

当圆盘非常多时，我们从递归的角度考虑，可以理解为先把上面n-1个圆盘借助C挪到B，然后把A中最底下的一个圆盘挪到C，然后再把B上的n-1个圆盘借助A挪到C。

void move(char from, char to)
{
	printf("%c--->%cn", from, to);
}
void hanoi(int n, char from, char temp, char to)
{
	if (n == 1)
	{
		move(from, to);
	}
	else
	{
		hanoi(n - 1, from, to, temp);
		move(from, to);
		hanoi(n - 1, temp, from, to);
	}
}
int main()
{
	int n;
	printf("需要叠的层数:>");
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	return 0;
}

//from—A是圆盘初始位置，
//to—C是圆盘最终位置，
//temp—B是圆盘临时存放的位置，
//move函数是在两根柱子之间移动，只有初始和最终柱子参与
//当只有1个圆盘时，只用移动一次从初始位置到最终位置而不需要中间柱子的参与。
//当圆盘数n大于1时，需要先将上层n-1个圆盘借助C柱子挪到B柱子暂时存放（递归过程），再把底层最后一个圆盘挪到C柱子，再把B柱子上存放的n-1个柱子借助A柱子挪到C柱子，完成目标。

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？

当n=1时，只有1种跳法，
当n=2时，可以一次跳2个台阶，也可以跳两次1级台阶，2种跳法。
当n=3时，可以跳3次1级台阶，也可以第一次跳1级，第二次跳2级，也可以第一次跳2级，第二次跳1级，3种跳法。
…

我们可以发现每次的跳法数都是前两次跳法数相加的和，这类似于斐波那契数列。

完整代码如下：

int Fibo(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else
		return Fibo(n - 1) + Fibo(n - 2);
}
int main()
{
	int n = 0;
	printf("台阶数:>");
	scanf("%d", &n);
	int ret=Fibo(n);
	printf("跳法数:>%dn", ret);
	return 0;
}