首页 > 代码库 > 关于斐波那契数列的一点小结

关于斐波那契数列的一点小结

斐波那契数列就是0,1,1,2,3,5……这样的一波数列,第三个数是前两个数的和。

兔子问题,上楼梯的台阶方法的个数问题,都是斐波那契数列。

斐波那契可以简单的用递归实现:

1 def fib(n)2    # Calculate the nth Fibonacci Number3    return n if n == 0 || n == 14    return fib(n-1) + fib(n-2) 5 end

简单有效,但是在n很大的时候时间长。

 

也可以用迭代来实现

 1 def fib(n) 2   return n if n == 0 || n == 1 3   a, b = 0, 1 4   until n == 1 5      b = a + b 6      a = b - a 7      n -= 1 8   end 9   b10 end    

时间复杂度o(n),空间复杂度o(1),就是两个变量a,b。

 

还有矩阵的方法

根据如下递推公式

可以求得,只需要计算矩阵[[1,1],[1,0]]的n次方即可,这个计算的时间复杂度是O(logn)

 1 require matrix 2 def fib(n) 3   mat = Matrix[[1,1],[1,0]] 4   return n if n == 0 || n == 1 5   return mat_n(mat,n-1).first 6 end 7  8 def mat_n(ma1,n) #计算矩阵的n次方 9   return ma1 if n == 110   n.even? ? mat_n(ma1,n/2)**2 : ma1*mat_n(ma1,n-1)11 end

这些都是网上可以找到的方法。

 

还有一种迭代的方法,复杂度也是O(logn)。

具体内容如下:

http://mitpress.mit.edu/sicp/chapter1/node15.html

其思想也是将两次迭代表示成一次迭代,这样n次迭代就只有o(logn)的时间就可以完成了。

 

另外,以上讨论的都是正数的情况,如果斐波那契数列的参数是负数呢?

由f(n+2) = f(n+1) + f(n),可以知道f(n) = f(n+2) - f(n+1),因此负数的斐波那契数列也是存在的。

递归方法可以直接得到,迭代方法也可以直接应用,这个矩阵方法就有点麻烦了,直接找比较难找出这个矩阵,可以先看一下负数的序列,

f(-1) = f(1)-f(0) = 1 ,f(-2) = -1 ,f(-3) = 2, f(-4) = -3,f(-5) = 5……

0 1 1 2 3 5 8 ……

0 1 -1 2 -3 5 -8 ……

找到规律了,在参数小于0的时候,斐波那契数列是一正一负分布的,而且和参数大于0恰好对应。哈哈,是不是很巧?

于是,计算的时候只要在参数为正数的情况下考虑奇偶就行了。

 

关于斐波那契数列的一点小结