我的斐波那契实现有什么问题？

Question

我正在尝试将我的递归 Fibonacci 函数转换为迭代解决方案。我尝试了以下方法：

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)))

当 x y 与 1 y 匹配时，我想将结果保存到变量 y 和 return 中，但它没有按预期工作。对于 fib_itt 0 和 fib_itt 1，它可以正常工作，但是对于 n > 1，它不起作用。例如，fib_rek 2 returns 1 和 fib_rek 3 returns 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.[=18= 跟踪迭代]

然后它只在 fib 中返回这个元组的第二部分（如果你使用第一个你会得到 0,1,1,2,3,... 但当然你也可以根据需要调整初始元组(fib k = fst $ fibIt k (1, 1)).

顺便说一句，如果您将迭代分解为 iterate，这个想法直接导致 fib.sequence 的这个很好的定义；）

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

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

我的斐波那契实现有什么问题？

What's wrong with my Fibonacci implementation?

haskell

fibonacci