1.　斐波那契数列 概念引入

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

1. python特有写法

打印正整数n之内的斐波那契数列
时间复杂度：O(n)，空间复杂度：O(1)

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之内的斐波那契数列

2. 递归

打印斐波那契数列前10位数字
时间复杂度：O(n)，空间复杂度：O(n)

# 递归
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))

3. 类对象

# 迭代的方式
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=" ")

4. 矩阵解决问题

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

def qpow(base, exp):
    if exp == 0:
        return 1
    ret = 1
    while exp:
        if exp & 1:
            ret = ret * base
        base = base * base
        exp >>= 1
    return ret

5. 矩阵再推导

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

def fib(n):
    if n < 1:
        return (1, 0)

    f_m_1, f_m = fib(n >> 1)
    if n & 1:
        return f_m_1 * (f_m_1 + 2 * f_m), f_m ** 2 + f_m_1 ** 2
    else:
        return f_m_1 ** 2 + f_m ** 2, f_m * (2 * f_m_1 - f_m)

6. 求第n位斐波值

def fib(n):
    if n < 1:
        return -1
    if (1 == n) or (2 == n):
        return 1
    return fib(n - 1) + fib(n - 2)

def main():
    n = int(input("请输入求解第几项： "))
    result = fib(n)
    print(result)

if __name__ == '__main__':
    main()

7. 实用版

#省内存
def fbnq(n):
    a,b=1,1
    if n==1 or n ==2:
        return 1
    else:
        i=3
        while i<=n:
            a,b=b,a+b
            i+=1
        return b

print(fbnq(int(input("输入一个数："))))

8. 迭代器版

class feibo(object):
    def __init__(self, length):
        self.num1 = 0
        self.num2 = 1
        self.num = self.num1
        self.length = length
        self.index = 0

    def __iter__(self):
        return self

    def __next__(self):
        self.num = self.num1
        while True:
            if self.index == self.length:
                raise StopIteration
            self.num1, self.num2 = self.num2, self.num1+self.num2
            self.index += 1
            return self.num


myfbnq = feibo(10)
# print(list(myfbnq))    # 指针位置已到最后一位
for i in myfbnq:
    print(i)