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