前言
相信学过《数据结构与算法》这门课程的同学都有听过汉诺塔问题，但是可能在大学的时候没有钻研过，或者在学的时候就没有弄懂，导致没有很好的理解汉诺塔的经典解法，下面让我来给大家来分析一下。
背景
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三个金刚石塔，在一个塔上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在最后一个塔上。并且规定，在小圆盘上不能放大圆盘，在三个塔之间一次只能移动一个圆盘。
分析
对圆盘编号1~n，数字大的圆盘比数字小的圆盘体积大。并且引入起始塔，中转塔，目标塔的概念，在算法运行的时候，这３个塔的身份可能会互相变换。
1.如果现在在塔A上面只有1个圆盘，那么直接把圆盘移动到塔C即可；
2.如果现在在塔A上面有2个圆盘，那么先把圆盘1从塔A移动到塔B，再把圆盘2从塔A移动到塔C，最后把圆盘1从塔B移动到塔C；
3..……
4.如果塔A有n个圆盘，那么需要先把圆盘n之前的(圆盘n-1~ 圆盘1)从塔A先移动到塔B，再把圆盘n从塔A移动到塔C，最后把放在塔B的(圆盘n-1~圆盘1)从塔B移动到塔C。
可以看出，上面的解法是很典型的分治法算法思想。
因为汉诺塔要求一次只能移动一个圆盘，并且小圆盘上面不能放大圆盘，所以需要把同一个塔最底下的大圆盘上面的圆盘搬走。要想移动圆盘ｎ，那么先要移动其上的(圆盘n-1~ 圆盘1)到中转塔，要想移动(圆盘n-1~ 圆盘1)中的圆盘n-1，那么先要移动其上的(圆盘n-2~ 圆盘1)到中转塔，依次类推……直到只有一个圆盘1，那么直接移动即可。同时，因为我们的目的是把所有的圆盘移动到目标塔，所以在移动完圆盘n到目标塔之后，需要把之前放在中转塔上的(圆盘n-1~圆盘1)移动到目标塔。
可能大家会说了，道理都懂，但是代码该如何写呢？其实这也是算法学习中比较占时间的部分，用计算机编程语言把算法表示（写）出来。下面给大家附上经典的实现，分析为何要这样写，并介绍一种我自己平时理解递归所用的思考方法。
Java版算法实现
一般来说，分治法总是结合递归去实现，以下示例代码就用了递归结构。
在写递归结构的时候，可以从语义层面去出发。思考过程如上面分析所示：我们需要写一个函数，它的作用是把圆盘n~圆盘1由一个起始塔移动到目标塔，由于要求要先移动圆盘n上面的圆盘后才能移动圆盘n，所以需要一个中转塔。经过这样的思考过程之后，我们就可以确定函数的签名了，即void hanoi(int n, String sourceTower, String tempTower, String targetTower)。
根据算法，函数体里面就可这样写（语义层面）：
如果当前为盘子1，那么直接移动到目标塔 move(n, sourceTower, targetTower)；
否则先将圆盘n-1~圆盘1移动到中转塔hanoi(n - 1, sourceTower, targetTower, tempTower)，移动完之后把圆盘n先移动到目标塔move(n, sourceTower, targetTower)，再把中转塔上的圆盘n-1~圆盘1移动到目标塔hanoi(n - 1, tempTower, sourceTower, targetTower)。
public class Hanoi {
public static void hanoi(int n, String sourceTower, String tempTower, String targetTower) {
if (n == 1) {
//如果只有一个盘子1，那么直接将其从sourceTower移动到targetTower
move(n, sourceTower, targetTower);
} else {
//将（盘子n-1~盘子1）由sourceTower经过targetTower移动到tempTower
hanoi(n - 1, sourceTower, targetTower, tempTower);
//移动盘子n由sourceTower移动到targetTower
move(n, sourceTower, targetTower);
//把之前移动到tempTower的（盘子n-1~盘子1），由tempTower经过sourceTower移动到targetTower
hanoi(n - 1, tempTower, sourceTower, targetTower);
}
}
//盘子n的从sourceTower->targetTower的移动
private static void move(int n, String sourceTower, String targetTower) {
System.out.println("第" + n + "号盘子 move:" + sourceTower + "--->" + targetTower);
}
public static void main(String[] args) {
System.out.println("移动汉诺塔的步骤：");
hanoi(3, "a", "b", "c");
}
}
运行结果:
移动汉诺塔的步骤：
第1号盘子 move:a--->c
第2号盘子 move:a--->b
第1号盘子 move:c--->b
第3号盘子 move:a--->c
第1号盘子 move:b--->a
第2号盘子 move:b--->c
第1号盘子 move:a--->c
可以发现，对于一次调用hanoi(n, sourceTower, tempTower, targetTower)，中转塔是给圆盘n-1~圆盘1用的。从语义上理解，hanoi(n, sourceTower, tempTower, targetTower)最终的调用效果是圆盘n~圆盘1从起始塔全部移动到了目标塔，并按要求（在小圆盘上不能放大圆盘）所有圆盘都放在目标塔上了。
可能有些同学还是不能理解为什么满足了在小圆盘上不能放大圆盘的的这个要求，很简单，因为我们每次想移动圆盘n的时候，都已经把圆盘n上面的圆盘拿走了，移动完圆盘n之后，再把其他圆盘移动到圆盘n所在的塔上，所以当然是满足了在小圆盘上不能放大圆盘的的这个要求。如果还是不能明白的话，可以从2个圆盘的情况和3个圆盘的情况去模拟看看。
附上一个算法调用的分析图：
3阶汉诺塔分析.png
总结
平时在用分治法解决问题的时候，先根据分治法的原则把问题逐步拆分。而分治法往往需要和递归结合起来去写代码，阅读或者设计递归结构的时候可以从语义的层面出发去进行。
与分治法一样，回溯法也可以跟递归结合去实现。但是两者还是有些许区别的。
分治法使用递归解决问题，问题一般是有解的。如汉诺塔，链表反转。
回溯法使用递归试探问题的解法，可能会无解。如迷宫问题，深度遍历。
结语
其实钻研算法的确挺烧脑的，而且需要投入比较多的时间。很多人觉得有这时间还不如去看看别的框架更好。其实吧，如果想在计算机领域成为大牛，算法知识是必不可少的。本人很喜欢看动漫《一拳超人》，里面有一句台词“兴趣使然”。确实，我觉得算法是最能体现计算机科学之魅力的东西，所以研究算法就不会觉得无聊，因为“兴趣使然”。
——写于2018中秋佳节。
网友评论