Java如何分析汉诺塔问题

一、汉诺塔问题来源

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘

二、问题分析

从简单问题开始

直接拿64个盘子来想，可能会比较难，我们可以先从1个盘子开始看，如下图：

一个盘子

A -> C 

只有一个盘子情况下，我们可以直接将 A 柱子上面的盘子移到 C 柱子上

需要移动一次

两个盘子

当有两个盘子时，我们也可以通过下面方式实现：

A -> B     A->C     B->C

需要移动3次

1.  A -> B

2.  A -> C

 3.  B -> C

 三个盘子

 当有三个盘子时，移动步骤如下：

A -> C     A -> B     C -> B     A -> C     B -> A     B -> C     A -> C

共需要移动7次 

 1.  A -> C

2.  A -> B

 3.  C -> B

4.  A -> C

 5.  B -> A

 6.  B -> C

 7.  A -> C

这就完成了3个盘子的移动

当有 4 个盘子时，这个问题其实就已经很复杂了

规律推导

1个盘子      移动1次

2个盘子      移动3次

3个盘子      移动7次

……

N 个盘子    移动 2^N - 1 次

那么64个盘子就是需要移动 2^64 - 1 次

三、解决问题

我们可以通过递归来解决这个问题，获得正确的移动方式

如果有N个盘子该怎么移动呢？

整体思路

我们可以先将 N - 1 个盘子从 A 柱借助 C 柱移动到 B 柱，再将 A 柱剩下的一个盘子移动到 C柱，然后将 B 柱上的 N - 1 个盘子借助 A 柱移动到 C 柱，就完成了所有柱子的移动（中间具体移动过程暂不讨论）

上代码

public static void hanoi(int num, String src, String help, String dest) {
    if (num == 1) {     // 只有一个盘子的时候直接移动
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
    } else {
        hanoi(num - 1, src, dest, help);   // 将n - 1个盘子从源柱子借助目标柱子挪到辅助柱子
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
        hanoi(num - 1, help, src, dest);  // 将辅助柱子上n - 1个盘子借助源柱子挪到目标柱子
    }
}
public static void main(String[] args) {
    hanoi(3, "A", "B", "C");
}

这段代码中 src 是源柱子，help是辅助柱子，dest 是目标柱子

这是一个二路递归

运行结果：

 这就成功完成了盘子的移动

四、婆罗门能否完成大梵天的任务

移动 64 个盘子需要多长时间

在这里我们假设婆罗门的人都非常聪明，不需要思考就直接能知道正确的移动方法，移动一个盘子需要一秒钟，一直不停的移

将2^64 - 1秒换算为年约为5849 4241 7355年（5849.42亿年），而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5849.42亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

相关预言

有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘

计算机移动64个盘子需要多长时间 ？

我的电脑核心频率为2.90GHz，也就是每秒钟运算 29 亿次，那么移动 2^64 - 1次需要的时间约为201年