Download presentation
Presentation is loading. Please wait.
1
河內之塔(Towers of Hanoi)問題
河內之塔(Towers of Hanoi)問題是一個古老而有趣的問題， 由法國數學家Eduard Lucas在十九世紀所創，河內之塔的 名稱來自以下的傳說： 在越南河內市的市郊有一座寺廟，這廟中有三支金子 做成的柱子，其中一根柱子上疊著64個大小不同圓盤， 如下圖所示：
2
河內之塔(Towers of Hanoi)問題
圓盤可以在三根柱子中移動，但是要遵 守以下規則： 每次只能移動一個圓盤 大圓盤不可以疊在小圓盤上面
3
傳說若能將柱子中的所有圓盤都移動到另外一支柱 子上時，則世界大同之日則會來臨。
經過推算，即使出家人能夠以一秒鐘一個圓盤的速 度來移動這些圓盤，仍然需要264-1秒，約為5千億 年才能搬完這些圓盤，而世界大同之日才會來臨。
4
簡化的河內之塔：只考慮3個圓盤
7
河內之塔的問題看似複雜，但是我們若能夠使用遞 迴的方式來設計演算法，則此問題會變得較容易解 決。其基本想法為將問題簡化為相同但問題大小較 小之問題，直到問題能夠直接解決為止。在本例中， 所謂問題大小就是「圓盤總數」，而當圓盤總數為 1，則我們可以直接將這個圓盤由其所在的柱子直 接移動到另外一支柱子來解決問題。以下是以遞迴 方式所設計的「河內之塔」演算法：
8
移動A柱的n-1個disk到B柱 移動A柱剩下的最大disk到C柱 移動B柱的n-1個disk到C柱
10
我們一開始介紹河內之塔問題時提到，即使以一秒鐘 一個圓盤的速度來移動64個圓盤，仍然需要264-1秒(約5 千億年)才能搬完這些圓盤，以下我們來看看這個時間 是如何推導出來的。
我們來分析圓盤需要移動的次數: 假設Hn為移動n個圓盤所需的移動次數，我們可得
11
假設Hn為移動n個圓盤所需的移動次數
12
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
