大四的萌新辣！

2.Even Fibonacci numbers

Posted on In Valine:

问题描述

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:

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

解法

  1. 一开始想的是我们可以直接写出对于前400万项的Fibonacci数列。

    然后判断每一项是否是偶数 再sum一下。

    时间复杂度：${O(2n)}$

    不过可以采用乘方优化达到${O(\log n + n)}$ 的复杂度

    可参考：https://www.cnblogs.com/AlvinZH/p/7637094.html

    BUT ：这种做法在400w情况下仍然爆了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  #include <bits/stdc++.h>
#define ll long long
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
using namespace std;

const int maxn = 4000000;
ll Fibonacci[maxn];
int ans = 0;
int main(void)
{
    IOS
    Fibonacci[1] = 1;
    Fibonacci[2] = 2;
    for(int i = 3; i <= maxn; i++)
        Fibonacci[i] = Fibonacci[i - 1] + Fibonacci[i - 2];
    for(int i = 1; i <= maxn; i++)
    {
        if(Fibonacci[i] % 2 == 0)
            ans += Fibonacci[i];
    }
    cout << ans << endl;;
    return 0;
}

  1. 数学解法：

    我们观察到 ，题目中只是让求出Fibonacci数列的偶数项之和，我们能否找到一个关于Fibonacci数列偶数项前${n}$项和的递推公式~

    观察题目中给的Fibonacci偶数项有：

    从第三项开始有：

    所以有以下公式(对Fibonacci偶数数列)：

    时间复杂度：${O(\frac{n}{2})}$[减少了一半的运算量]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #include <bits/stdc++.h>
       #define ll long long
       #define IOS {ios::sync_with_stdio(false);cin.tie(0);}
       using namespace std;
       
       const int maxn = 4000000;
       ll Fibonacci[maxn];
       int ans;
       int main(void)
       {
           IOS
           Fibonacci[1] = 2;
           Fibonacci[2] = 8;
           for(int i = 3; i <= maxn; i++)
               {
                   Fibonacci[i] = 4 * Fibonacci[i - 1] + Fibonacci[i - 2];
                   if(Fibonacci[i] < maxn)
                       ans += Fibonacci[i];
                   else
                       break;
               }
           cout << ans << endl;
           return 0;
       }

    注意点

    1. 判断偶数和！不是偶数个数！一开始写出SB代码…WA了

      读题意！！！

    正确答案

官方解答