從前從前,在越南有個地方叫做河內,河內裡有座山,山上有座塔,塔中有三根聳天而立的大銀棒,銀棒上串有64 個金盤。塔中的僧侶們會依照一個古老的預言,並依規則來移動這些金盤;而預言則說當這些金盤全部都移動完畢之後,世界就會毀滅。 這個傳說就叫做梵天寺之塔問題 ( Tower of Brahma puzzle ),也就是我們熟知的河內塔 ( Tower of Hanoi ) 問題,在這個問題中 64個金盤的它每個的大小都是不一樣的,並在一開始的時候會依序從底部最大排到頂部最小,而搬移的規則有三個:
既然在全部盤子都搬完之後世界就會毀滅了,那數學家們自然會想知道我們到底還剩下多少時間! 最後數學家用公式證明出,解決河內塔問題的最佳步驟為 2^N - 1 次,其中的N為金盤的數量,若我們要解一個三層的河內塔則需動 2^3 - 1 = 7次;六層即 2^6 - 1 = 63次;那傳說中的64層就會需要 2^64 - 1次,即便僧侶們各個單身三十年,手速驚為天人的一秒移一盤,也會需要超過5849億年才有辦法完成。 By the way,這個傳說是瞎掰的啦~ 也不知道提出這個問題的數學家- Anatole Lucas 怎麼這麼會掰xD 後來河內塔也常被做成給小朋友玩的益智玩具,附一段影片給你們看,應該能更好理解這東西。 Ok,那接下來身為資工人的你就要寫程式來解這個問題啦~ 它可以說是一個非常經典的遞迴問題,身為一個訓練有素的資工人很自然會想用遞迴的方式來解:
Solving the Tower of Hanoi Problem using C Language
實際運行結果:
基本上就是這樣,不會太困難,只不過對於剛學程式的小大一來說遞迴這東西真的常常不小心就有點卡住,可能你也知道它好像也可寫成遞迴的形式來解,but you don't know how T^T 這也沒關係啦~ 想當初 Jason 第一次寫河內塔的時候也不是用遞迴的形式解的,上機考有時間壓力R 一時之間沒想到要怎麼用遞迴解,就用 while 還是 for 迴圈幹了一個出來 xD 如果還在學程式的碰牆期的話,也沒關係,千萬不要低頭,不然會有雙下巴 哈哈哈哈哈 那這篇就寫到這邊吧~ 唉.. 最近爆幹忙,下一篇可能一個月後了吧 Orz
0 評論
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|