宇宙都要毁灭了你还在玩汉诺塔？(动画讲解汉诺塔问题)

CSDN话题挑战赛第2期
参赛话题：学习笔记

前言
💖作者：龟龟不断向前
✨简介：宁愿做一只不停跑的慢乌龟，也不想当一只三分钟热度的兔子。
👻专栏：C++初阶知识点

👻工具分享：

刷题：牛客网 leetcode
笔记软件：有道云笔记
画图软件：Xmind(思维导图) diagrams(流程图)

如果觉得文章对你有帮助的话，还请点赞，关注，收藏支持博主🙊，如有不足还请指点，博主及时改正

文章目标：

汉诺塔的规则
分析汉诺塔的逻辑
汉诺塔的代码实现
汉诺塔的移动次数–宇宙毁灭

汉诺塔问题

汉诺塔背景/规则

汉诺塔问题源自印度一个古老的传说，印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱，其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：

每次只能移动柱子最顶端的一个圆盘；
每个柱子上，小圆盘永远要位于大圆盘之上；

汉诺塔问题，实际上也是一个递归问题(没学习递归的同学，可以点击链接学习)

在这里插入图片描述

汉诺塔解法

动画讲解递归思路

我们从圆盘个数上，从少到多，来分析一下解决方法，一下我们用n来表示圆盘个数

我们用A B C或者起始柱辅助柱目标柱来表示柱子

n = 1时

在这里插入图片描述

n = 2

在这里插入图片描述

n = 3

在这里插入图片描述

这里并不是步遵守游戏规则，一次将两个圆盘从A般到B，而是两个圆盘的情况已经在n = 2的时候演示了

n = 4

在这里插入图片描述

同样的，3层的哈诺塔也已经在n = 3的时候演示。

类推：无论多少个圆盘，就能给他分解成三步，就类似于把大象装进冰箱

在这里插入图片描述

即无论有多少个圆盘，都可以按三步进行分解。

在这里插入图片描述

递归思路：有n个圆盘需要从A(起始柱)移到C(目标柱)，借助B(辅助柱)

可以分解陈有n -1圆盘从A移动到B，底盘从A移动到C，n-1个圆盘从B移动到C

特别注意，进行多圆盘移动的时候，是需要辅助柱的

代码实现汉诺塔

void Hanoi(char a,char b,char c,int n)
{
	if (n == 0)//圆盘数为0，直接返回,递归的限制条件
	{
		return;
	}
	//1.将n-1个圆盘，从a移动到b
	Hanoi(a, c, b, n - 1);
	//2.将1个圆盘，从a移动到c
	printf("%c -> %c\n", a, c);
	//3.将n-1个圆盘，从b移动到c
	Hanoi(b, a, c, n - 1);
}

int main()
{
	int num = 0;

	printf("请输入圆盘个数\n");//有 A B C三个支柱
	scanf("%d", &num);

	Hanoi('A', 'B', 'C', num);
	//第一个参数是：起始柱
	//第三个参数是：目标柱
	//第二个参数是：辅助柱
	//第四个参数：圆盘的个数
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28