58

在 Haskell 中，如何根据第 n 个斐波纳契数等于第 (n-2) 个斐波纳契数加上第 (n-1) 个斐波纳契数的属性生成斐波纳契数？

我看过这个：

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

我真的不明白这一点，或者它如何产生一个无限列表而不是一个包含 3 个元素的列表。

我将如何编写通过计算实际定义而不是通过使用列表函数做一些非常奇怪的事情来工作的haskell代码？

4

12 回答 12

102

这是一个计算第 n 个斐波那契数的不同且更简单的函数：

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

您所指的实现中继了一些关于斐波那契值如何相互关联的观察（以及 Haskell 如何根据自身定义数据结构，从而有效地创建无限数据结构）

您问题中的功能如下所示：

假设您已经有一个无限的斐波那契数列：

   [ 1, 1, 2, 3, 5,  8, 13, .... ]

这份tail名单是

   [ 1, 2, 3, 5, 8, 13, 21, .... ]

zipWith使用给定的运算符逐个元素地组合两个列表：

   [ 1, 1, 2, 3,  5,  8, 13, .... ]
+  [ 1, 2, 3, 5,  8, 13, 21, .... ]
=  [ 2, 3, 5, 8, 13, 21, 34, .... ]

因此，斐波那契数的无限列表可以通过在元素前面加上使用运算符将​​斐波那契数的无限列表1与1斐波那契数的无限列表的尾部压缩的结果来计算+。

现在，要获取第 n 个斐波那契数，只需获取斐波那契数的无限列表的第 n 个元素：

fib n = fibs !! n

Haskell 的美妙之处在于它在需要之前不会计算斐波那契数列中的任何元素。

我让你的头爆炸了吗？:)

于 2009-07-09T18:57:52.890 回答
32

按照定义，斐波那契数列的每一项都是前两项之和。把这个定义放到懒惰的haskell中会给你这个！

fibo a b = a:fibo b (a+b)

现在只需从 fibo 中取 n 个项目，从 0,1 开始

take 10 (fibo 0 1)
于 2014-02-06T14:31:26.650 回答
23

要扩展 dtb 的答案：

“简单”解决方案之间有一个重要区别：

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

而你指定的那个：

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

简单的解决方案需要O(1.618 N N)时间来计算第 N 个元素，而您指定的需要 O(N 2 )。那是因为您指定的那个考虑到计算fib n和fib (n-1)（计算它所需要的）共享 的依赖关系fib (n-2)，并且可以为两者计算一次以节省时间。O(N 2 ) 用于 O(N) 位数的 N 次加法。

于 2009-07-09T21:05:11.480 回答
6

这里有许多用于斐波那契数列的不同 Haskell 算法。“天真”的实现看起来就像你所追求的。

于 2009-07-09T19:00:29.453 回答
6 
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

首先，使用fibsand tail fibs，我们可以得到第三个元素：

