漢諾塔算法的理解

當盤子數為兩個時，移動圖如下：

移動規律為：

當盤子數為3個時：

移動規律為：

從以上移動移動規律可以總結出，當步驟序號和盤子數目相同時，就是把最底下的盤子從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