python - 在 Python 中解决 Project Euler #2

Question

我正在尝试解决欧拉计划问题 #2。即:

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.

但是，当我将以下代码与 4000000 一起使用时，终端窗口挂起。较小的数字运行正常。这段代码有什么地方真的很低效，因此很滞后吗？

n = int(raw_input("Enter the start number: "))

def fib_generator():
    a, b = 0, 1
    yield 0
    while True:
        a, b = b, a + b
        yield a

def even_sum(fib_seq):
    seq = []
    seq = [next(fib_seq) for number in range(n)]
    seq = [number for number in seq if number % 2 == 0]
    return sum(seq)

def start():
    fib = fib_generator()
    even_sum = even_sum(fib)
    print even_sum

start()

Answer 1

你有一个错误。您正在生成前 4,000,000 个斐波那契数，但问题陈述仅要求生成值不超过 4,000,000 的那些斐波那契数。

由于斐波那契数呈指数增长 (F_n ~ 1.618ⁿ)，因此您生成的数字的位数非常多 (log₁₀ F_n ~ n/5) 这将花费大量时间。

修复错误，你会没事的。