Project Euler 2

题目

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, \dots\]

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

解决方案

直接依照递推式\(F(i)=F(i-1)+F(i-2)\)进行递推即可，时间复杂度为对数级别。

代码

N = 4 * 10 ** 6
a, b = 1, 2
ans = 0
while True:
    if a > N:
        break
    if a % 2 == 0:
        ans += a
    c = a + b
    a, b = b, c
print(ans)