斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

数学上，斐波那契数列以递归的形式进行定义：
$F_{0} = 0\ F_{1} = 1\ F_{n} = F_{n-1} + F_{n-2}$

先来开看看“兔子数列”以及其他数学应用场景！！

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?

有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?

这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……

1，2，3，5，8，13……所以，登上十级，有89种走法。

一枚均匀的硬币掷10次，问不连续出现正面的可能情形有多少种？

答案是:
$（1/√5)*{[(1+√5)/2]^(10+2) - [(1-√5)/2]^(10+2)}=144$

时间复杂度

空间复杂度

通过时间复杂度和空间复杂度评判代码的执行效率。

• 例如：从规模上来说，如果需要计算F(4)的值，需要进行9次元素操作

  设T(n)为计算n的时间复杂度，那么
  $T(n) = T(n-1) + T(n-2)+O(1)$

  粗略估算，$T（n） < O（2^n）$

打印正整数n之内的斐波那契数列

# Python特有， 常规写法
def fib(self, n):
	a = 0
	b = 1
	while a <= n:
		print(a, end=" ", flush=True)
		a, b = b, a + b  # python不借助变量交换两数的值

fib(100)  # 求n之内的斐波那契数列

$时间复杂度：O(n)， 空间复杂度：O(1)$

打印斐波那契数列前10位数字

# 递归
def fibonacci(i):
    num_list = [0, 1]
    if i < 2:
        return num_list[i]
    elif i >= 2:
        return (fibonacci(i - 2) + fibonacci(i - 1))


print(fibonacci(10))

$时间复杂度：O(n)， 空间复杂度：O(n)$

# 迭代的方式
class FibIterator(object):
    """斐波那契数列迭代器"""
    def __init__(self, n):
        """
        :param n: int, 指明生成数列的前n个数
        """
        self.n = n
        # current用来保存当前生成到数列中的第几个数了
        self.current = 0
        # num1用来保存前前一个数，初始值为数列中的第一个数0
        self.num1 = 0
        # num2用来保存前一个数，初始值为数列中的第二个数1
        self.num2 = 1

    def __next__(self):
        """被next()函数调用来获取下一个数"""
        if self.current < self.n:
            num = self.num1
            self.num1, self.num2 = self.num2, self.num1+self.num2
            self.current += 1
            return num
        else:
            raise StopIteration

    def __iter__(self):
        """迭代器的__iter__返回自身即可"""
        return self


if __name__ == '__main__':
    fib = FibIterator(10)
    for num in fib:
        print(num, end=" ")

从定义开始：
$F_{0} = 0\ F_{1} = 1\ F_{n} = F_{n-1} + F_{n-2}$