1

给定一个系列

Fib(1) * Fib (n+2) + Fib(2) * Fib(n+1) + Fib(3) * Fib(n) + ...... + Fib(n-1) * Fib( 4)

或求和 Fib(x) * Fib (n-x+3)其中 x 从 1 变化到 n-1 其中 Fib(n) 是斐波那契数列的第 n 个数

评估这个系列 Fib(n) 可以使用矩阵求幂来计算。

但是这个的复杂性是 logn 并且对于 n 项它会是 nlogn 。

我希望这个系列可以简化为一个术语或一些其他优化，以提高*时间复杂度。*

有什么建议么 ？？

4

4 回答 4

3

我不能将总和减少为一项，但可以将其减少为五项的总和，从而降低O(log n)算术运算的复杂性。

但是，Fib(n)有Θ(n)位，所以位操作的数量不是对数的。有一个大小为 的数的乘法Fib(n)，n-1因此位操作的数量为M(n,log n)，其中是位数与位数相乘的位M(a,b)操作复杂度。对于朴素算法，，所以下面算法中的位操作数是。abM(a,b) = a*bO(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
于 2012-09-03T15:25:55.727 回答
2

要遵循的步骤：

  • 定义std::vector<int>并用您需要的所有斐波那契数填充它。使用动态规划计算这些数字；也就是说，利用您已经计算过的结果。不要多次计算相同的值！

  • 一旦你用你需要的所有数字填充了向量，Fib(x) * Fib (n-x+3)在循环中应用公式并计算产品的总和。

于 2012-09-03T13:17:14.587 回答
2

假设和, f(n)=f(n-1)+f(n-2)_n>2f(1)=f(2)=1f(0)=0

让 明确E(n)=sum(k=1 .. n-1, f(k)f(n-k+3))_E'(n)=sum(k=0 .. n, f(k)f(n-k))
E(n)=E'(n+3) - ( f(0)f(n+3) + f(n)f(3) + f(n+1)f(2) + f(n+2)f(1) + f(n+3)f(0) )

在wolfram上，您会发现 : E'(n)= (nL(n)-f(n))/5，L(n)=f(n+1)+f(n-1)

由此 ：
5E(n)=(n+3)( f(n+4)+f(n+2) ) - 5(2f(n) + f(n+1) +f(n+2))
5E(n)=(n+3)( 4f(n+1)+3f(n) ) - 10f(n+1) -15f(n)
5E(n)= (4n+2)f(n+1) + (3n-6)f(n)

应该很容易评估，复杂度应该和使用的斐波那契算法一样，

于 2012-09-03T14:52:58.503 回答
1

如果我知道卢卡斯号码是什么，那么我可以使用身份...

F(n)*F(m) = [L(m+n) - (-1)^n*L(mn)]/5

看到这将斐波那契数的乘积之和减少为卢卡斯数的总和。

更好的是，由于 n+m 对于每一项都是常数，因此总和会进一步减少。这个总和有 n-1 项，所以总和减少到卢卡斯数的总和。

[(n-1)*L(n+3) + L(n+1) - L(n-1) + L(n-3) - ... + (-1)^(n-1)* L(5-n)]/5

作为测试，对于 n = 5，我得到 40，这与产品的直接总和一致：

1*13 + 1*8 + 2*5 + 3*3 = 40

对于 n = 1000，我得到一个总和：

82283375600539014079871356568026158421560221654785733943009487102720 211767741849325389562067921531531130739623611293922046989610820831567088 516047002196966545744637588824274730947688693969572937880383134671205375

更好的是，一些额外的工作将使卢卡斯数的总和进一步收缩，因为负指数的卢卡斯数与正指数的卢卡斯数有简单的关系。

就计算第 k 个卢卡斯（以及第 k 个斐波那契）数而言，它可以非常有效地完成，如此处所示。

于 2012-09-03T15:13:48.810 回答