[数据结构学习笔记15] 汉诺塔（Towers of Hanoi）

汉诺塔是个古老的游戏，它可以用递归来解决。

 关于汉诺塔的玩法和介绍，请参考这里。

算法思想：

1. 目标是把最底下，最大的盘从起始柱子移到终点柱子

2. 那我们要先把除了最大的盘的其他盘子从起始柱子移到临时柱子上

3. 然后把最大的盘子从起始柱子移到终点柱子

4. 把除了最大盘的其他盘子从临时柱子移到终点柱子

算法表示：

1. 把top N-1的盘子从开始柱子移到临时柱子

2. 把第N个盘子从开始柱子移到终点柱子

3. 把N-1个盘子从临时柱子移到终点柱子

这个有个要注意的是，在玩的过程中，起始柱子，临时柱子，终点柱子可能都会变化。

代码实现（javascript）

var numberOfDisks = 3;

var hanoi = function (n, a, b, c) {
  if (n > 0) {
       hanoi(n - 1, a, c, b);
       console.log("Move disk " + n + " from " + a + " to " + c + "!");
       hanoi(n - 1, b, a, c);
    }  
}

hanoi(numberOfDisks, "starting", "temporary", "destination");

代码运行结果：

Move disk 1 from starting to destination!

Move disk 2 from starting to temporary!

Move disk 1 from destination to temporary!

Move dist 3 from starting to destination!

Move disk 1 from temporary to starting!

Move disk 2 from temporary to destination!

Move disk 1 from starting to destination!

代码运行过程：

hanoi(3, starting, temporary, destination)
       hanoi(2, starting, destination, temporary)
              hanoi(1, starting, temporary, destination)
                      hanoi(0, starting, destination, temporary)
                      // Move disk 1 from starting to destination!
                      hanoi(0, temporary, starting, destination)


                 // Move disk 2 from starting to temporary!
                 hanoi(1, destination, starting, temporary)
                       hanoi(0, destination, temprary, starting)
                       // Move disk 1 from destination to temporary!
                       hanoi(0, starting, destination, temporary)

                // Move disk 3 from starting to destination!
                hanoi(2, temporary, starting, destination)
                      hanoi(1, temporary, destination, starting)
                      // Move disk 1 from temporary to starting!
                      hanoi(0, destination, temporary, starting)

                    // Move disk 2 from temporary to destination!
                    hanoi(1, starting, temporary, destination)
                          hanoi(0, starting, destination, temporary)
                           // Move disk 1 from starting to destination!
                           hanoi(0, temporary, starting, destination)

可以看到移到汉诺塔是需要反复递归执行的。传说和尚移动的汉诺塔是有64层的。如果要移动64层要移动多少次呢？答案是2^64 - 1次！加入移动一次要花1秒，那么移动64层需要花18,446,744,073,709,551,615秒，大概是5850亿年！