三种Fibonacci数列第n项计算方法及其优劣分析

除了本文讨论的三种方法，之前的文章中还讨论了另外几种方法，详见相关阅读第一篇。

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