用代码实现 打印汉诺塔最优解的过程

废话少说咱们直接开始(‾◡◝)

首先先来看看汉诺塔问题的定义：

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

那我们简化一下问题：变成三个圆盘，毕竟我们也买不起这么多黄金圆盘

（才不是我懒~(￣▽￣)~*）

如图我们要移动三个圆盘到最边上，而且小圆盘上不能放大圆盘

img

那我们分析要让所用圆盘移到右边，很显然根据规则可以知道最下面的圆盘肯定要先移到最右边，不然移动别的大的就放不下了；

同时也可以看出：

要让最下面的圆盘移到最右边，就要让它上面的圆盘移到中间（就像把大象塞进冰箱要怎么办的问题一样）

顺着思路也就可以分析它上面的圆盘移到中间的问题，如果把中间的杆子当成右边的（即目标杆），那问题就变成两层的汉诺塔问题了（底层的那个金盘你会发现有没有都无所谓），那就很显然是一个递归问题了，下面直接写代码（本文采用java）：

（写递归就写过程，不要去太纠结结果）

1
2
3
4
5
6
7
8
9
10
11
//让所用圆盘移到右边    
static void leftToRight(int n) {
        //basecase
        if (n == 1) {
            System.out.println("move" + n + "left to right");
            return;
        }
        leftToMid(n - 1);//让它上面的圆盘移到中间
        System.out.println("move" + n + "left to right");
        midToRight(n - 1);//让它上面的圆盘从中间移到右边完成整个过程
    }

同理写出 leftToMid(n -1) midToRight(n -1)的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static void leftToMid(int n) {
       if (n == 1) {
           System.out.println("move" + n + "left to mid");
           return;
       }
       leftToRight(n - 1);//都是一样的
       System.out.println("move" + n + "left to mid");
       rightToMid(n - 1);//完成整个过程
   }

   private static void rightToMid(int n) {
       if (n == 1) {
           System.out.println("move" + n + "right to mid");
           return;
       }

       rightToLeft(n - 1);//都是一样的
       System.out.println("move" + n + "right to mid");
       leftToMid(n - 1);//完成整个过程
   }

其它的从左从中间。。。我想应该不用我写了把（才不是我懒o(^▽^)o）

但这么长显然代码并不好看，而且能发现递归过程有大量共性，考虑优化一下

将当前位置和目标位置抽象出来

1
2
3
4
5
6
7
8
9
10
//当前位置和目标位置 还有剩余位置抽象出来   
static void fromTo(String from, String other, String to, int n) {
        if (n == 1) {
            System.out.println("move" + n + from + " to " + to);
            return;
        }
        fromTo(from, to, other, n - 1);//other 和 to交换位置 代表当前圆盘的上面的圆盘移到剩余位置
        System.out.println("move" + n + from + " to " + to);
        fromTo(other, from, to, n - 1);//代表当前圆盘的上面的圆盘移到目标位置
    }

大功告成，我相信你也对递归有了更好的理解了吧

不过有个小彩蛋，那就是你会发现这个递归次数成指数增长

因为从递归式可以看出

f(n)=2f(n−1)+1f(n)=2f(n-1)+1

推出---->

f(n)+1=2(f(n)+1)f(n)+1=2(f(n)+1)

k(n)=2k(n−1)k(n)=2k(n-1)

有了递推式就可以写出 f(n)

f(n)=k(n)−1=2n−1f(n)=k(n)-1=2^n-1

也就是n层汉诺塔至少需要这么多步

也就是说64片黄金圆盘需要移动 18446744073709551615次？？？那故事里的金盘移动完怕不是地球都没了

( ‵▽′)ψ

（ps：第一次写，如果有什么不好的欢迎指出( •̀ ω •́ )y）下次见

每日一句：

上善若水，水善利万物而不争。[2]

参考

  1. ^百度百科
  2. ^老子《道德经》