找到Fibonacci系列的总和

Question

我已经给出了Set A我必须找到A的所有子集的Fibonacci和的总和.

Fibonacci(X)- 是Fibonacci系列的第X个元素
例如,用于A = {1,2,3}:

Fibonacci(1)+ Fibonacci(2)+ Fibonacci(3)+ Fibonacci(1 + 2)+ Fibonacci(2 + 3)+ Fibonacci(1 + 3)+ Fibonacci(1 + 2 + 3)1 + 1 + 2 + 2 + 5 + 3 + 8 = 22

有没有办法可以在不生成子集的情况下找到总和？

因为我觉得所有的子集的总和容易
即Sum of All Subset - (1+2+3)*(pow(2,length of set-1))

Answer 1

肯定有。

\n\n

首先，我们回顾一下第 n 个斐波那契数等于

\n\n

\xcf\x86(n) = [\xcf\x86^n - (-\xcf\x86)^(-n)]/\xe2\x88\x9a5

\n\n

其中\xcf\x86 = (\xe2\x88\x9a5 + 1)/2（黄金比例）和(-\xcf\x86)^(-1) = (1-\xe2\x88\x9a5)/2。但为了使其更短，让我将 \xcf\x86 表示为 A，将 (-\xcf\x86)^(-1) 表示为 B。

\n\n

接下来，我们注意到斐波那契数列的和是 A 和 B 的幂的和：

\n\n

[\xcf\x86(n) + \xcf\x86(m)]*\xe2\x88\x9a5 = A^n + A^m - B^n - B^m

\n\n

现在足以计算（在{1,2,3}示例中）的是

\n\n

A^1 + A^2 + A^3 + A^{1+2} + A^{1+3} + A^{2+3} + A^{1+2+3}。

\n\n

但是，嘿，有一个更简单的表达方式：

\n\n

(A^1 + 1)(A^2 + 1)(A^3 + 1) - 1

\n\n

现在，是时候得到全部结果了。

\n\n

让我们的集合成为{n1, n2, ..., nk}. 那么我们的总和将等于

\n\n

Sum = 1/\xe2\x88\x9a5 * [(A^n1 + 1)(A^n2 + 1)...(A^nk + 1) - (B^n1 + 1)(B^n2 + 1)...(B^nk + 1)]

\n\n

我认为，从数学上讲，这是答案的“最简单”形式，因为 n_i 之间没有关系。然而，这个表达式可能还有一些计算优化的空间。事实上，我根本不确定这（使用实数）是否会比“直接”求和更快，但问题是关于避免子集生成，所以这就是答案。

\n