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移动到bHanoi(a, c, b, n - 1);//2.将1个圆盘，从a移动到cprintf("%c -> %c\n", a, c);//3.将n-1个圆盘，从b移动到cHanoi(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;}递归的优缺点
优点：
非常明显，这种大事化小的思维方式，可以大大缩减我们的代码量，便于理解理解整体逻辑
缺点：
- 与现实生活的思维方式相差较大，不容易想
- 递归程度太深会造成栈溢出(例如死递归)
- 部分题目用递归实现特别低效(例如斐波那契)
64层汉诺塔等于宇宙毁灭？
已经有人开玩笑说：等你把64层汉诺塔解完，宇宙的毁灭了。
其实这也是可能的，前提是那个人是一个永生的人。
百度百科上面查询到，28亿宇宙将灭亡，咱们也不是什么大科学家，姑且不谈其真假性，我们来计算一下人解完64层需要花多少时间。
首先我们计算一下n层汉诺塔，需要移动圆盘多少次？
咱们使用上面的程序来找找规律，当然如果你是一个数学大佬，也可以使用数学知识来计算。
n = 3–7次
n = 4–15次
![在这里插入图片描述]
找规律我们不难发现，n层汉诺塔需要移动圆盘 2的n次方减1次，如果说64层汉诺塔
那就需要移动圆盘2^64 – 1次，即1844.67亿亿
如果一个人移动一次圆盘需要1秒钟，也需要1844.67亿亿秒，很明显，宇宙大人早就去世了。
假如你对你的校园女神表白了，而你的女神说等你解完64层汉诺塔就嫁给你，那…………这肯定是一个悲伤的故事
建议兄弟回家打开网易云。
OK，咱们折起就讲到这里，希望大家能够听懂汉诺塔问题，咱们下期见！
