河內塔 (Tower of Hanoi) 其實也是個古老的題目,最常被用來解釋什麼叫做堆疊。
河內塔最早發明這個問題的人是法國數學家愛德華·盧卡斯。
傳說越南河內某間寺院有三根銀棒,上串 64 個金盤。寺院裡的僧侶依照一個古老的預言,以上述規則移動這些盤子;預言說當這些盤子移動完畢,世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創的這個傳說,還是他受他人啟發。
若傳說屬實,僧侶們需要 2^(64) - 1 步才能完成這個任務;若他們每秒可完成一個盤子的移動,就需要 5845 億年才能完成。整個宇宙現在也不過 137 億年。
這個傳說有若干變體:寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜,其中一說是位於越南的河內,所以被命名為「河內塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。
--引自〈維基百科〉
我們先用三個盤子來演示一下。
移動條件:將全部盤子從柱子1移動到柱子3,一次移動一個盤子,大的盤子不能在小的下面。(這邊用英文符號代替盤子,A最大,Z最小)
C | ||
B | ||
A | ||
Column1 | Column2 | Column3 |
B | ||
A | C | |
Column1 | Column2 | Column3 |
A | B | C |
Column1 | Column2 | Column3 |
C | ||
A | B | |
Column1 | Column2 | Column3 |
C | ||
B | A | |
Column1 | Column2 | Column3 |
C | B | A |
Column1 | Column2 | Column3 |
B | ||
C | A | |
Column1 | Column2 | Column3 |
C | ||
B | ||
A | ||
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)
最近真的太忙,文章都打得很不齊全,總覺得很對不起自己的良心。現在只求能完賽,然後再慢慢的把文章有系統的建立起來。