當然、這是一個經典的遞歸問題~
想必來看這篇博文的同學對漢諾塔應該不會陌生了吧，
寫這篇博還是有初衷的：
之前學數據結構的時候自己看書、也上網上查了很多資料，資料都比較散、而且描述的不是很清楚，對于當時剛剛
接觸算法的我，要完全理解還是有一定難度。今天剛好有時間就整理了下思路、重寫分析了一下之前的疑惑的地方、
沒有透徹的地方便都豁然開朗了。所以迫不及待把我的想法記錄下來，和大家分享。
如果你也是和之前的我一樣對hanoi tower沒能完全消化，或者剛剛接觸漢諾塔，那希望我的這種理解方式能給你些
許幫助，如果你覺得已經完全掌握的比較牢靠了，那也可以看看，有好的idea可以一起分享；畢竟交流討論也是一種很好的
學習方式。
好了，廢話不多說，切入正題。
關于漢諾塔起源啊、傳說啊神馬的就不啰嗦了，我們直接切入正題：
問題描述：
有一個梵塔，塔內有三個座A、B、C，A座上有諾干個盤子，盤子大小不等，大的在下，小的在上（如圖）。
把這些個盤子從A座移到C座，中間可以借用B座但每次只能允許移動一個盤子，并且在移動過程中，3個座上的盤
子始終保持大盤在下，小盤在上。
描述簡化：把A柱上的n個盤子移動到C柱，其中可以借用B柱。
2011111320150185.gif (2.24 KB, 下載次數: 136)
下載附件
2016-5-8 22:02 上傳
我們直接假設有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階漢諾塔問題：");
- 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",A,C,n);
- }
- else
- {
- hanoi(A,C,B, n-1);
- printf("Move disk %d from %c to %c",n,A,C);
- hanoi(B,A,C,n-1,);
- }
- }
- //以上代碼c-free5編譯通過。
以上、如果有不對的地方、還希望您能指出。
我對遞歸的一點理解：
解決實際問題時、不能太去關心實現的細節（因為遞歸的過程恰恰是我們實現的方法）就像這個問題，如在第一步就過多的糾結于如何把n-1個盤子移動到B上、那么你的思路就很難繼續深入。只要看做是用函數實現就好，如果你能看出不管怎么移動，其實本質都一樣的時候，那么就能較快的得到結果了。就像這個案例，要注意到我們做的關鍵幾步都只是移動的順序有改變，其中的規則沒有改變，如
如果用函數表示的話，就只是參數調用的順序有所不同了。在遞歸的運用中、不用關心每一步的具體實現 ，只要看做用一個函數表示就好。分析問題的時候，最好畫出自己的推理過程，得到有效的狀態圖。
思考問題講求思路的連貫性、力求盡快進入狀態，享受完全投入到一件事中的美妙感覺。
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
