题目链接：偶数斐波那契数

解法一：暴力枚举

看见题目，第一反应就是先找到小于400万的所有斐波那契数，再从这些斐波那契数中筛选出偶数进行求和。
由于递归方法求斐波那契数的时间复杂度较高，故这里采用迭代的方法。

先通过循环逐个计算每个斐波那契数，直到达到了指定的最大值 。在循环中，每次更新 n 的值，并根据斐波那契数列的递推公式fib[n] = fib[n-1] + fib[n-2]来更新fib[n] 的值。然后，通过一个循环遍历斐波那契数列的所有元素，并累加所有偶数元素的和到变量sum中。

C语言代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
#define Max_N 4000000
int fib[Max_N+5] = {0};
int main (){
    fib[1]=1,fib[2]=2;
    int n = 2;
    while(fib[n]+fib[n-1]<=Max_N){
        n++;
        fib[n]=fib[n-1]+fib[n-2];
    }
    int sum = 0;
    for(int i = 1;i<=n;i++){
        if(fib[i]%2==0)
            sum+=fib[i];
    }
    printf("%d\n",sum);
    return 0;
}

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Fib_Sum {  

    public static void main(String[] args) {  
        final int MAX_N = 4000000;  
        int[] fib = new int[MAX_N + 5];  
        fib[1] = 1;  
        fib[2] = 2;  
        int n = 2;  
        while (fib[n] + fib[n - 1] <= MAX_N) {  
            n++;  
            fib[n] = fib[n - 1] + fib[n - 2];  
        }  
        int sum = 0;  
        for (int i = 1; i <= n; i++) {  
            if (fib[i] % 2 == 0) {  
                sum += fib[i];  
            }  
        }  
        System.out.println(sum);  
    }  
}

解法二：滚动数组

简单的理解就是让数组滚动起来，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用。这道题，我们要用到的是连续的解，前面的解是可以舍去。所以可以让数组滚起来，这样可以减少空间的消耗。

C语言代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
#define Max_N  4000000
int main (){
    int fib[3]={0};
    fib[1]=1,fib[2]=2;
    int n = 2,sum = 2; //因为第二项斐波那契数也是偶数
    while(fib[n % 3] + fib[(n - 1) % 3] <= Max_N){
        n++;
        fib[n % 3] = fib[(n - 1) % 3] + fib[( n - 2) % 3];
        if(fib[n % 3] % 2 == 0) 
            sum += fib[n % 3];
    }
    printf("%d\n",sum);
    return 0;
}

按照这个思路，我们设置不需要开辟数组，直接利用三个变量来存储数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
#define Max_N 4000000
int main (){
	int a = 1, b = 2, c , sum = 2;
    while(a + b <= Max_N){
        c = a + b;
        a = b;
        b = c;
        if(c % 2 ==0)
            sum+=c;
    }
    printf("%d\n",sum);
    return 0;
}

上面这两段代码，在性能上没有显著的差异，它们的时间复杂度和空间复杂度都是 O(1)。但是，第二段代码可能更容易理解。因为它直接操作了斐波那契数列的当前值和前两个值，而无需通过数组索引。

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class FibonacciSum {
    public static void main(String[] args) {
        final int Max_N = 4000000;
        int[] fib = new int[3];
        fib[1] = 1;
        fib[2] = 2;
        int n = 2;
        int sum = 2; // 因为第二项斐波那契数也是偶数

        while (fib[n % 3] + fib[(n - 1) % 3] <= Max_N) {
            n++;
            fib[n % 3] = fib[(n - 1) % 3] + fib[(n - 2) % 3];
            if (fib[n % 3] % 2 == 0) {
                sum += fib[n % 3];
            }
        }

        System.out.println(sum);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class FibonacciSum {
    public static void main(String[] args) {
        final int Max_N = 4000000;
        int a = 1, b = 2, c, sum = 2;
        
        while (a + b <= Max_N) {
            c = a + b;
            a = b;
            b = c;
            if (c % 2 == 0) {
                sum += c;
            }
        }
        
        System.out.println(sum);
    }
}

参考文章

求解斐波那契数列(Fibonacci Numbers)算法居然有9种，你知道几种？
神奇的斐波那契数列