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 团队
微信号:算法与编程之美
长按识别二维码关注我们!
温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!