C++程序 查找斐波那契数列偶数项之和

给定一个正整数N，任务是找到F2 + F4 + F6 + …… + F2n的值，其中Fi表示第i个斐波那契数。

斐波那契数列是以下整数序列中的数字。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……

示例：

输入: n = 5

输出: 88

N = 5，因此将生成从零项到第十项的斐波那契数列：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

在偶数项处的元素之和=0 + 1 + 3 + 8 + 21 + 55

输入: n = 8

输出: 1596

0 + 1 + 3 + 8 + 21 + 55 + 144 + 377 + 987 = 1596

方法－1: 此方法通过直接找到所有斐波那契数，然后只从偶数索引中加总。但它需要O(n)的时间复杂度。
下面是以上方法的实施:

// C++程序查找偶数项斐波那契数列之和
#include <bits/stdc++.h>
using namespace std;
 
// 计算前n个斐波那契数并将偶数索引的和存储起来
int calculateEvenSum(int n)
{
    if (n <= 0)
        return 0;
 
    int fibo[2 * n + 1];
    fibo[0] = 0, fibo[1] = 1;
 
    // 初始化结果
    int sum = 0;
 
    // 添加剩余的项
    for (int i = 2; i <= 2 * n; i++)
    {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
 
        // 对于偶数索引
        if (i % 2 == 0)
            sum += fibo[i];
    }
 
    // 返回交替和
    return sum;
}
 
// 主函数
int main()
{
 
    // 获取n
    int n = 8;
 
    // 找到偶数索引总和
    cout << "Even indexed Fibonacci Sum upto " <<
             n << " terms: " << calculateEvenSum(n) <<
             endl;
 
    return 0;
}  

输出:

Even indexed Fibonacci Sum upto 8 terms: 1596

时间复杂度: O(N).

辅助空间: O(N).

方法－2:

可以清楚地看到，可以这样得到所需求的和：

2 ( F 2 + F 4 + F 6 +………+ F 2n ) = (F 1 + F 2 + F 3 + F 4 +………+ F 2n ) – (F 1 – F 2 + F 3 – F 4 +………+ F 2n )

现在可以将公式中的 n 替换为 2n 以得到第一项。

因此 F 1 + F 2 + F 3 + F 4 +………+ F 2n = F 2n+2 – 1。

如果将公式中的 n 替换为 2n，则可以找到第二项。

因此，F 1 – F 2 + F 3 – F 4 +………- F 2n = 1 + (-1) 2n+1 F 2n-1 = 1 – F 2n-1 。

因此，2 ( F 2 + F 4 + F 6 +………+ F 2n )

= F 2n+2 – 1 – 1 + F 2n-1

= F 2n+2 + F 2n-1 – 2

= F 2n + F 2n+1 + F 2n+1 – F 2n – 2

= 2 ( F 2n+1 -1)

因此，( F 2 + F 4 + F 6