“Python”中的欧拉项目#2

问题描述 投票:0回答:12

我在这里绝对是初学者。我正在用 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)
amazon-web-services python fibonacci
12个回答
6
投票

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

您的斐波那契计算非常昂贵 - 也就是说,递归地尝试获得下一个斐波那契数需要 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

1
投票

这绝对不是唯一的方法,而是另一种方法。

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

0
投票

你应该使用生成器函数,要点如下:

def fib(max):

    a, b = 0, 1

    while a < max:

        yield a

        a,b = b, a+b

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


0
投票

这可能是最有效的方法。

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

0
投票

使用递归可能适用于较小的数字,但由于您正在测试最多 4000000 个案例,因此您可能希望将已经找到的值存储到 value 中。您可以在现有答案中查找该算法。

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

0
投票

你也可以尝试这个动态程序,对我来说效果更快

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)

0
投票

正如其他答案所指出的,您的代码缺乏效率。有时,保持尽可能简单是一个好程序的关键。这对我有用:

    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)

希望这有帮助。干杯!


0
投票

它已经过优化并且可以工作

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

0
投票

这是基于 Lutz Lehmann 对此答案的评论的稍微更有效的算法(也适用于已接受的答案):

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 * 第四个偶数) + 第三个偶数

0
投票
如果我们知道需要多少步才能达到 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)
    

0
投票
调整

jackson-jones 答案,找到低于 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。


0
投票
这是我的简单输出

list = [] even_list = [] a = 0 b = 1 while a+b < 4000000: c = a+b print(c, end = ' ') list.append(c) b = a a = c for i in range(0,33): if list[i]%2 == 0 and list[i]//2 != 0 : even_list.append(list[i]) print('Fibanocci Series',list) print('Even Numbers', even_list) print('Sum of even fibannoci', sum(even_list))

© www.soinside.com 2019 - 2024. All rights reserved.