我的斐波那契實現有什麼問題？

Question

我試圖將我的遞歸斐波那契函數轉換爲迭代解決方案。我試過如下：

fib_itt :: Int -> Int 
fib_itt x = fib_itt' x 0 
where 
    fib_itt' 0 y = 0 
    fib_itt' 1 y = y + 1 
    fib_itt' x y = fib_itt' (x-1) (y + ((x - 1) + (x - 2))) 

我想要的結果保存到變量y並返回它當xy比賽與1y，但預期它不工作。對於fib_itt 0和fib_itt 1，它工作正常，但對於n > 1，這是行不通的。例如，fib_rek 2返回1和fib_rek 3回報2。

Answer 1

你的算法是錯誤的：在y + (x-1) + (x-2)只添加了連續的數字 - 而不是在fib.series的數字。

好像你嘗試過某種對的方法（我認爲） - 是的這是一個好主意，可以這樣做：

fib :: Int -> Int 
fib k = snd $ fibIt k (0, 1) 

fibIt :: Int -> (Int, Int) -> (Int, Int) 
fibIt 0 x = x 
fibIt k (n,n') = fibIt (k-1) (n',n+n') 

，你可以看到：本通兩個需要的部分（最後一個和倒數第二個數字）作爲一對數字，並跟蹤k的迭代。

然後它只是給回這個元組的fib第二部分（如果你使用的第一個，你會得到0,1,1,2,3,...當然你可以調整初始元組，以及如果你喜歡（fib k = fst $ fibIt k (1, 1)）。

---

這個想法直接利茲到fib.sequence的這個漂亮的定義，如果你因子迭代出來iterate的方式;）

fibs :: [Int] 
fibs = map fst $ iterate next (1,1) 
     where 
     next (n,n') = (n',n+n') 

fib :: Int -> Int 
fib k = fibs !! k