Project Euler #2 的 “Python” 解法

Question

我还是个新手，刚开始学习编程。我在用Python尝试解决Project Euler上的问题。能不能帮我指出我的代码哪里出错了？

问题是：斐波那契数列中的每一个新项都是通过把前两个项相加得到的。假设从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

使用递归的方法在处理小数字时可能有效，但因为你要测试的数字范围达到4000000，所以你可能需要把已经找到的值存起来。你可以在已有的答案中找到这种算法。

另一种方法是使用比奈特公式。这个公式可以直接给你第n个斐波那契数。你可以在MathWorld上了解更多信息。

需要注意的是，偶数的斐波那契数在这个序列中每三个元素就会出现一次。你可以使用：

def binet(n):
     """ Gets the nth Fibonacci number using Binet's formula """
     return int((1/sqrt(5))*(pow(((1+sqrt(5))/2),n)-pow(((1-sqrt(5))/2),n)));

s = 0; # this is the sum
i = 3;
while binet(i)<=4000000:
    s += binet(i);
    i += 3; # increment by 3 gives only even-numbered values

print(s);

Answer 2

这可能是最有效的方法。

a, b = 1, 1
total = 0
while a <= 4000000:
    if a % 2 == 0:
        total += a
    a, b = b, a+b  
print (total)

Answer 3

你应该使用生成器函数，简单来说就是这样：

def fib(max):

    a, b = 0, 1

    while a < max:

        yield a

        a,b = b, a+b

现在从命令行调用这个函数，或者在这个函数后面写一个调用fib函数的函数，你的问题就能解决了。我花了7个月才搞定这个问题。

Answer 4

这绝对不是唯一的方法——这只是另一种做法。

def fib(number):
    series = [1,1]
    lastnum = (series[len(series)-1]+series[len(series)-2])
    _sum = 0
    while lastnum < number:
        if lastnum % 2 == 0:
            _sum += lastnum
        series.append(lastnum)
        lastnum = (series[len(series)-1] +series[len(series)-2])
    return series,_sum

Answer 5

你的代码并不是错误，只是运行得太慢了。要解决Project Euler的问题，不仅你的代码要正确，算法也必须高效。

你计算斐波那契数列的方法非常耗时——也就是说，递归地计算下一个斐波那契数需要的时间是O(2^n)，当你想要计算总和达到四百万时，这个时间实在是太长了。

下面是一个在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