“Python”中的欧拉计划＃2

Question

我在这里绝对是初学者。我正在用 Python 尝试回答有关 Project Euler 的问题。你能指出我的代码哪里出了问题吗？

Q) 斐波那契数列中的每一项新项都是通过添加前两项而生成的。从 1 和 2 开始，前 10 项将是：

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

通过考虑斐波那契数列中值不超过四百万的项，求偶数项的总和。

def fib(a):
    if ((a==0) or (a==1)):
        return 1
    else:
        return((fib(a-1))+(fib(a-2)))
    r=0
    sum=0
    while (fib(r))<4000000:
        if(((fib(r))%2)==0):
            sum+=fib(r)
            print(sum)

Answer 1

你的代码没有错，只是太慢了。为了解决欧拉计划问题，不仅你的代码必须正确，而且你的算法必须高效。

您的斐波那契计算非常昂贵 - 也就是说，递归地尝试获得下一个斐波那契数需要 O(2^n) 时间运行 - 当您想要对限制为 400 万的数字求和时，时间太长了。

Python 中更高效的实现如下：

x = 1
y = 1
z = 0
result = 0

while z < 4000000:
   z = (x+y)         
   if z%2 == 0:
       result = result + z

   #next iteration

   x = y
   y = z

print result