iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 9
0

河內塔 (Tower of Hanoi) 其實也是個古老的題目,最常被用來解釋什麼叫做堆疊。

河內塔最早發明這個問題的人是法國數學家愛德華·盧卡斯。

傳說越南河內某間寺院有三根銀棒,上串 64 個金盤。寺院裡的僧侶依照一個古老的預言,以上述規則移動這些盤子;預言說當這些盤子移動完畢,世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創的這個傳說,還是他受他人啟發。

若傳說屬實,僧侶們需要 2^(64) - 1 步才能完成這個任務;若他們每秒可完成一個盤子的移動,就需要 5845 億年才能完成。整個宇宙現在也不過 137 億年。

這個傳說有若干變體:寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜,其中一說是位於越南的河內,所以被命名為「河內塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。
--引自〈維基百科

我們先用三個盤子來演示一下。
移動條件:將全部盤子從柱子1移動到柱子3,一次移動一個盤子,大的盤子不能在小的下面。(這邊用英文符號代替盤子,A最大,Z最小)

     
   
   
   
Column1 Column2 Column3
     
     
   
 
Column1 Column2 Column3
     
     
     
Column1 Column2 Column3
     
     
   
 
Column1 Column2 Column3
     
     
   
 
Column1 Column2 Column3
     
     
     
Column1 Column2 Column3
     
     
   
 
Column1 Column2 Column3
     
   
   
   
Column1 Column2 Column3

全部的程式碼:

def hanoi(n, A, B, C):
    if n == 1:
        return [(A, C)]
    else:
        return hanoi(n-1, A, C, B) + hanoi(1, A, B, C) + hanoi(n-1, B, A, C)


n = input("Please enter integer:")
for move in hanoi(int(n), 'A', 'B', 'C'):
    print("move %c to %c" % move)

拉蒙碎碎念

最近真的太忙,文章都打得很不齊全,總覺得很對不起自己的良心。現在只求能完賽,然後再慢慢的把文章有系統的建立起來。


上一篇
[資料結構] 佇列 (Queue)
下一篇
[資料結構] 樹 (Tree)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言