这个Fibonacci函数如何工作？ [关闭]

Question

谁能告诉我以下功能是如何工作的？

尤其是fibu'-thing和元组？谢谢！

fibu :: Integer -> Integer
fibu x = fst (fibu' x)
      where fibu' 0 = (0, 0)
            fibu' 1 = (1, 0)
            fibu' n = (a + l, l)
                      where (l, a) = fibu' (n-1)

Answer 1

我们先来分析吧

fibu' 0 = (0, 0)
fibu' 1 = (1, 0)
fibu' n = (a + l, l)
    where (l, a) = fibu' (n-1)

这里我们有一个函数，它将数字i作为输入，并返回一个带有两个数字的2元组。这两个数字是（Fi，Fi-1），其中Fi是第i个斐波纳契数。

前两个数字（对于i = 0，i = 1）是硬编码的（如(0, 0)和(1, 0)）。但当然我们不能保持对Fibonacci值的硬编码。如果我不是0或1，最后一行将被解雇。实施此案例是为了处理i-1案件。

在那种情况下，我们递归计算fibu' (n-1)（所以包含（Fn-1，Fn-2）的元组，我们在前两个Fibonacci数中计算出来。然后我们知道（这是Fibonacci归纳关系Fn = Fn-1 + Fn-2）。这意味着我们可以返回(a+l, l)。所以如果我们调用fibu' 5，它将调用fibu' 4，fibu' 3等，直到我们到达fibu' 1然后我们将每次构造一个新的元组，将继续计算最后两个斐波纳契数，直到我们用指数5达到斐波纳契数。

现在fibu'的唯一问题是它返回一个2元组，并且用户通常想要得到一个简单的数字（第i个Fibonacci数）。所以现在我们定义一个函数：

fibu :: Integer -Integer
fibu x = fst (fibu' x)

这将返回2元组的第一项（即第i个斐波纳契数）。

Answer 2

你可能已经看到了Fibonacci序列的天真实现：

fibo :: Integer -> Integer
fibo 0 = 0
fibo 1 = 1
fibo n = fibo (n-1) + fibo (n-2)

好吧，问题是该函数以递归方式调用自身两次。而且这些呼叫中的每一个都会再次召唤两次......所以你最终会得到指数级的呼叫。

你要问的实现是什么来解决这个问题：它不仅返回第n个斐波纳契数，而且返回第n个和第n-1个。然后n + 1调用只需要一个额外的调用，而不是两个调用，因为一次调用为计算序列的下一个元素提供了所需的全部内容。

对于最终结果，您不需要两个数字但只需要一个，因此使用fst丢弃倒数第二个值。