Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

1.利用数组求fib数列

  1. 开一个足够大的数组，并初始化前两项1，2
  2. 通过递推法逐个将斐波那契数列的每一项存入数组
  3. 将所有为偶数的项的数字相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;

long long num[4000005] = {1, 2};

int main(){
    long long sum = 0;
    int i = 2;
	//1.利用递推法求出斐波那契数列的每一项，并存入数组中
    while(num[i - 1] <= 4000000){
        num[i] = num[i - 1] + num[i - 2];
        i++;
    }
    //2.对数组每一项进行判断，若为偶数将其加入sum中
    for(int j = 0; j < i; j++){
        if(num[j] % 2 == 0){
            sum += num[j];
        }
    }
    cout << sum; 
    return 0;
}
//空间复杂度:O(n)

2.两个变量求fib数列

  1. 不需要定义数组，在运算的过程中就可以知道哪些项是偶数
  2. 计算过程中只保留两个数字：前一个数 和 后一个数，两个数循环相加即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

int main(){
    long long ans = 0;
    int a = 1, b = 2;
    
    while(b < 4000000){
        //1.在运算过程中就可以进行奇偶判断
        if(b % 2 == 0){
        	ans += b;
    	}
        //2.通过两个变量表示斐波那契数列两个数字
    	b = b + a;
        a = b - a;
    }
    cout << ans << endl;
    return 0;
}
//空间复杂度:O(1)

3.总结：

相对于方法1，方法2同时正向、反向利用了斐波那契数列项之间的关系，

从而避免了开辟数组空间，减小了算法的空间复杂度。在关于斐波那契数列的问题时要灵活运用项之间的关系

1
2
3
4
5
while(b < 4000000){
    if (b % 2 == 0) ans += b;
    b = b + a;
    a = b - a;
}
1
2
3
4
5
while(b < 4000000){
    if (b % 2 == 0) ans += b;
    b = b + a;
    swap(a, b);
}