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
主 编 | 王文星
责 编 | 周茂林
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读