昨天讲完了斐波拉契数列，今天使用多种编程技巧来实现斐波拉契数列。
普通循环法
普通循环的方法就是我们昨天讲过的，这里贴出程序：
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编程，实现斐波拉契数列的几种方法，分别是：
- 循环法。包括
for循环和while循环 - 递归法。
- 生成器法。
- 矩阵法。
综上可以发现生成器的效率非常高（没有比较递归），生成1万个斐波拉契数列用时最少。没有比较递归法，是因为此处实现的递归算法，产生了大量的重复计算，比较用时显得没有意义。
注意：time_all函数功能是统计每个函数的用时，非常影响程序的美观，如何优雅地编程是每个程序员应该追求的。下节内容引入装饰器的概念，进一步改写time_all函数。
