三种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')