第2题: 偶斐波那契数

2023-06-30 2024-04-02 约 500 字预计阅读 1 分钟

题目

偶斐波那契数

斐波那契数列中的每一项都是前两项的和。由 $1$ 和 $2$ 开始生成的斐波那契数列的前 $10$ 项为:

$$ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots $$

考虑该斐波那契数列中不超过四百万的项，求其中为偶数的项之和。

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, \ldots $$

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

解题方法

暴力计算

直接生成小于四百万的斐波那契数列，依次判断数字是否满足条件并累加。

通项公式

观察斐波那契数列 $F_{n}$ 可知，每间隔两个元素存在一个偶数。其中第一个偶数为 $F_{2}=2$，第二个偶数为 $F_{5}=8$。

现假设第 $n$ 项为偶数（ $n>5$ ）,则可以通过以下运算得到偶数项的计算公式如下：

$$ {{\begin{aligned}F_{n} &=F_{n-1}+F_{n-2} \\ &=(F_{n-2}+F_{n-3})+(F_{n-3}+F_{n-4}) \\ &=((F_{n-3}+F_{n-4})+F_{n-3})+(F_{n-3}+F_{n-4}) \\ &=3F_{n-3}+2F_{n-4} \\ &=3F_{n-3}+F_{n-4}+F_{n-5}+F_{n-6} \\ &=4F_{n-3}+F_{n-6} \\ \end{aligned}}} $$

取出所有的偶数项构成新的数列 $G$ ，公式如下

$$ G_{n} = \begin{cases} 2 & n=1 \\ 8 & n=2 \\ 4*G_{n-1} + G_{n-2} & n>2 \end{cases} $$

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
std::uint64_t even_fibonacci(std::uint64_t max) {
    std::uint64_t a{ 2 };
    std::uint64_t b{ 8 };
    std::uint64_t c{ 4 * b + a };
    std::uint64_t sum{ 0 };
    if (a < max) sum += a;
    if (b < max) sum += b;
    while (c < max) {
        sum += c;
        a = b;
        b = c;
        c = 4 * b + a;
    }
    return sum;
}