我在这里绝对是初学者。我正在用 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)
你的代码不是错，只是太慢了。为了解决欧拉计划问题，不仅你的代码必须正确，而且你的算法必须高效。
您的斐波那契计算非常昂贵 - 也就是说，递归地尝试获得下一个斐波那契数需要 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
这绝对不是唯一的方法，而是另一种方法。
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
你应该使用生成器函数，要点如下：
def fib(max):
a, b = 0, 1
while a < max:
yield a
a,b = b, a+b
现在从shell中调用这个函数，或者在调用fib函数之后编写一个函数，你的问题就会得到解决。我花了7个月才解决这个问题
这可能是最有效的方法。
a, b = 1, 1
total = 0
while a <= 4000000:
if a % 2 == 0:
total += a
a, b = b, a+b
print (total)
使用递归可能适用于较小的数字，但由于您正在测试最多 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);
你也可以尝试这个动态程序，对我来说效果更快
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)
正如其他答案所指出的，您的代码缺乏效率。有时，保持尽可能简单是一个好程序的关键。这对我有用：
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)
希望这有帮助。干杯！
它已经过优化并且可以工作
def fib(n):
a, b = 0, 1
while a < n:
print(a, end=' ')
a, b = b, a+b
print()
fib(10000)
这是基于 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)示例：
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)
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。
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))