使用递归的思想解决汉诺塔问题
使用递归的思想解决汉诺塔问题
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，
假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31557600秒，计算一下：
18446744073709551615秒
这表明移完这些金片需要5845.42亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.42亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
我在网上找到了一个简单的汉诺塔游戏的网站，汉诺塔小游戏，感兴趣的可以去试着玩一玩，通过传说我们也了解了游戏规则，就是：每次只能移动一个盘子，且大盘子不能放到小盘子之上; 总共三个塔座，一个起始塔座，一个中间塔座作为辅助，一个目标塔座。
如何使用递归的方法去解决汉诺塔问题呢，让我们来一步一步的分析吧。
首先，假如起始塔座只有一个盘子，那么直接将它移动到目标塔座就好了，假如起始塔座有超过1个的盘子，那么就比较麻烦了，我们发现，要想将所有盘子移动到目标塔座，就要先将最大的盘子移动到目标，而要想做到这一步，就要将它上面的所有盘子移动到中间塔座，再将最大的盘子移动到目标塔座，最后将中间塔座的其余盘子移动到目标塔座，问题变简单了是不是，问题变成了如何将上面的几个盘子从中间塔座移动到目标塔座（少了一个盘子）。
就拿本文的图片中的例子来讲，有四个盘子，要将4号盘子移动到目标塔座，就要将上面的三个盘子先全部移动到中间塔座，再将最大的盘子移动到目标塔座，最后将中间塔座上面的三个盘子移动到目标塔座，这个时候变成了移动三个盘子的问题。
这个时候，要将中间塔座上的三个盘子全部移动到目标塔座，就要现将上面的两个盘子移动到第一个塔座，也就是原来的起始塔座，再将第三个盘子移动到目标塔座，最后将前面移动到第一个塔座的两个盘子移动到目标塔座。这个时候问题变成了移动两个盘子的问题。
这个时候，要将第一个塔座上的两个盘子移动到目标塔座，就要先将最上面的一个盘子移动到中间塔座，再将第二个盘子移动到目标塔座，最后将中间塔座上面的最后一个盘子移动到目标塔座。移动完成。
递归的思想解决这个问题，就是将问题一步步分解为简单的问题，通过编程解决这个问题，那么就不用考虑中间乱七八糟的情况，我们只知道假如剩下一个盘子，则直接将盘子移动到目标塔座，其余的情况，就要借助中间塔座；说着有点儿绕，直接看代码吧，我的注释还是比较清楚的，我就不信你不理解。
汉诺塔代码：
package hanoitower;
public class HanoiTower {
// 计算移动次数
private static long MoveCount;
/**
* 移动方法，传递参数分别是 盘子数，起始塔座，中间塔座，目标塔座
* 递归算法
* @param PlateNumber
* @param OriginTower
* @param IntermediateTower
* @param TargetTower
*/
public static void Move(int PlateNumber, String OriginTower, String IntermediateTower, String TargetTower ) {
// 当只有一个盘子时，直接将盘子从起始塔座移动到目标塔座
if(PlateNumber == 1) {
System.out.println("盘子1 从"+OriginTower+"座 移动到 "+TargetTower+"座");
MoveCount++;
}else {
// 如果盘子数大于1,就要将移动n个盘子的问题变成移动n-1个盘子的问题
// 比如，要将三个盘子从A移动到C，就要现将上面的两个盘子移动到B
Move(PlateNumber-1, OriginTower, TargetTower, IntermediateTower);
// 剩下的最大一个盘子直接移动到C
System.out.println("盘子"+PlateNumber+" 从"+OriginTower+"座 移动到 "+TargetTower+"座");
MoveCount++;
// 现在，上面的两个盘子都在B，A则变成了中间座
// 问题变成了将两个盘子从B起始，通过A，移动到C的问题
Move(PlateNumber-1, IntermediateTower, OriginTower, TargetTower);
}
}
/**
* 显示最少的移动次数
*/
public static void MoveCounts() {
System.out.println("最少需要移动"+MoveCount+"步");
}
}
测试代码：
package hanoitower;
public class TestHanoiTower {
public static void main(String[] args) {
HanoiTower.Move(5, "A", "B", "C");
HanoiTower.MoveCounts();
}
}
控制台输出结果：
盘子1 从A座 移动到 C座
盘子2 从A座 移动到 B座
盘子1 从C座 移动到 B座
盘子3 从A座 移动到 C座
盘子1 从B座 移动到 A座
盘子2 从B座 移动到 C座
盘子1 从A座 移动到 C座
盘子4 从A座 移动到 B座
盘子1 从C座 移动到 B座
盘子2 从C座 移动到 A座
盘子1 从B座 移动到 A座
盘子3 从C座 移动到 B座
盘子1 从A座 移动到 C座
盘子2 从A座 移动到 B座
盘子1 从C座 移动到 B座
盘子5 从A座 移动到 C座
盘子1 从B座 移动到 A座
盘子2 从B座 移动到 C座
盘子1 从A座 移动到 C座
盘子3 从B座 移动到 A座
盘子1 从C座 移动到 B座
盘子2 从C座 移动到 A座
盘子1 从B座 移动到 A座
盘子4 从B座 移动到 C座
盘子1 从A座 移动到 C座
盘子2 从A座 移动到 B座
盘子1 从C座 移动到 B座
盘子3 从A座 移动到 C座
盘子1 从B座 移动到 A座
盘子2 从B座 移动到 C座
盘子1 从A座 移动到 C座
最少需要移动31步
也可以去文章前面提到的小游戏中去验证方案是否可行。
也可以试着跑一跑64个盘子的情况
运行后，CPU的情况有点儿吓人啊，哈哈，估计我这破机子，把自己跑废了也跑不完。