1

我正在尝试解决 Project Euler 问题 #2。这是：

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

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

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

但是，当我将以下代码与 4000000 一起使用时，终端窗口会挂起。较小的数字运行正常。这段代码是否真的效率低下，因此滞后？

n = int(raw_input("Enter the start number: "))

def fib_generator():
    a, b = 0, 1
    yield 0
    while True:
        a, b = b, a + b
        yield a

def even_sum(fib_seq):
    seq = []
    seq = [next(fib_seq) for number in range(n)]
    seq = [number for number in seq if number % 2 == 0]
    return sum(seq)

def start():
    fib = fib_generator()
    even_sum = even_sum(fib)
    print even_sum

start()
4

4 回答 4

4

你有一个错误。您正在生成前 4,000,000 个斐波那契数，但问题陈述只要求那些值不超过 4,000,000 的斐波那契数。

由于斐波那契数呈指数增长（F n ~ 1.618 n），因此您生成的数字位数非常多（log 10 F n ~ n / 5），这将花费大量时间。

修复错误，你会没事的。

于 2013-07-25T01:01:12.083 回答
2

您只需要添加逻辑以在下一个斐波那契数超过 4000000 时停止。

此外，我发现这一行存在潜在问题：

def start():
    fib = fib_generator()
    even_sum = even_sum(fib) #<--- right here
    print even_sum

变量名与函数名相同是不好的。

于 2013-07-25T01:04:32.273 回答
0

是的，您的代码中有一些效率低下的地方，您使用两个seq = ...语句将一个很长的列表两次加载到内存中。为什么不尝试一个生成器表达式而不是两个列表推导？此外，您可以更改您的 Fibonacci 生成器以在某个数字处停止：

def fib_generator(n):
    a, b = 0, 1
    while a < n:
        yield a
        a, b = b, a + b

def even_sum(fib_seq):
    seq = (number for number in fib_seq if not number % 2)
    return sum(seq)

def start():
    n = int(raw_input('Enter max constraint: '))
    fib_seq = fib_generator(n)
    even_sum1 = even_sum(fib_seq)
    print even_sum1

start()
于 2013-07-25T05:33:50.017 回答
0

这对我来说跑得很快

lst = []
num1 = 1
num2 = 2
sum = 0
jump = 0
next = 0

while next<4000000:
    next = num1 + num2
    if next<4000000:
        if jump ==0:
            num1 = next
            jump = 1
        else:
            num2 = next
            jump = 0
        if next%2 == 0:
            lst.append(next)

for item in lst:
    sum+=item

print ''
print "Sum: ",
print sum
于 2013-08-07T22:55:29.507 回答