fibs                        : [1, 1, ?
tail fibs                   : [1, ?
zipWith (+) fibs (tail fibs): [2, ?

现在，我们知道第三个是 2，我们可以得到第四个：

fibs                        : [1, 1, 2, ?
tail fibs                   : [1, 2, ?
zipWith (+) fibs (tail fibs): [2, 3, ?

现在是第五个：

fibs                        : [1, 1, 2, 3, ?
tail fibs                   : [1, 2, 3, ?
zipWith (+) fibs (tail fibs): [2, 3, 5, ?

等等 ..

于 2019-07-24T18:13:26.250 回答
3

fibonaci(n)的定义是：

fibonacci (n) = fibonacci (n-1) + fibonacci (n-2)

Haskell 中的幼稚实现

fibonacci :: Integer -> Integer
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci x = fibonacci (x-1) + fibonacci (x-2)

所有的公式都可以追溯到这个定义，有些跑得很快，有些跑得很慢。上面的实现有 O(n) = 2^n

本着你的问题的精神，让我删除列表的使用，并给你一些在 O(n) 中运行的东西，即我们不要将所有从 0 到 n 的斐波那契保存在一个列表中。

如果我们有一个三元组（一个包含三个成员的元组），看起来像：

(n, fibonacci[n-1], fibonacci[n])

记住最初的定义，我们可以从最后一个三元组计算下一个三元组：

(n+1, fibonacci[n], fibonacci[n-1] + fibonacci[n]) =(n+1, fibonacci[n], fibonacci[n+1])

最后一个三元组的下一个三元组： (n+2, fibonacci[n+1], fibonacci[n] + fibonacci[n+1]) =(n+1, fibonacci[n+1], fibonacci[n+2])

等等……

n = 0 => (0,0,1) 
n = 1 => (1,1,1) - calculated from the previous triple
n = 2 => (2,1,2) - calculated from the previous triple
n = 3 => (3,2,3) - calculated from the previous triple
n = 4 => (4,3,5) - calculated from the previous triple
n = 5 => (5,5,8) - calculated from the previous triple

让我们在 Haskell 中实现它并使用自解释变量名称：

nextTripleIfCurrentNIsLessThanN :: (Int, Integer, Integer) -> Int -> (Int, Integer, Integer)
nextTripleIfCurrentNIsLessThanN (currentN, x, y) n = if currentN < n
then nextTripleIfCurrentNIsLessThanN (currentN + 1, y, x + y) n
else (currentN, x, y)

thirdElementOfTriple :: (x,y,z) -> z
thirdElementOfTriple (x,y,z) = z

fibonacci :: Int -> Integer
fibonacci n = thirdElementOfTriple (nextTripleIfCurrentNIsLessThanN (0,0,1) n)

这将在 O(n) 中起作用 [它是温和的二次方，大量出现。原因是添加大数字比添加小数字更昂贵。但这是关于计算模型的单独讨论。]

fibonacci 0
1
fibonacci 1
1
fibonacci 2
2
fibonacci 3
3
fibonacci 4
5
fibonacci 5
8
fibonacci 5000
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626
于 2017-11-09T15:36:43.420 回答
1

使用迭代

fibonaci = map fst (iterate f (0,1)) where f (x,y) = (y,x+y)

使用

take 10 fibonaci

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
于 2014-04-19T13:50:32.113 回答
1

一种生成无限斐波那契数列的惰性方法可以通过unfoldr以下方式轻松实现；

fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)
于 2017-05-10T16:36:33.783 回答
0

大声笑，我喜欢 Haskell 模式匹配，但它在标准斐波那契函数中变得无用。标准列表是从右侧构建的。要使用模式匹配和缺点，必须从左侧构造列表。好吧，至少有一个安慰是，这真的很快。〜O（n），应该是。需要一个辅助函数来反转无限列表（您只能在 Haskell 中做的事情，joy），并且此函数输出运行的每个后续列表，因此“last”也用于辅助函数管道中。

f (x:y:xs) = (x+y):(x:(y:xs))

帮手

fib n = reverse . last . take n $ iterate f [1,0]

这是一个列表版本，我认为，它解释了列表是如何构建的，这是目的。我想做一个元组版本。

2018 年 3 月 15 日编辑

首先，Will Ness 启发了我的知识，即在每次迭代中生成的整个列表是不必要的，并且只需要使用的最后两个值，并且结果列表的值是生成的每个列表或对的第一个值。太有趣了。在威尔告诉我列表的值是列表的第一个值之后，我运行它并看到值 0,1,1,2,3,5,8,13 作为每个列表的每个头部，我说 WTF，会在我的电脑上更改我的代码吗？价值观在那里，但如何！？过了一会儿，我意识到他们一直在那里，但我只是没有看到他们。啊。Will 的函数和辅助函数的版本是：

f = (\(x:y:xs) -> (x+y):x:xs) -- notice, no y: put back only x+y & x

和他的辅助函数重写

fib n = map head . take n $iterate f [0,1]

我也认为它们现在可以合并：

fib n = take n . map head $ iterate (\(x:y:xs) -> (x+y):x:xs) [0,1]

顺便说一句，该函数也可以与元组一起使用

fib n = take n . map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

另一种形式，列表推导形式，也可以写成所有人：

fib n = take n [ fst t | t <- iterate (\(a,b) -> (b,a+b)) (0,1)]

这些都是迭代的和健壮的。最快的是 fib 5000 的列表为 12.23 秒的映射。fib 5000 的元组理解在 13.58 秒时第二快。

于 2018-03-11T19:20:33.420 回答
0

输入代码，你的定义是

fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
  -- i.e.
  -- fib (n+2) = fib (n+1) + fib n

Int -> a ~= [a]因为

from f = map f [0..]     -- from :: (Int -> a) -> [a]
to = (!!)                -- to :: [a] -> (Int -> a)

因此

fibs :: [Integer]
fibs = from fib 

fibs !! 0 = 1
fibs !! 1 = 1
fibs !! (n+2)    = fibs !! (n+1)     +  fibs !! n
-- or,
drop 2 fibs !! n = drop 1 fibs !! n  +  fibs !! n
                 = zipWith (+) (tail fibs) fibs !! n
-- i.e.
take 2 fibs = [1,1]
drop 2 fibs = zipWith (+) (tail fibs) fibs
-- hence, 
fibs = take 2 fibs ++ drop 2 fibs
     = 1 : 1 : zipWith (+) (tail fibs) fibs

或者，如a, b = (0,1) : (b, a+b)：

fibs :: [Integer]
fibs = a
  where
  (a,b) = unzip $ (0,1) : zip b (zipWith (+) a b)
于 2019-11-12T15:32:45.740 回答
0

我在做CIS194的作业6，发现你可以这样写。计算前 n 个元素只需要 O(n) 加法运算。

fibs2 :: [Integer]
fibs2 = [0, 1] ++ [fibs2 !! (n-1) + fibs2 !! (n-2) | n <- [2..]]
于 2020-11-09T12:25:37.150 回答
0

我试图在 python3 中重新实现它。目标是在 python 中获得一个类似的算法，这显然是相同的，但不是模仿 Haskell 的所有方面。

我想出了以下代码。

fibs.py：

# python version of Haskell's code
#    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

from operator import add

fibsList = [1, 1]  # growing

def fibs(n):
  if n >= len(fibsList):                # lazy evaluation
    x=zipWith(n-2,add,fibs,tail(fibs))  # or: ...,fibs,tailfibs)
    fibsList.append(x)
  return fibsList[n]

def zipWith(n,op,list1,list2):
  return op(list1(n),list2(n))

def tail(list):                         # or: def tailfibs(n):
  return lambda n : list(n + 1)         #       return fibs(n+1)

# test
print (fibs(10))
print (*fibsList)

运行它会输出

$ python fibs.py
89
1 1 2 3 5 8 13 21 34 55 89

这将与 Haskell 代码执行相同的操作，但它是一步一步的版本，您可以在其中添加一些日志记录

于 2022-01-28T08:35:08.740 回答