三种Fibonacci数列第n项计算方法及其优劣分析
感谢国防科技大学刘万伟老师和中国传媒大学胡凤国两位老师提供的思路，文章作者不能超过8个字符，我的名字就写个姓吧，名字不写了^_^。另外，除了本文讨论的三种方法，之前的文章中还讨论了另外几种方法，详见相关阅读第一篇。
def fibo4(n):
'''递推法
适用于任意大小的n
使用生成器函数
速度快，无误差'''
def nested():
a, b = 1, 1
while True:
yield a
a, b = b, a+b
# 创建生成器对象
temp = nested()
# 获取前n-1项
for i in range(n-1):
next(temp)
# 返回第n项
return next(temp)
def fibo5(n):
'''通项公式法，速度也不错
涉及实数运算，会有误差，
n越大，误差越大，
n大到一定程度会崩溃'''
z = 5**0.5
u = (1+z) / 2
v = (1-z) / 2
return int((u**n - v**n)/(u-v))
from sympy import sqrt, Symbol, simplify
def fibo6(n):
'''通项公式法，速度快
通过符号计算库的简化策略，
弥补了实数运算引入的误差'''
c1 = ((1+sqrt(5))/2)
c2 = ((1-sqrt(5))/2)
c3 = sqrt(5)
k = Symbol("k")
f = (c1**k-c2**k)/c3
return simplify(f.subs(k, n))
n = 50
print(fibo4(n))
print(fibo5(n))
print(fibo6(n))
当n=50时，运行结果为：
12586269025
12586269025
12586269025
当n=80时，运行结果如下，注意开始fibo5有误差了：
23416728348467685
23416728348467744
23416728348467685
当n=200时，运行结果如下，误差越来越大了：
280571172992510140037611932413038677189525
280571172992512015699912586503521287798784
280571172992510140037611932413038677189525
当n=8000时，fibo4和fibo6仍然正常工作，而fibo5在n=1500左右时就已经无法工作了，代码崩溃。
Traceback (most recent call last):
File "C:/Python36/fibonacci.py", line 43, in <module>
print(fibo5(n))
File "C:/Python36/fibonacci.py", line 27, in fibo5
return int((u**n - v**n)/(u-v))
OverflowError: (34, 'Result too large')
----------相关阅读---------
Python组合列表中多个整数得到最小整数（一个算法的巧妙实现）
哈夫曼编码原理与Python实现代码（附手动推导过程原稿真迹）
Python版归并排序算法（附Python程序__name__属性用法演示视频）
----------喜大普奔----------
1、继《Python程序设计基础》（2017年9月第5次印刷）、《Python程序设计（第2版）》（2017年9月第4次印刷）、《Python可以这样学》（2017年7月第3次印刷）系列图书之后，董付国老师新书《Python程序设计开发宝典》已于2017年8月1日在清华大学出版社出版，并于2017年9月进行了第2次印刷。为庆祝新书《Python程序设计开发宝典》全面上架，清华大学出版社联合“赣江图书专营”淘宝店推出特价优惠活动，《Python程序设计开发宝典》原价69元，新书上架期间超低价39.8元，可以复制下面的链接使用浏览器打开查看图书详情和购买：
https://detail.tmall.com/item.htm?spm=a1z10.3-b-s.w4011-14464369246.84.46f16db0roWfX4&id=557107249812&rn=339cbc9df2bac424664103917dedfbd2&abbucket=8&tbpm=3
