有關(guān)如何有效地解決Haskell中以下函數(shù)的所有問題的大量建議 (n > 108)f(n) = max(n, f(n/2) + f(n/3) + f(n/4))我已經(jīng)在Haskell中看到了用于記憶斐波那契數(shù)的記憶示例，其中涉及（懶惰地）計算直到所需n的所有斐波那契數(shù)。但是在這種情況下，對于給定的n，我們只需要計算很少的中間結(jié)果。謝謝
3 回答
楊__羊羊
TA貢獻1943條經(jīng)驗 獲得超7個贊
并非最有效的方法，但要記?。?/p>
f = 0 : [ g n | n <- [1..] ]
where g n = max n $ f!!(n `div` 2) + f!!(n `div` 3) + f!!(n `div` 4)
請求時f !! 144，將檢查是否f !! 143存在，但不計算其確切值。它仍然設(shè)置為某些未知的計算結(jié)果。唯一需要計算的精確值。
因此，最初，就計算多少而言，該程序一無所知。
f = ....
當我們發(fā)出請求時f !! 12，它開始進行一些模式匹配：
f = 0 : g 1 : g 2 : g 3 : g 4 : g 5 : g 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...
現(xiàn)在開始計算
f !! 12 = g 12 = max 12 $ f!!6 + f!!4 + f!!3
遞歸地對f提出了另一個要求，因此我們計算
f !! 6 = g 6 = max 6 $ f !! 3 + f !! 2 + f !! 1
f !! 3 = g 3 = max 3 $ f !! 1 + f !! 1 + f !! 0
f !! 1 = g 1 = max 1 $ f !! 0 + f !! 0 + f !! 0
f !! 0 = 0
現(xiàn)在我們可以滴一些
f !! 1 = g 1 = max 1 $ 0 + 0 + 0 = 1
這意味著程序現(xiàn)在知道：
f = 0 : 1 : g 2 : g 3 : g 4 : g 5 : g 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...
繼續(xù)滴滴答答：
f !! 3 = g 3 = max 3 $ 1 + 1 + 0 = 3
這意味著程序現(xiàn)在知道：
f = 0 : 1 : g 2 : 3 : g 4 : g 5 : g 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...
現(xiàn)在我們繼續(xù)計算f!!6：
f !! 6 = g 6 = max 6 $ 3 + f !! 2 + 1
f !! 2 = g 2 = max 2 $ f !! 1 + f !! 0 + f !! 0 = max 2 $ 1 + 0 + 0 = 2
f !! 6 = g 6 = max 6 $ 3 + 2 + 1 = 6
這意味著程序現(xiàn)在知道：
f = 0 : 1 : 2 : 3 : g 4 : g 5 : 6 : g 7 : g 8 : g 9 : g 10 : g 11 : g 12 : ...
現(xiàn)在我們繼續(xù)計算f!!12：
f !! 12 = g 12 = max 12 $ 6 + f!!4 + 3
f !! 4 = g 4 = max 4 $ f !! 2 + f !! 1 + f !! 1 = max 4 $ 2 + 1 + 1 = 4
f !! 12 = g 12 = max 12 $ 6 + 4 + 3 = 13
這意味著程序現(xiàn)在知道：
f = 0 : 1 : 2 : 3 : 4 : g 5 : 6 : g 7 : g 8 : g 9 : g 10 : g 11 : 13 : ...
因此，計算是相當懶惰的。該程序知道for的某些值f !! 8等于g 8，但是不知道是什么g 8。
- 3 回答
- 0 關(guān)注
- 531 瀏覽
添加回答
舉報
0/150
提交
取消