当前位置：首页 > news >正文

你是真的“C”——函数递归详解汉诺塔+青蛙跳台阶

news 来源：原创 2024/11/17 23:54:01

函数递归详解汉诺塔+青蛙跳台阶问题😎

前言🙌
函数递归之汉诺塔详解分析🙌
- 汉诺塔问题的简介😊
- 汉诺塔的移动图解😊
- 汉诺塔具体的移动过程展示😊
- 汉诺塔的难处所在：😊
函数递归之青蛙跳台阶详解分析🙌
- 青蛙跳台阶的问题是什么样的问题？😊
总结撒花💞

哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

前言🙌

哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，手把手带领大家用函数递归的方法解决汉诺塔+青蛙跳台阶的问题！都是精华内容，可不要错过哟！！！😍😍😍

函数递归之汉诺塔详解分析🙌

汉诺塔问题的简介😊

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根柱子(编号A、B、C)，在A柱自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A柱上的金盘全部移到C柱上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根柱上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一柱子上。
而将64个圆盘从A柱借助B柱，移动到C柱需要多长的时间呢？通过平常的方法是很难计算的。今天我用递归的思想来计算一下汉诺塔的移动次数和汉诺塔的移动步骤！

汉诺塔的移动图解😊

首先，我们来分析一下汉诺塔移动圆盘的规律：一次只能移动一个圆盘，并且小盘在上，大盘在下！假设我们现在有n个圆盘，那么大概移动的思路是：

先要把n-1个圆盘从A柱移动到B柱上；
再把第n个圆盘（最大的圆盘）从A柱移动到C柱上；
最后把n-1个圆盘从B柱移动到C柱上。

以三层汉诺塔举例说明： 😍

在这里插入图片描述

汉诺塔移动次数的推导： 😍

在这里插入图片描述
由三层的汉诺塔可以推导出n层汉诺塔的移动次数： 😍

步骤1的移动步数就是n-1个圆盘移动所需的步数，我们可以将其步数视为f（n-1）步；
步骤2的移动步数为1；
步骤3的移动步数与步骤1一样，步骤3的移动步数也是f（n-1）步。
小结一下😍：对于1层汉诺塔移动次数为1次，对于其他层数的汉诺塔则为：前一层汉诺塔移动所需的次数+1+前一层汉诺塔移动所需的次数。
因此可以得到递推公式：f（n-1）+ 1 + f（n-1）= 2 * f（n-1）+ 1。

大概的思路理清楚以后，我再用代码的形式实现出来辅助大家的理解： 😍

#include<stdio.h>
int  HanoiStep(int n)
{
	if (n <= 1)
		return 1;
	else
		return 2 * HanoiStep(n - 1) + 1;

}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = HanoiStep(n);
	printf("%d层汉诺塔的移动次数：%d\n",n,ret);
	return 0;
}

代码测试结果图： 😍
在这里插入图片描述

汉诺塔具体的移动过程展示😊

这里所要实现的效果是将汉诺塔的每一步移动都展示出来。我先按照上面总结出来的规律，将1~4层的汉诺塔的移动过程推导出来。 😍 在这里插入图片描述
由图表可知😍：我们可以从上述规律和1~4层移动步骤的过程展示中可以进一步推导出n层汉诺塔的规律和移动过程。

n层汉诺塔的推演过程： 😍

把n-1个圆盘从A移动到B柱上；
把第n个圆盘从A移动到C柱上；
把n-1个圆盘从B移动到C柱上。

n-1个圆盘从A移动到B的推演过程： 😍

把n-2个圆盘从A移动到C柱上；
把第n-1个圆盘从A移动到B柱上；
把n-2个圆盘从C移动到B柱上。

以此类推，对于n-1个圆盘从B移动到C柱上，可以推测出来： 😍

把n-2个圆盘从B移动到A柱上；
把第n-1个圆盘从B移动到C柱上；
把n-2个圆盘从A移动到C柱上。

不难发现，上述的推导过程和所总结出的规律，汉诺塔的移动可以通过递归的方法实现出来。

代码实现思路归纳： 😍

先定义A，B，C三个字符，表示A，B，C三根柱子。定义变量n为汉诺塔层数。
对于一层汉诺塔而言，直接移动即可，对于其他层数的汉诺塔来说，则需要递归展开。

具体的代码实现：😍

#include<stdio.h>
void  HanoiMove(int n,char A,char B,char C)
{
	if (n == 1)
	{
		printf("%c -> %c\n", A, C);
	}
	else
	{
		HanoiMove(n - 1, A, C, B);//将n-1个圆盘从A移动到B柱
		printf("%c -> %c\n", A, C);//将第n个圆盘从A移动到C柱
		HanoiMove(n - 1, B, A, C);//将n-1个圆盘从B移动到C柱
	}
		

}

int main()
{
	int n = 0;
	scanf("%d", &n);
	HanoiMove(n, 'A', 'B', 'C');
	return 0;
}

代码测试结果图： 😍
在这里插入图片描述

汉诺塔的难处所在：😊

了解了汉诺塔的移动步数和过程，当我们对64片黄金圆盘移动完需要的时间做一个估算时，你就会发现汉诺塔问题的难处咯！当我们将每次移动看作一秒，那么时间为：2 ^ 64 - 1 = 18,446,744,073,709,551,615秒，换算成年数，约为5800亿年。按照这个进度，移到世界毁灭都不一定能够将64个圆盘全部从A柱移动到C柱上（捂脸）。

函数递归之青蛙跳台阶详解分析🙌

青蛙跳台阶的问题是什么样的问题？😊

青蛙跳台阶问题简述： 😍
一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶。例如:跳上第一级台阶只有一种跳法:直接跳 1 级即可。跳上两级台阶,有两种跳法: 每次跳 1 级,跳两次; 或者一次跳 2 级。问要跳上第 n 级台阶有多少种跳法？

在这里插入图片描述

理清楚思路之后，我们不能发现，青蛙跳台阶的问题也是可以通过函数递归的方法来实现的。
青蛙跳台阶递归代码实现： 😍

int Frog(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else if (n >= 3)
		return Frog(n - 1) + Frog(n - 2);
}
#include<stdio.h>
int main()
{

	int n = 0;
	scanf("%d", &n);
	int ways = Frog(n);
	printf("跳%d阶台阶方法总数为：%d\n", n, ways);
	return 0;
}