递归实现青蛙跳台阶问题与汉诺塔问题

1.青蛙跳台阶问题

1.1题目描述

一只青蛙一次可以跳1到2阶台阶，问，青蛙跳到第n阶台阶时，有几种跳法？

跳到第1阶台阶时， 有 1种跳法

跳到第2阶台阶时， 有 2种跳法

跳到第n阶台阶时，

从第n-1阶台阶跳1阶台阶到达第n阶台阶，这是方法1

从第n-2阶台阶跳2阶台阶到达第n阶台阶，这是方法2

所以

跳到第n阶台阶的方法总数=

跳到第n-1阶台阶的方法总数 + 跳到第n-2阶台阶的方法总数

值得注意的是

从第n-2阶台阶连续跳两次

，每次跳1阶台阶到达第n阶台阶，这种方法‘3’实际上是方法1的重复

因为方法‘3’是从第n-2阶台阶到第n-1阶台阶，再从第n-1阶台阶跳到第n阶台阶的

该过程的前半部分实现的是到第n-1阶的方法1

后半部分实现的是到第n阶的方法‘1’

所以方法‘3’需要舍去

代码实现

int Fact(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else return Fact(n - 1) + Fact(n - 2);
}

可以发现，这就是斐波那契 数列的规律

2.汉诺塔问题

有三根柱子和若干个大小不同的圆盘，这些圆盘最初都按照大小顺序穿在源柱上，最大的在最下面，最小的在最上面。目标是将所有这些圆盘移动到目标柱上，同时遵守相应的规则。

规则如下：

1. 每次只能移动一个圆盘：你不能同时拿起多个圆盘进行移动。

2. 大盘不能放在小盘上面：在任何时候，较大的圆盘都不能放在较小的圆盘之上。

3. 只能使用三根柱子：通常称为源柱（起始时所有圆盘都在这里）、目标柱（最终所有圆盘都要移动到这里）和辅助柱（作为移动过程中的临时存放点）。

请问，如何将圆盘从源柱移动到目标柱，同时满足所有规则，并给出最少的移动步骤？

最开始我们将 A 柱作为源柱， B柱作为 辅助 柱， C柱作为目标柱

我们需要将A柱上的圆盘 移动到 C 柱上去

当A柱上只有1个圆盘时，我们直接将圆盘从A移动到C

当A柱上有n个圆盘，n大于1时， 我们需要

先将n-1个圆盘，即最大圆盘上面的圆盘，移动到辅助柱B柱上面去，

再将最大的圆盘移动到C柱上去，此时其余的圆盘在B柱上

这时A成为辅助柱，B柱成为源柱,C柱成为目标柱

重复上面的步骤即可

void move(char a, char c)
{
     printf("%c -> %c\n", a, c);
}//书写一个函数打印顺序
void Hanoi(int n, char A, char B, char C)
{
    if(n == 1)
         move(A, C);
    else
    {
//当n大于1时，以C柱为辅助柱，将n-1个圆盘移动到B柱上
      Hanoi(n-1, A, C, B);
//将这时最大的圆盘移动到c柱上
       move(A, C);
//以A柱为辅助柱，将n-1个圆盘移动到C柱上
      Hanoi(n-1,B, A, C);
     }
}
         

解决这个问题的关键是，相信函数能够实现相应的功能