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

            x                y                 z

解决汉诺塔问题的关键在于有整体思维. 假如将最后一个盘子上面的所有盘子看着一个整体 M_n-1最后一个盘子看作M_n,这时候问题移动方式:

   1 ,将M_n-1移动到y.

   2 ,将M_n移动到z .

   3, 将M_n-1移动到z, 移动完毕.

于是问题变为如何将 M_n-1 从x移动到y 这里我们在借助上面的思想将 M_n-1  拆分位M_n-2 和 M_n-1俩个部分,将于是原先的 z柱子看作原先的y 柱子.于是Mn-1的移动方式变为.

   1, 将M_n-2 移动到z.

   2,将M_n-1 移动过到y.

   3,将M_n-2 移动到y.

不断递推直到n =1

golang的代码实现:

package main

import "fmt"

/***
   n 当前递归盘子数量
   x 当前递归的初始盘子所在的柱子
   y 当前递归要借用的柱子
   z 要移动到的柱子
 */
func hannuota(n int, x, y, z byte) {
   //将最后一个盘子上面的n-1盘子借助z移动到y
   if (n == 1) {
      fmt.Printf("将第%d个盘子从%c->%c\n", n, x, z)
      return
   }
   hannuota(n-1, x, z, y)
   //最下面的正好可以移动到z
   fmt.Printf("将第%d个盘子从%c->%c\n", n, x, z)
   //将当前在y上面的n-1盘子借助x移动到z
   hannuota(n-1, y, x, z)
}

func main() {
   hannuota(4, 'x', 'y', 'z')
}

运行结果:

将第1个盘子从x->y

将第2个盘子从x->z

将第1个盘子从y->z

将第3个盘子从x->y

将第1个盘子从z->x

将第2个盘子从z->y

将第1个盘子从x->y

将第4个盘子从x->z

将第1个盘子从y->z

将第2个盘子从y->x

将第1个盘子从z->x

将第3个盘子从y->z

将第1个盘子从x->y

将第2个盘子从x->z

将第1个盘子从y->z