Python斐波拉契数列

什么是斐波拉那契数列

斐波拉契数列（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)

运行结果：

图片.png

计算过程：

图片.png

扩展阅读：

在打印列表的过程中，很多时候只用到前几个元素，后面很多元素根本用不到，白白占用了存储空间，特别是列表数量上百万、千万、甚至无穷大时，那么有没有一种办法可以用几个元素就计算到第几个呢？用生成器就可以解决这个问题。

把前面的函数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)