使用不含zipWith函数的方法计算斐波那契数列

Question

我一直在尝试实现一个从0到n的斐波那契数列列表，而不使用惰性zipwith方法。目前我所拥有的代码可以返回从n到1的列表。有没有办法修改这段代码，使其能够返回从0-n的列表呢？

示例：

fib_seq 4 = [3,2,1,1] 
-- output wanted: [1,1,2,3]

如果没有办法实现我想要代码实现的功能，是否有一种方法只返回斐波那契数列的列表，输入一个数字比如说4，它应该返回[0, 1, 1, 2]。

fib_seq :: Int -> [Int]
fib_seq 0 = [0]
fib_seq 1 = [1]
fib_seq n = sum (take 2 (fib_seq (n-1))) : fib_seq (n-1)

- Jimbhoy

---

最好使用let，fib_seq2 n = let { fs = fib_seq2 (n-1) } in sum (take 2 fs) : fs。比较fib_seq 30的速度。 - Will Ness

Answer 1

你可以选择使用一个辅助函数和一个独立的函数来产生斐波那契数列的无限列表，或者你可以使用take 10 fibs得到前10个斐波那契数。我实现的函数肯定不是计算斐波那契数列最快的方法，最快的方法是使用zipWith函数，但是在这里我们不使用它，所以这是我不用zipWith实现的方法。

例如，take 10 fibs将返回：[0,1,1,2,3,5,8,13,21,34]

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)   

fibs :: [Int]
fibs = (map fib [0..])

- program.exe

---

这正是我所需要的，因为它允许我选择是要无限列表还是选择要打印的斐波那契数列的数量。感谢您的帮助！ - Jimbhoy

没有问题，很高兴能够帮到你。在这个问题中还有一些其他很好的答案，请确保您已经仔细阅读并理解了它们。由于程序需要进行大量递归调用，因此我的版本对于计算更大的斐波那契数会非常缓慢。 - program.exe

Answer 2

经常情况下，你可以通过考虑问题的稍微更一般化的版本来解决问题。

假设我们想要从预先指定的两个初始值a和b开始的无穷斐波那契数列。有一个显然的递归解法:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 ...
 λ> 
 λ> aux_fib a b = a : (aux_fib b (a+b))
 λ> 
 λ> take 4 (aux_fib 1 1)
 [1,1,2,3]
 λ> 

好的：

 λ> 
 λ> fib_seq n = take n (aux_fib 1 1)
 λ> 
 λ> fib_seq 4
 [1,1,2,3]
 λ> 

注意: 在Haskell中，驼峰命名法被认为更符合习惯，因此更像是auxFib和fibSeq。

- jpmarinier

Answer 3

如果你想让列表从0开始，你可以使用一个辅助函数，并在fib_seq中使用这个辅助函数（我建议你将其改为驼峰式命名，比如fibSeq，标准的Haskell符号）。

好的，函数如下：fibSeq 7将返回[0,1,1,2,3,5,8]：

fibHelp :: Int -> Int -> [Int]
fibHelp x y = x : (fibHelp y (x+y))

fibSeq :: Int -> [Int]
fibSeq n = take n (fibHelp 0 1)

- tDownUnder

Answer 4

感觉有点作弊，但你可以像这样使用闭式公式来计算斐波那契数列：

fib n = (phi^n - psi^n) / sqrt 5
  where
    phi = (1 + sqrt 5) / 2
    psi = (1 - sqrt 5) / 2

fibSeq n = fib <$> [1 .. n]

否则，Haskell Wiki上有许多实现变体可供选择。例如，非常简洁。

fibs = 0 : 1 : next fibs
  where
    next (a : t@(b:_)) = (a+b) : next t

- michid

---

闭式公式很快就会产生极差的精度。矩阵平方指数法会更有效。 - dfeuer

我们需要一些形式的任意定点精度数字才能使其工作，也许？我们可以将fib n的数量级近似为phi^n，因此我们预先知道所需的位数，并且只需使用两倍以确保安全。问题是，这样做的复杂度会是什么。 :) @dfeuer - Will Ness

@WillNess，我不能告诉你，但似乎几乎肯定不会比平方乘法更好。 - dfeuer

@dfeuer 我的感觉也是这样。 :) - Will Ness

我指的是平方幂运算。 - dfeuer

关于矩阵形式，由于φ是一个代数数，您可以通过将其表示为具有有理（或在这种情况下为整数）系数的多项式的隐式根来避免精度问题，即x²-x-1，然后有一个非常漂亮的闭合形式公式的实现，但这个评论框太小了，无法容纳。它也不快哈哈。 - Jon Purdy