140 阿裏雲技術社區[雲棲]

學習筆記（菜鳥日誌）-"漢諾塔"的遞歸過程

記得大一上C語言課程的時候我還剛剛會用迅雷下載電影，聽不懂，也沒認真聽過，匆匆幾個星期上完了考試。關於“漢諾塔”這樣的字眼，也是僅僅記得是在那個書裏麵出現過而已。最近偶然拿起C語言的書，再次看到了“漢諾塔”遞歸算法的例子，轉好幾圈，終於搞明白了。現在花點時間重新這裏下思路，一則方便自己以後回憶，二則希望能給和我一樣菜的新手們提供參考，三則希望有高人出現對文中不足的地方加以斧正！

關於“漢諾塔”這個古老的益智遊戲如果不清楚的，到百度百科一下！

為了方便理解，這裏首先創造三個概念：源，踏板，目標。

如果任務是：將A上的圓盤移動至C，我們稱A為源，B為踏板，C為目標。

思路：1 要是源上隻有一個圓盤，隻直接將圓盤移動至目標。（無需借助踏板過渡）

2 要是源上有n（n>1）個圓盤，則分為下麵三個步驟完成。（借助踏板）

A先將前n-1個移動到踏板上（由上至下的順序）先移動到踏板上。（任務細分，重複1，2兩個步驟）

B 再將最後(第n個)一個移動至目標。

C 最後在將踏板上的全部移動至目標。（任務細分，重複1，2兩個步驟）

就上圖一我們按照上麵的思路遞歸一下整個過程：

第一層：進棧

任務：A （源）移動3 C（目標），n=3>1，所以借助B(踏板)，先將前兩個先

移動至B，再將最後一個移動至C，最後將踏板上的移動至C。

第二層：進棧

任務：A （源）移動2 B（目標），n=2>1，所以借助C(踏板)，先將前一個先

移動C,再將當前任務的最後一個移動至B，最後將踏板C上的移動至B。

第三層：進棧

任務：A （源）移動1 C（目標），n=1=1，直接將A上最上麵一個移動至C；

出棧。

回溯到第二層：

將當前任務的最後一個移動至B。




踏板C上的移動至目標B 出棧。回溯到第一層: 現在已經完成了將A上的上麵兩個移動至踏板B上，現在還剩下兩個步驟：將A上的一個移動到C上，將踏板B上的兩個移動到C上。 1將A上的移動到C上。 2 將B的兩個移動到C 上。分兩步進行：第二層：進棧借助A為踏板，先將B得上一個移動到A上。將B上的最底下一個移動至目標C 踏板A上的移動至目標C 出棧出棧自此，整個任務完成！ C/C++代碼： #include "stdio.h" int main() { void hanoi(int n,char origin,char bridge,char destination); // 對hanoi函數的聲明 intm; printf("input the number of diskes:"); scanf("%d",&m); printf("The step to move %d diskes:\n",m); hanoi(m,'A','B','C'); return 0; } void hanoi(int n,char origin,charbridge,char destination) // 定義hanoi函數 // 將n個盤從origin座借助bridge座,移到 destination座 { void move(char x,char y); //對move函數的聲明 if(n==1) move(origin,destination); else { hanoi(n-1,origin,destination,bridge); move(origin,destination); hanoi(n-1,bridge,origin,destination); } } voidmove(char x,char y) // 定義move函數 { printf("%c-->%c\n",x,y); }