[ 資料結構 小學堂 ] 堆疊 : 堆疊應用 (河內塔問題)

前言 : 
在西元 1883 年, 法國數學家 Lucas 所提出流傳在印度的河內塔 (Tower of Hanoil) 遊戲, 是典型使用遞迴與堆疊觀念來解決的範例. 河內塔問題描述如下 : 

有三根木椿, 第一根上有 n 個盤子, 最底層的盤子最大, 依序往上層的盤子越來越小. 河內塔問題就是將所有盤子從第一根木椿, 並以第二根木椿當作橋梁, 全部移到第三根木椿. 如下圖所示 :

不過在移動時, 尚須遵守以下遊戲規則 :
1. 每次只能從最上面移動一個盤子.
2. 任何盤子可以從任何木椿移到其他木椿.
3. 直徑較小的盤子永遠必須放在直徑較大的盤子上面.

解題說明 : 
為了方便推導公式, 我們將從移動一個盤子開始, 再來移動兩個. 最後考慮移動 n 個盤子. 
* 移動一個盤子 : 
 

* 移動兩個盤子 : 
 

* 移動 n 個盤子 : 
 

公式推導 : 
由上面解題說明, 在解移動 n 個盤子時, 可以看成下面的組合 : 
 

所以公式推導如下 : 
 

範例程式 : 
* ch04.h 代碼 : 

view plaincopy to clipboardprint?

1. /* 
2. * 利用河內塔函數求出不同盤子數的盤子移動步驟. 
3. */  
4. void ch04_06(bool b);  

* ch04.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "ch04.h"  
2. #include   
3. using namespace std;  
4.   
5. void _hanoi(int n, int p1, int p2, int p3) {  
6.     if(n==1) {  
7.         cout << "移動盤子從 " << p1 << " 到 " << p3 << endl;  
8.     } else {  
9.         _hanoi(n-1, p1, p3, p2);  
10.         cout << "移動盤子從 " << p1 << " 到 " << p3 << endl;  
11.         _hanoi(n-1, p2, p1, p3);  
12.     }  
13. }  
14.   
15. void ch04_06(bool b) {  
16.     if(b) {  
17.         int j;  
18.         cout << "請輸入盤子數量: " ;  
19.         cin >> j;  
20.         _hanoi(j, 1, 2, 3);  
21.     }  
22. }  

執行函式 ch04_06 結果 : 

請輸入盤子數量: 3
移動盤子從 1 到 3
移動盤子從 1 到 2
移動盤子從 3 到 2
移動盤子從 1 到 3
移動盤子從 2 到 1
移動盤子從 2 到 3
移動盤子從 1 到 3 <根據公式計算, 移動 3個盤子為 2^3-1=7, 故需要移動7次>

補充說明 : 
* [ 資料結構 小學堂 ] 堆疊 : 堆疊應用 (遞迴) 
* [C++ 演算法] 河內塔 (Towers of Hanoi)