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