Download presentation
Presentation is loading. Please wait.
1
河內之塔(Towers of Hanoi)問題(1/11)
河內之塔(Towers of Hanoi)問題是一個古老而有趣的問題，由法國數學家Eduard Lucas在十九世紀所創，河內之塔的名稱來自以下的傳說： 在越南河內市的市郊有一座寺廟，這廟中有三支金子做成的柱子，其中一根柱子上疊著64個大小不同圓盤，如下圖所示：
2
河內之塔(Towers of Hanoi)問題(2/11)
這些圓盤可以在三根柱子中移動，但是要遵守以下之規則： 每次只能移動一個圓盤 大圓盤不可以疊在小圓盤上面 這廟裡的出家人都很認真的在研究著怎麼移動圓盤，因為傳說若能將柱子中的所有圓盤都移動到另外一支柱子上時，則世界大同之日(原Eduard Lucas之說法為世界末日)則會來臨，當然，廟裡的出家人都希望世界大同之日能夠趕快來臨。不過，經過數學家的推算，即使這些出家人能夠以一秒鐘一個圓盤的速度來移動這些圓盤，仍然需要264-1秒，約為5千億年才能搬完這些圓盤，而世界大同之日才會來臨。 以下，我們先來看一個簡化的河內之塔的例子。在此例子中，我們只考慮3個圓盤，以下我們顯示如何在7個步驟內將圓盤由某支柱子搬動到另外一支柱子。
3
河內之塔(Towers of Hanoi)問題(3/11)
4
河內之塔(Towers of Hanoi)問題(4/11)
5
河內之塔(Towers of Hanoi)問題(5/11)
河內之塔的問題看似複雜，但是我們若能夠使用遞迴的方式來設計演算法，則此問題會變得較容易解決。其基本想法為將問題簡化為相同但問題大小較小之問題，直到問題能夠直接解決為止。在本例中，所謂問題大小就是「圓盤總數」，而當圓盤總數為1，則我們可以直接將這個圓盤由其所在的柱子直接移動到另外一支柱子來解決問題。以下是以遞迴方式所設計的「河內之塔」演算法：
6
Towers of Hanoi(河內之塔) 移動A柱的n-1個disk到B柱 移動A柱剩下的最大disk到C柱
移動B柱的n-1個disk到C柱
7
河內之塔(Towers of Hanoi)問題(6/11)
以下是以遞迴的「河內之塔」演算法撰寫成的Java範例程式：
8
河內之塔(Towers of Hanoi)問題(7/11)
範例程式(檔名：河內之塔.java) //檔名:河內之塔測試.java //說明:以遞迴方式解決河內之塔(Towers of Hanoi)問題 import javax.swing.*; public class 河內之塔測試 extends JApplet { String 顯示字串; public void init( ) { String 輸入字串; 輸入字串=JOptionPane.showInputDialog("請輸入河內之塔(Towers of Hanoi)圓盤個數"); int 個數=Integer.parseInt(輸入字串); 顯示字串=(個數+"個圓盤河內之塔(Towers of Hanoi)圓盤之移動順序:");
9
河內之塔(Towers of Hanoi)問題(8/11)
河內之塔(個數,'A','B','C'); //A,B,C分別為「來源柱」、「中間柱」及「目的柱」的代號 JOptionPane.showMessageDialog(null,顯示字串); } //方法:init() 定義區塊結束 private void 河內之塔(int n, char 來源柱, char 中間柱, char 目的柱) { //n代表圓盤個數 if (n==1) 顯示字串+= ("\n圓盤1自柱"+來源柱+"到柱"+目的柱); else { 河內之塔(n-1,來源柱,目的柱,中間柱);//將n-1個圓盤藉由目的柱由來源柱移動至中間柱 顯示字串+= ("\n圓盤"+n+"自柱"+來源柱+"到柱"+目的柱); //將最大的圓盤直接由來源 柱移動至目的柱 河內之塔(n-1,中間柱,來源柱,目的柱);//將n-1個圓盤藉由來源注由中間柱移動至目的柱 } } //方法: 河內之塔() 定義區塊結束 } //類別:河內之塔測試 定義區塊結束
10
河內之塔(Towers of Hanoi)問題(9/11)
網頁檔案(檔名：河內之塔測試.html) <html> <h1>「河內之塔測試」執行中<h1> <applet code="河內之塔測試.class" width=350 height=100> </applet> </html> 執行結果(以瀏覽器載入檔案：河內之塔測試.html)
11
河內之塔(Towers of Hanoi)問題(10/11)
我們一開始介紹河內之塔問題時提到，即使以一秒鐘一個圓盤的速度來移動64個圓盤，仍然需要264-1秒(約5千億年)才能搬完這些圓盤，以下我們來看看這個時間是如何推導出來的。 我們來分析圓盤需要移動的次數: 假設Hn為移動n個圓盤所需的移動次數，我們可得
12
河內之塔(Towers of Hanoi)問題(11/11)
13
Towers of Hanoi(河內之塔) Disk 1 from A to C Disk 2 from A to B
Disk 1 from C to B Disk 3 from A to C Disk 1 from B to A Disk 2 from B to C
Similar presentations
