2014年9月10日 星期三

河內塔(漢諾塔)算法解析 The tower of hanoi algorithm analysis

起源(Origin):
       最早發明這個問題的人是法國數學家愛德華·盧卡斯
傳說印度某間寺院有三根柱子,上串64個金盤。寺院裡的僧侶依照一個古老的預言,以上述規則移動這些盤子;預言說當這些盤子移動完畢,世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創的這個傳說,還是他受他人啟發。
若傳說屬實,僧侶們需要264 − 1步才能完成這個任務;若他們每秒可完成一個盤子的移動,就需要5849億年才能完成。整個宇宙現在也不過137億年。
這個傳說有若干變體:寺院換成修道院僧侶換成修士等等。寺院的地點眾說紛紜,其中一說是位於越南河內,所以被命名為「河內塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。
佛教中確實有「浮屠」()這種建築;有些浮屠亦遵守上述規則而建。「河內塔」一名可能是由中南半島在殖民時期傳入歐洲的。

來源網址: http://zh.wikipedia.org/wiki/%E6%B1%89%E8%AF%BA%E5%A1%94

這個遊戲有 三個柱子,暫以 A  B  C 代替

目的,要把 A柱上的多個盤子由A 移動到 C 柱
當一個盤子時, A -> C
當二個盤子時, A -> B, A -> C, B -> C

解法重點,只要超過二個盤子,都可以想像只有二個盤子
也就是 n 跟 n-1 個盤子(最低部的盤子跟除了 最底部以外的盤子)

最底部以外的盤子  n - 1 
最低部的盤子為      n

所以只有三個步驟不斷重複

A -> B
A -> C
B -> C

第一步 將 n-1個盤子 A移動到B
第二步 將 最底部盤子n  A移動到B
第三步 將 n-1個盤子 B移動到C

有圖說明觀念才會清楚些





# Python 版本
def hanoi(n, A="A", B="B", C="C"):
    if n > 0:
        hanoi(n-1, A, C, B)
        print "Move a Disc from %s to %s" % (A, C)
        hanoi(n-1, B, A, C)

if __name__ == '__main__':
    hanoi(input('How many disks you wanna play? '))


// F# 版本
let rec hanoi(n: int, A: string, B: string, C: string) =
    if n > 0 then
        hanoi(n-1, A, C, B)
        printfn "Move a Disc from %s to %s" A C
        hanoi(n-1, B, A, C)

hanoi(3, "A", "B", "C")

沒有留言:

張貼留言