2021-11-08【C】【递归】【代码】入门汉诺塔问题+青蛙跳台阶（斐波那契解法）

• 汉诺塔问题
• • 三层汉诺塔为例
  • ❀思路
  • 代码
  • 运行结果
• 青蛙跳台阶
• • ❀思路
  • 代码
  • 运行结果

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

题目规则：三根柱子，将起始柱上的圆盘全部移动到目标柱上
1.每次只能移动一个圆盘
2.移动中三根杆，大盘在下，小盘在上
3.每次只能移动柱子最上端的一个圆盘

如图所示需要7步

其中1，2，3步完成了把2个盘从A挪到B（如果把B柱看做目标柱，C柱看做中转柱，这3步相当于两层汉诺塔的解法）。
第4步完成了把最大的盘从A挪到C
5，6，7步完成了把2个盘从B挪到C（如果把A看作中转柱，B看作起始柱，这3步相当于两层汉诺塔解法）
思路总结:n层汉诺塔解法
用x,y,z分别表示起始柱，中转柱，目标柱
圆盘从上到下编号依次为1,2，……n
（1）n-1个圆盘从x挪到y
（2）最大的n号圆盘从x挪到z
（3）n-1个圆盘从y挪到z
把n层汉诺塔的解法步数看成是n的函数，记为h(n)
h(2) = h(1)+1+h(1)
h(3) = h(2)+1+h(2)
……
h(n) = h(n-1)+1+h(n-1)

#define _CRT_SECURE_NO_DEPRECATE 0
#include
//1.汉诺塔问题，参数含义，num汉诺塔层数，x起始柱，y中转柱，z目标柱
//盘片从上到下编号为1,2，……，n

int pre = 0;//统计移动盘片次数

//必须设置全局变量，因为Hanno函数为递归函数，如果在函数内定义，pre会被重复定义置0
int Hanno(int num, char x, char y, char z)
{
	if (1 == num)
	{
		printf("把%d号盘片从%c挪到%cn", num, x, z);
		pre++;
		return 1;	
	}
	else
	{
		//1.把n-1个盘片从x挪到y
		Hanno(num - 1, x, z, y);//因为此时y为目标柱
		//2.把最大的盘片从x挪到z
		printf("把%d号盘片从%c挪到%cn",num,x,z);
		pre++;
		//3.把n-1个盘片从y挪到z
		Hanno(num - 1, y, x, z);//因为此时y为目标柱
	}
	return pre;
}

int main()
{
	int num = 0;
	char x = '0';
	char y = '0';
	char z = '0';
	
	printf("请输入起始柱字符n");
	scanf("%c", &x);
	printf("请输入中转柱字符n");
	scanf("n%c", &y);
	printf("请输入目标柱字符n");
	scanf("n%c", &z);
	printf("此时的起始柱为： %c 中转柱为： %c 目的柱为： %c n", x, y, z);
	
	printf("请输入汉诺塔层数n");
	scanf("%d", &num);
	printf("%d层汉诺塔需要移动%d次",num,Hanno(num, x, y, z));

	return 0;
}

3层汉诺塔运行结果：

5层汉诺塔运行结果：

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

考虑最简单的情况，跳1级台阶，只有一种跳法。[1]
跳2级台阶，有两种跳法。[1,1] ，[2]
一般情况下，把跳n级台阶的跳法数看成是n的函数，记为f(n)。

思路总结
当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；
另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。
因此n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。
这实际类似斐波那契数列

int frog(int n)
{
	if (1 == n)
	{
		return 1;
	}
	else if(2 == n)
	{
		return 2;
	}
	else if(n > 2)
	{
		return (frog(n - 2) + frog(n - 1));
	}
	else
	{
		printf("输入台阶数错误n");
		return-1;
	}
}

int main()
{
	int n = 0;
	printf("请输入台阶数：n");
	scanf("%d", &n);
	
	printf("%d层台阶有%d种跳法n", n, frog(n));

	return 0;
}