1、數據結構課程常見問題 -單元18 漢諾塔問題1漢諾塔問題？解析：漢諾塔遞歸棧 問題抽象 3個塔，n個碟子 初始：所有碟子放在1號塔，大的在底下，小的在上面 任務：把碟子移動到2號塔，順序不變， 可用3號塔輔助 限制 每次只能移動一個碟子 總是大碟子在下，小的在上 遞歸解法 移動碟子的方法：move(n, t1, t2, t3) 將n個碟子從t1移到t2，t3輔助 可分解為3個步驟 將n-1個碟子從t1移到t3：move(n-1, t1, t3, t2) 將最大的碟子從t1移到t2 將n-1個碟子從t3移到t2：move(n-1, t3, t2, t1) 漢諾塔遞歸程序 void TowersO

2、fHanoi(int n, int x, int y, int z) / Move the top n disks from tower x to tower y. / Use tower z for intermediate storage. if (n 0) TowersOfHanoi(n-1, x, z, y); cout Move top disk from tower x to top of tower y endl; TowersOfHanoi(n-1, z, y, x); moves(n)=2n-1最少次數，(2n) 一般遞歸程序轉換為循環 遞歸函數主體的轉換 轉換為循環，whi

3、le(1)即可 遞歸調用的轉換 將當前參數、局部變量（活動記錄）壓棧 參照調用方式改變參數，繼續循環 函數執行結束遞歸返回的處理 若棧空，整個遞歸過程結束，跳出循環 否則，將調用者的活動記錄彈出棧，恢復其環境，繼續循環 遞歸函數不同入口的區分返回地址的處理 上例：ENTRANCE、FIRST、SECOND 活動記錄的一部分，與參數、局部變量一同壓棧、出棧 在循環主體中，根據當前活動記錄的入口值，執行不同代碼 漢諾塔的遞歸棧實現 #include #include #include #include #include using namespace :std; enum ENTRANCE = 0

4、, FIRST, SECOND ; struct ac int n, x, y, z; int r; ; 漢諾塔的遞歸棧實現 void hanoi(int n, int x, int y, int z) stack stack; struct ac ac = n, x, y, z, ENTRANCE ; while (1) if (ac.n = 0) if (stack.empty() break; ac = stack.top(); stack.pop(); if (ac.r = ENTRANCE) ac.r = FIRST; else ac.r = SECOND; 漢諾塔遞歸棧實現 if

5、(ac.r = ENTRANCE) stack.push(ac); ac.n-; swap(ac.y, ac.z); else if (ac.r = FIRST) cout Move top disk from tower ac.x to top of tower ac.y endl; stack.push(ac); ac.r = ENTRANCE; ac.n-; swap(ac.x, ac.z); 漢諾塔遞歸棧實現 else if (ac.r = SECOND) if (stack.empty() break; ac = stack.top(); stack.pop(); if (ac.r = ENTRANCE) ac.r = FIRST; else ac.r = SECOND; 漢諾塔遞歸棧實現