Python|斐波那契数列
欢迎点击「算法与编程之美」↑关注我们！
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。
1 定义
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
规律是：这个数列从第3项开始，每一项都等于前两项之和。
2 代码
递推法
滚动变量，产生数据量少。
|
def fib(n): a, b = 1, 1 for i in range(n-1): a, b = b, a+b return a |
递归法
编写代码量少，但随数据增大，产生大量数据，效率会非常低。
|
def fib(n): return n <= 2 and 1 or fib(n-1)+fib(n-2) |
矩阵法
根据数列从第3项开始，每一项都等于前两项之和这一规律列式：
然后就可以利用numpy第三方库矩阵相乘来求斐波那契数列。
|
import numpy def fib(n): return (numpy.matrix([[1, 1], [1, 0]]) ** (n - 1) * numpy.matrix([[1], [0]]))[0, 0] |
3 总结
上面三种方法在数据小的情况下效率差不多，前两种方法更容易思考，编写的代码量少且结构简单，特别是递归法。但随着数据的增大，递归产生大量数据，效率会非常低，递推法中变量是滚动的，不会产生太大数据。而矩阵法快速相乘的效率会比其他两种方法更好。
END
主 编 | 王文星
责 编 | 周茂林
where2go 团队
微信号：算法与编程之美
长按识别二维码关注我们!
温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！