花式编程之斐波拉契数列

昨天讲完了斐波拉契数列，今天使用多种编程技巧来实现斐波拉契数列。

普通循环法

普通循环的方法就是我们昨天讲过的，这里贴出程序：

def fib1(n):
    ret = [] # 用于存储菲波拉契数
    a, b = 0, 1 # 设定初始值
    while b < n: # 判断斐波拉契数小于指定值
        ret.append(b) # 添加到存储列表
        a, b = b, a+b # 生成下一个菲波拉契数
    return ret 

if __name__ == '__main__':
    fibs = fib1(100) # 调用函数
    print(fibs) # 打印斐波拉契列表

普通循环法还可以使用for循环来实现：

def fib2(n):
    """指定生成n个斐波拉契数"""
    ret = []
    a, b = 0, 1
    for i in range(n):
        ret.append(b)
        a, b = b, a + b
    return ret

if __name__ == '__main__':
    fibs = fib2(10) # 生成前10个斐波拉契数
    print(fibs)

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

递归法

递归简单说就是函数调用自身的行为，称为递归。

def _fib(n):
    """递归法 得到第n个斐波拉契数"""
    if n <= 0: # 小于0直接返回None
        return
    if n == 1 or n == 2: # 当n为1或者2时，返回1
        return 1
    else:
        return _fib(n-1) + _fib(n-2) # 前两项之和

def fib3(n):
    """调用递归函数,输出前n个斐波拉契数"""
    ret = []
    for i in range(1, n+1):
        ret.append(_fib(i))
    return ret

if __name__ == '__main__':
    print(fib3(10)) # 打印前10个斐波拉契数

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

生成器法

这里主要使用yield关键词，对于Python编程部分，后续会有系列着重讲解。

def fib4(n):
    """生成器"""
    a, b = 0, 1
    for i in range(n):
        yield b # 在于yield关键词
        a, b = b, a + b

if __name__ == '__main__':
    print(list(fib4(10)))

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

矩阵法

def fib5(n):
    """矩阵法"""
    ret = []
    m = np.matrix([[1, 1], [1, 0]])
    for i in range(n):
        ret.append((m ** i)[0, 0])
    return ret

if __name__ == '__main__':
    print(fib5(10))

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

比较用时

编写计时函数，用于统计每种斐波拉契数列生成的用时，编写函数如下：

def time_all():
    num = 10000
    t2 = time()
    fib2(num)
    f2 = time() - t2
    print("循环法用时: ",f2)

    # t3 = time()
    # fib3(num)
    # f3 = time() - t3
    # print("递归法用时:", f3)

    t4 = time()
    list(fib4(num))
    f4 = time() - t4
    print("生成器法用时:", f4)

    t5 = time()
    fib5(num)
    f5 = time() - t5
    print("矩阵法用时:", f5)

循环法用时:  0.008877992630004883
生成器法用时: 0.0039789676666259766
矩阵法用时: 0.412276029586792

总结

本次内容主要讲解了使用Python编程，实现斐波拉契数列的几种方法，分别是：

1. 循环法。包括for循环和while循环
2. 递归法。
3. 生成器法。
4. 矩阵法。
   综上可以发现生成器的效率非常高（没有比较递归），生成1万个斐波拉契数列用时最少。没有比较递归法，是因为此处实现的递归算法，产生了大量的重复计算，比较用时显得没有意义。
   注意：time_all函数功能是统计每个函数的用时，非常影响程序的美观，如何优雅地编程是每个程序员应该追求的。下节内容引入装饰器的概念，进一步改写time_all函数。