电脑与问题解决-电脑解题程序-解题方法设计.ppt

電腦與問題解決-電腦解題程序-解題方法設計 第*頁 電腦與問題解決-電腦解題程序-解題方法設計 以河內塔為例介紹遞迴關係 王鼎中老師 河內塔的起源 1883年，一位法國的數學家Edouard Lucas教授在歐洲的一份雜誌上介紹了一個相當吸引人的難題～迷人的智力遊戲。 這個遊戲名為河內塔（Tower of Hanoi），它源自古印度神廟中的一段故事（也有一說是Lucas教授為增加此遊戲之神秘色彩而捏造的）。   河內塔的由來 根據一個古老的故事，在遠東的某處有一個寺院，裏面有一堆六十四個由大到小純金打造的盤子。有一回，這些盤子被疊在一起，最大的盤子放在最底層。每一個盤子被穿了一個孔，放在寶石的針上。它們可以根據規則由一個位置搬移到另外一個位置。 當這個河內塔從某個位置全部被搬到另外一個位置時，世界末日就會降臨！  河內塔遊戲的解法 1個盤子 顯然只須移動一次即可。 2個盤子 必須要先搬移上面的盤子到第2根柱子， ?再將下面的盤子搬到第3根柱子， ?最後將上面的盤子搬回第3根柱子，需要搬移三次可以完成； 河內塔的遞迴解法 3個盤子： 要先假設一次搬兩個盤子，依照2個盤子的搬移步驟來拆解 1. 先搬移上面兩個盤子到第2根柱子； ?(兩層河內塔問題) ?次數：3 2. 再搬移最下面的盤子到第3根柱子； ?次數：1 3. 將上兩個盤子搬到第3根柱子 (兩層河內塔問題) ?次數：3 次數＝3 ＋1 ＋3 ＝7次 河內塔的遞迴解法 如此可以發現若要解決3層河內塔問題，則透過2層河內塔的解法即可達成，要解決2層河內塔問題，則透過1層河內塔的解法即可達成，1層河內塔則直接搬動即可。 4層河內塔問題如何解決? 要解決四層河內塔的問題一樣要先解決三層河內塔的問題 如此我們可以歸納出一個公式： f(n) = f(n-1) + 1 + f(n-1) 以公式計算河內塔問題 符合遞迴的兩個條件： 反覆執行：f(n) = f(n-1) + 1 + f(n-1) ?不斷呼叫自己本身 停止執行的條件：f(n) =1 以程式解決河內塔問題 在程式實作上，若我們可以寫一個函數T(n)來計算n層河內塔的搬動次數 　 則依據遞迴關係式可將該函數定義為 T(n) 　IF n=1 　　　times = 1 　ELSE 　　　times = T(n-1) + 1 + T(n-1) 　Return times 上述的函數T(n) 乃是呼叫 T(n-1)來完成，此種在函數中呼叫函數本身的結構 當times = 1時，為終止條件 64個盤子的河內塔問題解法 根據運算可得T(64)=18,446,774,073,709,551,615。 假設一位熟練的僧侶每秒鐘搬動一次盤子，日以繼夜不眠不休的工作，也需要約584,942,417,355年，這是非常遙遠的事，科學家估計地球約已經存在2,000,000,000年，也沒有一種生物能活這麼久，所以我們大可放心的睡覺。 如何運用遞迴解決問題 首先必須根據問題找出遞迴關係式，接著為了避免無窮盡的遞迴下去，必須要設定令遞迴停下來的終止條件，因此，要運用遞迴解決問題，就必須先掌握遞迴解題的兩個要素： 找出遞迴關係式 設定終止條件 電腦與問題解決-電腦解題程序-解題方法設計 第*頁 電腦與問題解決-電腦解題程序-解題方法設計