斐波那契直接计算公式

Question

我看到斐波那契有直接公式 (Phi^n)/√5 虽然我在同一时间得到结果，但准确的结果与我设法写的东西不相近：

for r = 0 to 2 Sum [(n-r)!/((n-2r)!r!)]

（! 是阶乘的符号）：

def fr(n, p):
    # (n-r)!/((n-2r)!r!)
    r = int(n / p)
    n_f = 0
    for j in range(1, r + 1):
        t_f = 1
        r_f = factorial(j)
        i = (n - j)

        while i > (n - (2 * j)):
            t_f = t_f * i
            i = i - 1

        n_f = n_f + t_f / r_f

    return n_f + 1

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

所以对于 12 我们可以做 fr(11, 2) 也 (Phi12)/√5 = 144.0013888754932 四舍五入到 Fib(12) =144

我不明白为什么 (n-r)!/((n-2r)!r!) 很快

Answer 1

第n个斐波那契数的比奈公式如下：

def binet(n):
    phi = (1 + 5**.5) / 2
    psi = (1 - 5**.5) / 2
    return (phi**n - psi**n) / 5**.5

这个公式在数学上是精确的，但在实践中它容易出现浮点误差。 psi**n 项随着 n 的增加迅速收敛到零，因此当 n 很大时可以省略。这会产生您的近似公式。

比奈的公式非常快。在我的机器上，它计算出第 1000 个斐波那契数大约需要 400 纳秒。

In [21]: %timeit binet(1000)
426 ns ± 24.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

斐波那契数列的二项式求和公式很有趣。它表示斐波那契数是沿帕斯卡三角形的浅对角线求和，如图所示。

这个公式之所以有效，是因为每条对角线都是前两条对角线的总和，就像斐波那契数列中的每一项都是前两项的总和一样。比如第九条和第十条对角线相加可以得到第十一条对角线

    1 +  7 + 15 + 10 + 1 = 34
1 + 8 + 21 + 20 +  5     = 55
-----------------------------
1 + 9 + 28 + 35 + 15 + 1 = 89

但是，这个公式一点也不快。它似乎很快，因为计算机每秒可以执行数百万次计算。我的机器需要 84 毫秒来使用您的代码计算第 1000 个斐波那契数。这比使用 Binet 公式所需的时间长 200,000 倍。

 In [22]: %timeit fr(1001, 2)
 84 ms ± 875 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

斐波那契直接计算公式

Fibonacci direct calculation formula

python

math

fibonacci