目录
🍉前言
上期文章我们对c语言中的冒泡排序进行了详细的分析，对于什么是冒泡排序，冒泡排序的思想，怎么实现它进行了分析，让大家对冒泡排序有了清晰的认识。接下来会对汉诺塔问题进行讲解，大家可以端上小板凳了。
🍊什么叫汉诺塔
汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。这就是汉诺塔的来源，现在逐渐演变成了一个益智游戏。大家可以想一想，移动这64片圆盘需要多少次呢？今天我们就用函数的递归来实现一下。
🍑汉诺塔移动过程分析
汉诺塔的规则是：有abc三根柱子，要a柱子上的盘子都移动到c盘上。要求是每次只能移动一个，且大盘子要在小盘子的下面。这里我们以三阶汉诺塔为例来进行分析，通过分析我们可以发现可以分为三步：第一步 将n-1个通过c柱子移动到b柱子 第二步 将第n个移动到c柱子 第三步 将n-1个通过a柱子移动到c柱子
🍓汉诺塔移动次数分析
对于这么难以计算的问题，我们可以通过穷尽法来从中找规律：
阶层 |
次数 |
规律 |
1 |
1 |
2^1-1 |
2 |
3 |
2^2-1 |
3 |
7 |
2^3-1 |
4 ...... n |
15 ...... ...... |
2^4-1 ...... 2^n-1 |
通过穷尽法，我们发现，这个汉诺塔的移动次数是成指数增长的。当有64个盘子时，我们需要移动2^64次=18446744073709551616次，如果一次一秒，婆罗门要移动5833亿年!
n阶移动的次数：和上面说的可分为三步，可以把步骤一将n-1个通过c柱子移动到b柱子的次数为f(x-1),步骤二为1，步骤三n-1个通过a柱子移动到c柱子的次数也为f(x-1). 这n的次数为2*F(x-1)-1;
🥝具体代码分析
用函数递归求移动的次数
用函数递归打印移动的过程
🍇总结
我们可以发现在思考汉诺塔这样的问题的时候，在脑子里想是很难想明白的。这时我们就需要借助图形在宏观的帮助我们了解 ，使问题清晰化。
