偶数项斐波那契数列求和

偶数项斐波那契数列求和

题目描述

斐波那契数列中的每个新项都是通过将前两个项相加而生成的。从1和2开始，前10个项将是：

1，2，3，5，8，13，21，34，55，89，…

通过考虑斐波那契数列中值不超过400万的项，找到偶值项的总和。

思路

可以直接通过公式来求，第三项等于前两项之和
也可以通过推导公式来求，只求偶数项
Fn=Fn−1+Fn−2
=Fn−2+Fn−3+Fn−3+Fn−4
=2Fn−3+Fn−2+Fn−4
=2Fn−3+(Fn−3+Fn−4)+(Fn−5+Fn−6)
=3Fn−3+Fn−4+Fn−5+Fn−6=4Fn−3+Fn−6
最终公式：EFn=4EFn−1+EFn−2(EF1=2,EF2=8)

代码

#include <iostream>
#include <vector>using namespace std;int main() {vector<int>q {2, 8};int n = 4000000;long long res = 0;int a = 2, b = 8, c = 0;while (1) {c = b * 4 + a;a = b;b = c;if (b < n) q.push_back(b);else break;}for (int i = 0; i < q.size(); i ++ ) {cout << q[i] << ' ';res += q[i];}cout << endl;cout << res << endl;return 0;
}