當然、這是一個經(jīng)典的遞歸問題~
想必來看這篇博文的同學對漢諾塔應該不會陌生了吧，
寫這篇博還是有初衷的：
之前學數(shù)據(jù)結構的時候自己看書、也上網(wǎng)上查了很多資料，資料都比較散、而且描述的不是很清楚，對于當時剛剛
接觸算法的我，要完全理解還是有一定難度。今天剛好有時間就整理了下思路、重寫分析了一下之前的疑惑的地方、
沒有透徹的地方便都豁然開朗了。所以迫不及待把我的想法記錄下來，和大家分享。
如果你也是和之前的我一樣對hanoi tower沒能完全消化，或者剛剛接觸漢諾塔，那希望我的這種理解方式能給你些
許幫助，如果你覺得已經(jīng)完全掌握的比較牢靠了，那也可以看看，有好的idea可以一起分享；畢竟交流討論也是一種很好的
學習方式。
好了，廢話不多說，切入正題。
關于漢諾塔起源啊、傳說啊神馬的就不啰嗦了，我們直接切入正題：
問題描述：
有一個梵塔，塔內(nèi)有三個座A、B、C，A座上有諾干個盤子，盤子大小不等，大的在下，小的在上（如圖）。
把這些個盤子從A座移到C座，中間可以借用B座但每次只能允許移動一個盤子，并且在移動過程中，3個座上的盤
子始終保持大盤在下，小盤在上。
描述簡化：把A柱上的n個盤子移動到C柱，其中可以借用B柱。
我們直接假設有n個盤子：
先把盤子從小到大標記為1、2、3......n
先看原問題三個柱子的狀態(tài)：
狀態(tài)0 A：按順序堆放的n個盤子。B:空的。C：空的。
目標是要把A上的n個盤子移動到C。因為必須大的在下小的在上，所以最終結果C盤上最下面的應該是標號為n的盤子，試想：
要取得A上的第n個盤子，就要把它上面的n-1個盤子拿開吧？拿開放在哪里呢？共有三個柱子：A顯然不是、如果放在C上
了，那么最大的盤子就沒地方放，問題還是沒得到解決。所以選擇B柱。當然，B上面也是按照大在下小在上的原則堆放的
（記住：先不要管具體如何移動，可以看成用一個函數(shù)完成移動，現(xiàn)在不用去考慮函數(shù)如何實現(xiàn)。這點很重要）。
很明顯：上一步完成后三個塔的狀態(tài)：
狀態(tài)1： A：只有最大的一個盤子。B：有按規(guī)則堆放的n-1個盤子。C空的。
上面的很好理解吧，好，其實到這里就已經(jīng)完成一半了。（如果前面的沒懂，請重看一遍。point：不要管如何移動！）
我們繼續(xù)：
這時候，可以直接把A上的最大盤移動到C盤，移動后的狀態(tài)：
中間狀態(tài)： A：空的。B：n-1個盤子。C：有一個最大盤（第n個盤子）
要注意的一點是：這時候的C柱其實可以看做是空的。因為剩下的所有盤子都比它小，它們中的任何一個都可以放在上面，也就是 C柱上。
所以現(xiàn)在三個柱子的狀態(tài)：
中間狀態(tài)： A：空的。B：n-1個盤子。C：空的
想一想，現(xiàn)在的問題和原問題有些相似之處了吧？。。如何更相似呢？。顯然，只要吧B上的n-1個盤子移動到A，待解決的問題和原問題就相比就只是規(guī)模變小了
現(xiàn)在考慮如何把B上的n-1個盤子移動到A上，其實移動方法和上文中的把n-1個盤從A移動到B是一樣的，只是柱子的名稱換了下而已。。（如果寫成函數(shù)，只是參數(shù)調(diào)用順序改變而已）。
假設你已經(jīng)完成上一步了（同樣的，不要考慮如何去移動，只要想著用一個函數(shù)實現(xiàn)就好），請看現(xiàn)在的狀態(tài)：
狀態(tài)2： A：有按順序堆放的n-1個盤子。B：空的。C：按順序堆放的第n盤子(可看為空柱)
就在剛才，我們完美的完成了一次遞歸。如果沒看懂請從新看一遍，可以用筆畫出三個狀態(tài)、靜下心來慢慢推理。
我一再強調(diào)的：當要把最大盤子上面的所有盤子移動到另一個空柱上時，不要關心具體如何移動，只用把它看做一個函數(shù)可以完成即可，不用關心函數(shù)的具體實現(xiàn)。如果你的思路糾結在這里，就很難繼續(xù)深入了。
到這里，其實 基本思路已經(jīng)理清了。狀態(tài)2和狀態(tài)0，除了規(guī)模變小 ，其它方面沒有任何區(qū)別了。然后只要用相同的思維方式，就能往下深入。。。
好了，看看如何用算法實現(xiàn)吧：
定義函數(shù)Hanoi（a,b,c,n）表示把a上的n個盤子移動到c上，其中可以用到b。
定義函數(shù)move(m,n)表示把m上的盤子移動到n上
我們需要解決的問題正是 Hanoi (a,b,c,n) //上文中的狀態(tài)0
1、把A上的n-1個移動到B： Hanoi (a,c,b,n-1); // 操作結束為狀態(tài)1
2、把A上的大盤子移動到C move(a,c)
3、把B上的n-1移動到A Hanoi (b,c,a,n-1); //操作結束位狀態(tài)2(和狀態(tài)1相比只是規(guī)模變小)
如果現(xiàn)在還不能理解、請回過頭再看一遍、畢竟如果是初學者不是很容易就能理解的。可以用筆記下幾個關鍵的狀態(tài)，并且看看你有沒有真正的投入去看，獨立去思考了。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Hanoi {
public static void main(String[] args) throws IOException{
int n;
BufferedReader buf;
buf = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please input the number of disk ");
n = Integer.parseInt(buf.readLine());
Hanoi hanoi = new Hanoi();
hanoi.move(n,'A','B','C');
}
public void move(int n, char a, char b, char c){
if(n == 1){
System.out.println("Disk " + n + " From " + a + " To " + c);
}
else{
move(n-1,a,c,b);
System.out.println("Disk " + n + " From " + a + " To " + c);
move(n-1,b,a,c);
}
}
}
以上、如果有不對的地方、還希望您能指出。
我對遞歸的一點理解：
解決實際問題時、不能太去關心實現(xiàn)的細節(jié)（因為遞歸的過程恰恰是我們實現(xiàn)的方法）就像這個問題，如在第一步就過多的糾結于如何把n-1個盤子移動到B上、那么你的思路就很難繼續(xù)深入。只要看做是用函數(shù)實現(xiàn)就好，如果你能看出不管怎么移動，其實本質(zhì)都一樣的時候，那么就能較快的得到結果了。就像這個案例，要注意到我們做的關鍵幾步都只是移動的順序有改變，其中的規(guī)則沒有改變，如
如果用函數(shù)表示的話，就只是參數(shù)調(diào)用的順序有所不同了。在遞歸的運用中、不用關心每一步的具體實現(xiàn) ，只要看做用一個函數(shù)表示就好。分析問題的時候，最好畫出自己的推理過程，得到有效的狀態(tài)圖。
思考問題講求思路的連貫性、力求盡快進入狀態(tài)，享受完全投入到一件事中的美妙感覺
-----------------------------------------------------
Silence, the way to avoid many problems;
Smile, the way to solve many problems;