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

標籤

2010年9月24日 星期五

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

前言 : 
在西元 1883 年, 法國數學家 Lucas 所提出流傳在印度的河內塔 (Tower of Hanoil) 遊戲, 是典型使用遞迴與堆疊觀念來解決的範例. 河內塔問題描述如下 : 
有三根木椿, 第一根上有 n 個盤子, 最底層的盤子最大, 依序往上層的盤子越來越小. 河內塔問題就是將所有盤子從第一根木椿, 並以第二根木椿當作橋梁, 全部移到第三根木椿. 如下圖所示 :

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


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

* 移動兩個盤子 : 
 

* 移動 n 個盤子 : 
 

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

所以公式推導如下 : 
 

範例程式 : 
* ch04.h 代碼 : 
  1. /* 
  2. * 利用河內塔函數求出不同盤子數的盤子移動步驟. 
  3. */  
  4. void ch04_06(bool b);  
* ch04.cpp 代碼 : 
  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, 123);  
  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)

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!