平行河內塔之研究

Abstract

河內塔（Tower of Hanoi）問題是一個很有名的數學遊戲，大多數教科書都拿它當作遞迴（Recursion）概念的例子。本論文探討它的一種變形問題，這種變形允許同一時間內在最上面的碟子可以自由的移動，因此，除了原來的搬移法外，還可以歸納出三種新的搬移碟子的方式：交換(Exchanging)、移位(Shift)、及旋轉(Rotation)，這三種方式的不同組合如何減少搬動的次數是我們要首先研究的主題。本論文討論其中的四種組合: (1)交換河內塔, (2)移位河內塔, (3)旋轉河內塔, 以及(4)移位旋轉河內塔，運用divide-and-conquer的方法，為上述各個問題設計出演算法並證明它們是最佳的搬移方式。 此外，針對交換河內塔這個問題，我們還設計了兩種非遞迴的演算法，一種是運用模擬recursive call的設計方式；另一種是用對應到其他問題的設計方式。

Tower of Hanoi is a famous mathematical recreation game. It appears in many programming textbooks as an example for the concept of recursion. One of its numerous variants is studied in this thesis. We allow every top disk can be simultaneously moved. Therefore, we get three new moving abilities: exchange, shift, and rotation. How different combinations of these moves affect the total number of steps is our concern in this thesis. By using the divide-and-conquer technique, we design optimal algorithms for four of these problems: (1)Tower of Hanoi with exchange, (2)Tower of Hanoi with shift, (3)Tower of Hanoi with rotation, and (4)Tower of Hanoi with shift and rotation. Besides, two iterative algorithms for Tower of Hanoi with exchange are proposed. One is devised by simulating how recursive call works; the other is designed by reducing Tower of Hanoi with exchange to another problem.