什么是斐波拉那契数列
斐波拉契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
也就是说斐波那契数列就是从第三个数开始(第一、二两个数都是1),后面的数都是前两个数之和。那么如何用Python来表示该数列呢?
算法思路:
- 初始化前两个数a和b为1
- 从第三个数开始,大小等于前面两个数之和,F(3)=F(1)+F(2)
- 用循环语句打印该数列
代码示意:
def fib(max):
n, a, b = 0, 0, 1
while n < max:
print b
a, b = b, a+b
n += 1
print 'Done'
fib(6)
运行结果:
计算过程:
扩展阅读:
在打印列表的过程中,很多时候只用到前几个元素,后面很多元素根本用不到,白白占用了存储空间,特别是列表数量上百万、千万、甚至无穷大时,那么有没有一种办法可以用几个元素就计算到第几个呢?用生成器就可以解决这个问题。
把前面的函数print改成yield即可:
def fib(max):
n, a, b = 0, 0, 1
while n < max:
yield b
a, b = b, a+b
n += 1
print 'Done'
fib(6)