經典遞歸----漢諾塔（Hanoi Tower）JAVA實作

問題分析

漢諾塔問題是一個經典的問題。漢諾塔（Hanoi Tower），又稱河内塔，源于印度一個古老傳說。

大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞着64片黃金圓盤。

大梵天指令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。

并且規定，任何時候，在小圓盤上都不能放大圓盤，且在三根柱子之間一次隻能移動一個圓盤。

問應該如何操作？

遞歸的思想就是把難題簡單化，假設三根柱子我們分别命名為A、B、C

，我們的想法就是把A上的圓盤轉移到C柱上。

• 假設A盤隻有一個圓盤，那麼我們隻需要執行A->C
• 假設A盤有兩個圓盤，那麼我們需要執行A->B,A->C,B->C
• 假設A盤有三個圓盤，那麼我們需要執行A->C，A->B,C->B,A->C,B->A,B->C,A->C

我們發現若A柱上的圓盤增加一個，需要執行的次數成會越來越多，這樣寫下去不僅麻煩，還容易寫錯。執行的次數為n ^ 2 -1，若A柱上有6個，就需要移動63次，是以我們會這樣想：如果有人把A柱上的前5個都先轉移到B柱上，那麼我隻需要将A柱上的第6個圓盤轉移到C柱上，再将B柱上的5個轉移到C柱上不就可以了。

通過以上分析，我們假設要移動n個圓盤，那麼相對應的就應該有三步：

1. 将n-1個圓盤從A柱移動到B柱
2. 将第n個圓盤從A柱移動到C柱
3. 将n-1個圓盤從B柱移動到C柱

整理好思路，我們來看遞歸代碼

代碼實作

//設定靜态變量，記錄執行的次數
static int m=0;
//列印輸出将圓盤從A柱上移動到C柱上，
public static void move(char A,char C){
        System.out.println("第"+(++m)+"次"+"移動，将"+A+"移到"+C);
    }
    //定義A，B，C柱，n代表A柱上的圓盤數量，
    //實際上這個函數是将A柱上的圓盤移動到c柱，B柱隻是輔助盤
public static void hnota(int n,char A,char B,char C){
        if(n==1) {
        //當A柱上隻有一個圓盤時，直接移動，這也是終止條件
            Test.move(A,C);
        }else{
        	//将n-1個圓盤從A柱移動到B柱
            hnota(n-1,A,C,B);
            //将第n個圓盤從A柱移動到C柱
            move(A,C);
            //将n-1個圓盤從B柱移動到C柱,将A柱作為輔助柱
            hnota(n-1,B,A,C);
        }

    }
           

大家可以參照我這個自己動手寫一下，最後附上代碼（n==4）運作結果：