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

Question

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

amazon-web-servicespythonfibonacci

5

我是一名绝对的新手。我在使用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

1

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

2

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

1

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

1

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

1

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

显示剩余5条评论

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Saurabh · Answer 1

这是基于Lutz Lehmann对this answer的评论而稍微更高效的算法（也适用于被接受的答案）：

def even_fibonacci_sum(cutoff=4e6):
    first_even, second_even = 2, 8
    even_sum = first_even + second_even
    while even_sum < cutoff:
        even_fib = ((4 * second_even) + first_even)
        even_sum += even_fib
        first_even, second_even = second_even, even_fib
    return even_sum

考虑以下斐波那契数列：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

斐波那契数列中每隔三个元素就是偶数。

因此，上述序列中的偶数为2、8、34、144、610等。

对于偶数n，下面的方程式成立：

n = 4 * (n-1) + (n-2)

例如：

34 = (4 * 8) + 2，即第三个偶数=（4 * 第二个偶数）+ 第一个偶数
144 = (4 * 34) + 8，即第四个偶数=（4 * 第三个偶数）+ 第二个偶数
610 = (4 * 144) + 34，即第五个偶数=（4 * 第四个偶数）+ 第三个偶数