汉诺塔算法的理解

fdwm 10年前

当盘子数为两个时，移动图如下：

汉诺塔算法的理解

移动规律为：

步骤 盘子编号 源柱子 目标柱子
1 1
 A B
2 2 A C
3 1 B C

当盘子数为3个时：

汉诺塔算法的理解

移动规律为：

步骤 盘子编号 源柱子 目标柱子
1 1 A C
2 2 A B
3 1 C B
4 3 A C
5 1 B A
6 2 B C
7 1 A C

从以上移动移动规律可以总结出，当步骤序号和盘子数目相同时，就是把最底下的盘子从A移动到C，其它的步骤都是对等的，规律如下：

  1. 中间以上动作是：源柱子(A)不变，目标柱子为C，辅助柱子为B进行移动，也就是

    源柱子->目标柱子

    源柱子->辅助柱子

    目标柱子->辅助柱子

  2. 中间动作：从A到C也就是从源柱子到目标柱子

  3. 中间以下动作：源柱子是B，目标柱子为C，辅助柱子为A进行移动，也就是

    源柱子->辅助柱子

    源柱子->目标柱子

    辅助柱子->目标柱子

按照以上规律，可以大概总结出实际上移动的主要动作实际上就是在重复三步动作，用java代码可以表示如下： 

/**   * @author lenovo   *   */  public class Hanoi {      /**      *       * @param n 盘子的数目      * @param origin 源座      * @param assist 辅助座      * @param destination 目的座      */      public void hanoi(int n, char origin, char assist, char destination) {          if (n >= 1) {              hanoi(n - 1, origin, destination, assist);              System.out.println("Direction:" + origin + "--->" + destination);              hanoi(n - 1, assist, origin, destination);          }      }          public static void main(String[] args) {          Hanoi hanoi = new Hanoi();          hanoi.hanoi(3, 'A', 'B', 'C');      }  }

一开始我理解这个算法的时候老是一直在分析程序的出栈，入栈动作，后面看了这篇文章汉诺塔的递归算法与解析才有点恍然大悟，这个算法实际上是考验对递归思想的理解：总结事物的规律，然后再用程序表达出来。

来自：http://my.oschina.net/u/914897/blog/403306