在Python中解决欧拉计划第二题

Question

我是一名绝对的新手。我在使用Python尝试解决Project Euler中的问题。请问我的代码哪里出了错？

问题描述：斐波那契数列中每个数字都是由前两个数字相加得到的。通过从1和2开始，前10个数字为：

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

考虑斐波那契数列中值不超过400万的项，找出其中偶数项之和。

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)

- Ashtrix

---

那是一种昂贵的创建斐波那契数列的方式。 - alex

你的代码有什么问题？ - Matt Ball

首先，您没有增加r，因此您的代码永远不会退出while循环。其次，使用递归是实现您想要的功能的一种昂贵的方式。 - Rod Xavier

哦，是的！我太蠢了。我会增加r的值。而且，使用比递归更好的东西。非常感谢。@RodXavier - Ashtrix

此外，您计算 fib(r) 两次！将其存储在一个变量中，在同一循环中不要计算两次。 - devnull

Answer 1

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

你的斐波那契计算非常昂贵 - 也就是说，递归地尝试获取下一个斐波那契数列中的数字需要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

- manan

---

非常感谢。我理解了你的意思。我想再试一次。虽然我想坚持使用Python。我会尝试弄清楚你所使用的算法，并生成我的Python代码。 - Ashtrix

实际上，使用cpython在我的笔记本电脑上执行该代码需要9秒钟，在pypy上则只需要1.2秒。这是一种效率低下的算法，但你现在不必担心这个问题。 - placeybordeaux

Answer 2

这绝不是唯一的方式，但另一种做法。

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

- durga

Answer 3

正如其他答案所指出的那样，您的代码缺乏效率。有时候，将其尽可能简单是编写良好程序的关键。以下是对我有效的做法：

    x=0
    y=1
    nextterm=0
    ans=0
    while(nextterm<4000000):
        nextterm=x+y
        x=y
        y=nextterm
        if(nextterm%2==0):
            ans +=nextterm;
    print(ans)

希望这能有所帮助。干杯！

- Anuj Kulkarni

Answer 4

它经过优化并且可以工作

def fib(n):
    a, b = 0, 1
    while a < n:
        print(a, end=' ')
        a, b = b, a+b
    print()
fib(10000)

- jackson jones

Answer 5

如果我们知道需要多少步骤才能达到4000000，那么它就可以工作。大约需要30个步骤。

a=1
b=2
list=[a,b]
for i in range (0,30):
    a,b=b,a+b
    if b%2==0:
        list.append(b)
print(sum(list)-1)

- mesut.a

---

请在您的回答中提供更多细节。目前的写法很难理解您的解决方案。 - Community

Answer 6

将jackson-jones answer进行调整，以找到400万以下的偶数斐波那契项之和。

# create a function to list fibonacci numbers < n value
def fib(n):
    a, b = 1, 2
    while a < n:
        yield a
        a, b = b, a+b

# Using filter(), we extract even values from our fibonacci function
# Then we sum() the even fibonacci values that filter() returns 
print(sum(filter(lambda x: x % 2 == 0, fib(4000000))))

结果为4613732。

- Blake

Answer 7

你也可以尝试这个动态程序，对我来说速度更快

dict = {}
def fib(x):
    if x in dict:
        return dict[x]
    if x==1:
        f = 1
    elif x==2:
        f = 2
    else:
        f = fib(x-1) + fib(x-2)
    dict[x]=f
    return f

i = 1
su = 0
fin = 1

while fin < 4000000:
    fin = fib(i)
    if fin%2 == 0:
        su += fib(i)
    i+=1

print (su)

- user3903149

Answer 8

你应该使用生成器函数，以下是要点：

def fib(max):

    a, b = 0, 1

    while a < max:

        yield a

        a,b = b, a+b

现在从 shell 调用这个函数，或者在这个调用之后编写一个函数调用 fib 函数，你的问题就会得到解决。我花了7个月时间解决这个问题。

- vamosrafa

---

你仍然需要在 yield a 上面添加 if not a % 2: 来去除非偶数。但是，如果不比 @the_prole 的解决方案稍微慢一些的话，这似乎是一个不错的解决方案。 - JDG

Answer 9

这可能是最有效的方法。

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

- the_prole

---

一种稍微更加高效的实现方法是利用每个第三个斐波那契数都是偶数这一特性进行循环展开并消除if语句。更加高效的方法是找到偶数元素之和的递归公式以及其解0.5*(F[(n//3)*3+2]-1)，（约定F[0]=0，F[1]=1），然后使用倍增算法计算此公式中的单个斐波那契数。 - Lutz Lehmann

Answer 10

使用递归可能适用于较小的数字，但由于您要测试每个案例直到4000000，因此您可能希望将已经找到的值存储到values中。您可以在现有答案中寻找此算法。

另一种方法是使用Binet公式。该公式将始终返回第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);

- iptq

---

我不知道为什么，但在我的电脑上进行10^5次迭代时，这要比其他方法慢十倍。并且我在timeit之外导入了所有东西。 - JDG