漢諾塔

是根據一個傳說形成的數學問題：有三根杆子A，B，C。A杆上有 N 個 (N&gt;1) 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至 C 杆：提示：可將圓盤臨時置於 B 杆，也可將從 A 杆移出的圓盤重新移回 A 杆，但都必須遵循上述兩條規則。問：如何移？最少要移動多少次？傳說.最早發明這個問題的人是法國數學家愛德華·盧卡斯。傳說越南河內某間寺院有三根銀棒，上串 64 個金盤。寺院裡的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題。但不知道是盧卡斯自創的這個傳說，還是他受他人啟發。若傳說屬實，僧侶們需要 formula_1步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要 5849 億年才能完成。整個宇宙現在也不過 137 億年。這個傳說有若干變體：寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜，其中一說是位於越南的河內，所以被命名為「河內-{}-塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。解答.如取 N=64，最少需移動 264−1 次。即如果一秒鐘能移動一塊圓盤，仍需 5849 億年。目前按照宇宙大爆炸理論的推測，宇宙的年齡僅為 137 億年。在真實玩具中，一般 N=8；最少需移動 255 次。如果 N=10，最少需移動 1023 次。如果N=15，最少需移動32767次；這就是說，如果一個人從 3 歲到 99 歲，每天移動一塊圓盤，他最多僅能移動 15 塊。如果 N=20，最少需移動 1048575 次，即超過了一百萬次。演算法求解.解法的基本思想是遞迴。假設有 A、B、C 三個塔，A 塔有 formula_2 塊盤，目標是把這些盤全部移到 C 塔。那麼先把 A 塔頂部的 formula_3 塊盤移動到 B 塔，再把 A 塔剩下的大盤移到 C，最後把 B 塔的 formula_3 塊盤移到 C。如此遞迴地使用下去， 就可以求解。遞迴解.在 Java語言中：public class HW {public static java.util.Scanner sc = new java.util.Scanner(System.in);public static void Towers(int n,char a,char b,char c){if(n==1){System.out.println("移動"+n+"從"+a+"到"+c);else{Towers(n-1,a,c,b);System.out.println("移動"+n+"從"+a+"到"+c);Towers(n-1,b,a,c);public static void main(String[] args) {int n = sc.nextInt();Towers(n,'A','B','C');以 C++ 語言實現：using namespace std;void Towers(int n,char a,char b,char c){if(n==1){cout«"Move disk "«n«" from"«a«" to "«c«endl;else{Towers(n-1,a,c,b);cout«"Move disk "«n«" from"«a«" to "«c«endl;Towers(n-1,b,a,c);int main(int argc, char *argv[]) {int n;cin»n;Towers(n,'A','B','C');cout« endl;以 Python 語言實現：def hanoi(n, a, b, c):if n == 1:print(a, '--&gt;', c)else:hanoi(n - 1, a, c, b)hanoi(1 , a, b, c)hanoi(n - 1, b, a, c)if __name__ == '__main__':hanoi(5, 'A', 'B', 'C')以 Erlang 語言求解：-module(hanoi).-export([hanoi/1]).hanoi(N) when N&gt;0 -&gt;do_hanoi({N, 1, 3}).do_hanoi({0, _, _}) -&gt;done;do_hanoi({1, From, To}) -&gt;io:format("From ~p, To ~p~n", [From, To]);do_hanoi({N, From, To}) -&gt;do_hanoi({N-1, From, by(From, To)}),do_hanoi({1, From, To}),do_hanoi({N-1, by(From, To), To}).by(From, To) -&gt;[Result|_] = [1, 2, 3] -- [From, To],Result.以 Haskell 語言實現：hanoi :: Integer -&gt; String -&gt; String -&gt; String -&gt; [(String, String)]hanoi 0 _ _ _ = []hanoi 1 from _ to = [(from, to)]hanoi x from buffer to =hanoi (x-1) from to buffer ++ hanoi 1 from buffer to ++ hanoi (x-1) buffer from to任意初始結構的解法.為了從任意初始結構中找尋最佳解如下：以 Scheme 語言表示：; Let conf be a list of the positions of the disks in order of increasing size.; Let the pegs be identified by the numbers 0, 1 and 2.(define (hanoi conf t)(let ((c (list-&gt;vector conf)))(define (move h f t)(vector-set! c h t)(printf "move disk ~s from peg ~s to peg ~s~n" h f t))(define (third-peg f t) (- 3 f t))(define (hanoi h t)(if (&gt; h 0)(let ((h (sub1 h)))(let ((f (vector-ref c h)))(if (not (= f t))(let ((r (third-peg f t)))(hanoi h r)(move h f t)))(hanoi h t)))))(hanoi (vector-length c) t)))在 Java語言中：public class Hanoi {public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println(hanoiFunc(7));public static int hanoiFunc(int i) {int sum = 0;if (i == 1) {sum += i;else {sum = 2 * hanoiFunc(i - 1) + 1;return sum;在 C語言中：int conf[HEIGHT]; /* Element conf[d] gives the current position of disk d. */void move(int d, int t) {/* move disk d to peg t */conf[d] = t;void hanoi(int h, int t) {if (h &gt; 0) {int f = conf[h-1];if (f != t) {int r = 3 - f - t ;hanoi(h-1, r);move(h-1, t);hanoi(h-1, t);影象解釋.可以用無向圖來表示漢諾塔， 在表示的時候會更加地直觀和清晰， 雖然說理解上有一點難度。現在規定， 每一個節點表示盤子的位置一種可能性， 每一條邊表示一種移動的方法。"注： 這裡不考慮在兩個柱子之間的， 沒有意義的， 來回移動的情況。"對於只有一個盤子的漢諾塔，可以表示為：對於有兩個盤子的漢諾塔， 可以表示為：相互連線的三個三角形， 組成了一個較大三角形的三個角。每一個節點的第二個字母表示更大的盤子， 且最初時沒有被移動。對於每一個頂端的小三角形， 表示兩個盤子的一種移動的方法：外圍的三角形的每一個節點， 表示在一個柱子上盤子的所有分佈可能。對於 h+1 個盤子， 就可以"複製" h 個盤子時候的三角形圖， 然後拼成一個新的大三角形圖， 稍微改動一下，這個大的三角形圖就可以用來表示 h+1 個盤子時的情況了。所以當有三個盤子時， 圖形為：最外面的三角形的邊， 表示了盤子從一個柱子移動到另一個柱子最快的方式。 最大的三角形可以沿著中線分成三個次小的三角形， 就是上面由二級的漢諾塔組成三級的漢諾塔的逆向操作， 次小三角形相互之間的連線， 表示著最大的盤子的移動方式。同理， 在這次三角形的也可以沿其中線分割成為三個次次三角形， 一樣的， 次次小三角形相互之間的連線， 表示著次大的盤子的移動方式。 繼續下去， 也就可以表示出一個漢諾塔的移動方式。通常，對於具有 n 個盤子的圖， 有 formula_5個節點； 每個節點都有三條邊連線著其他節點， 但是在頂點的的節點只卻只有有兩條邊連線著其他節點。 所以說總是下都可以將最小的盤子移動到另外兩個柱子中的一個， 對於多數情況， 是可以在兩個柱子間移動一個盤子， 除了所有的盤子都在一個柱子上。 邊角的節點表示著所有的盤子都在一個柱子的情況， 即可以在 a， b 或 c 柱上堆滿盤子， 顯然只要三種。 對於 formula_6個盤子的圖， 可以透過表示 formula_7給盤子的圖 "複製" 三份， 組合在一起的。 因此也就很方便地表示了每一層的漢諾塔移動方式， 每一個次小的三角形表示次小的盤子的所有可能的移動方式和放置狀態， 次小的三角形之間的連線表示了大盤子的三種可能的移動方式。 所以圖形有 formula_8 個節點， 基本都有三個與之相連線的邊， 而頂點只有兩個。在盤子數比較多的時候， 漢諾塔的影象就會開始和分形圖比較相似了。如果使用最麻煩的移動方式， 即不走重複的路(移動方式)， 需要 formula_9 次移動， 每秒移動一次， 需要的時間超過 formula_10年。在不考慮重複使用路徑的情況下， 去除掉沒有經過的邊， 就可以表示出當有三個盤子時的最長路徑 。就是沒有去做無意義 (多餘的) 的， 將一個盤子在兩個柱子間瘋狂來回移動的情況下， 去除沒有使用的移動方法， 就可以得到當有三個盤子時的最麻煩的移動方式順便一提，這個最長的非重複路徑， 可以透過清除掉從 a 到 b 的路徑得到。也可以得出三個盤子的漢諾塔圖的 哈密頓迴路：該圖較為清楚地表達了：這裡的 formula_15， 詳細在 上。多塔漢諾塔問題.Frame-Stewart 演演算法本質上也是遞迴的，可簡單敘述如下：對於任何移動方法，必定會先將 formula_18個圓盤移動到一箇中間柱子上，再將第 formula_7到第 formula_20個圓盤透過剩下的 formula_21個柱子移到目標柱子上，最後將 formula_22個在中間柱子上的圓盤移動到目標柱子上。這樣所需的操作步數為 formula_23。進行最最佳化，易得： formula_24 。流行文化.2011年電影《猿人爭霸戰：猩兇革命》曾出現河內塔以測試猩猩的智商。其後續電影《猩球崛起2》中也有類似的場景。