漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

二．抽象為數學問題：

　　如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數

解：（1）n == 1

　　　　　　第1次 1號盤 A---->C sum = 1 次

(2) n == 2

　　　　　　第1次 1號盤 A---->B

　　　　　　 第2次 2號盤 A---->C

　　　　　　第3次 1號盤 B---->C sum = 3 次

　　（3）n == 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 sum = 7 次

不難發現規律：1個圓盤的次數 2的1次方減1

　　　　　　　2個圓盤的次數 2的2次方減1

3個圓盤的次數 2的3次方減1

。 。 。 。 。

n個圓盤的次數 2的n次方減1

故：移動次數為：2^n - 1

三．演算法分析（遞迴演算法）：

我們在利用計算機求漢諾塔問題時，必不可少的一步是對整個實現求解進行演算法分析。到目前為止，求解漢諾塔問題最簡單的演算法還是同過遞迴來求。

實現這個演算法可以簡單分為三個步驟：

　　　　（1） 把n-1個盤子由A 移到 B；

　　　　（2） 把第n個盤子由 A移到 C；

　　　　（3） 把n-1個盤子由B 移到 C；

從這裡入手，在加上上面數學問題解法的分析，我們不難發現，移到的步數必定為奇數步：

　　　　（1）中間的一步是把最大的一個盤子由A移到C上去；

　　　　（2）中間一步之上可以看成把A上n-1個盤子透過藉助輔助塔（C塔）移到了B上，

　　　　（3）中間一步之下可以看成把B上n-1個盤子透過藉助輔助塔（A塔）移到了C上；

public class Hanoilmpl {

public static void hanoi(int n, char A, char B, char C) {

if (n == 1) {

move(A, C);

} else {

hanoi(n - 1, A, C, B);//將n-1個盤子由A經過C移動到B

move(A, C); //執行最大盤子n移動

hanoi(n - 1, B, A, C);//剩下的n-1盤子，由B經過A移動到C

}

}

private static void move(char A, char C) {//執行最大盤子n的從A-C的移動

System.out.println("move:" + A + "--->" + C);

}

public static void main(String[] args) {

System.out.println("移動漢諾塔的步驟：");

hanoi(3, "a", "b", "c");

}

}