c++ - 斐波那契数列乘积之和

Question

<分区>

Answer 1

我无法将总和缩减为单个项，但可以将其缩减为五个项的总和，从而将复杂度降低为 O(log n)算术运算。

然而，Fib(n)有Θ(n)位，所以位操作的数量不是对数的。有一个大小为 Fib(n) 的数字相乘与 n-1 , 所以位操作的数量是 M(n,log n) , 其中M(a,b)是 a 乘法的位运算复杂度-位编号带有 b -位数。对于朴素算法，M(a,b) = a*b ，所以下面算法中的位操作数是O(n*log n) .

允许这种减少的事实是斐波那契数(就像由线性递归定义的序列中的所有数字一样)可以写成纯指数项的总和，特别是

Fib(n) = (α^n - β^n) / (α - β)

在哪里

α = (1 + √5)/2;    β = (1 - √5)/2.

除了斐波那契数列，我还使用了卢卡斯数列，它遵循与斐波那契数列相同的循环，

Luc(n) = α^n + β^n

所以卢卡斯数的序列(从索引 0 开始)以

开始

2 1 3 4 7 11 18 29 47 ...

关系Luc(n) = Fib(n+1) + Fib(n-1)允许斐波那契数和卢卡斯数之间的简单转换，以及 Luc(n) 的计算在O(log n)步骤可以重用斐波那契代码。

所以根据上面给出的斐波那契数的表示，我们发现

(α - β)^2 * Fib(k) * Fib(n+3-k) = (α^k - β^k) * (α^(n+3-k) - β^(n+3-k))
                                = α^(n+3) + β^(n+3) - (α^k * β^(n+3-k)) - (α^(n+3-k) * β^k)
                                = Luc(n+3) - ((-1)^k * α^(2k) * β^(n+3)) - ((-1)^k * α^(n+3) * β^(2k))

使用关系 α * β = -1 .

现在，自 α - β = √5求和k = 1, ..., n-1产量

   n-1                                              n-1                   n-1
5 * ∑ Fib(k)*Fib(n+3-k) = (n-1)*Luc(n+3) - β^(n+3) * ∑ (-α²)^k - α^(n+3) * ∑ (-β²)^k
   k=1                                              k=1                   k=1

几何和可以写成封闭形式，稍加改动就可以得出公式

n-1
 ∑ Fib(k)*Fib(n+3-k) = [5*(n-1)*Luc(n+3) + Luc(n+2) + 2*Luc(n+1) - 2*Luc(n-3) + Luc(n-4)]/25
k=1