我正在尝试使用Python解决以下问题:
斐波那契序列中的每个新项都是通过将前两项相加而生成的。从1和2开始,前10项将是:1、2、3、5、8、13、21、34、55、89
通过考虑Fibonacci序列中值不超过400万的项,找到偶数值项的和
到目前为止,我已经能够生成斐波那契元素,但在尝试求和偶数元素时,我的代码似乎停滞不前。下面是代码:
def fib(n):
if n==0:
return 0
elif n==1:
return 1
if n>1:
return fib(n-1)+fib(n-2)
n=0
total=0
while fib(n)<=4000000:
if fib(n)%2==0:
total+=fib(n)
print(total)
欢迎提出任何建议。
您有一个无限循环,因为n
在while
循环中从未从零递增。此外,为什么不求和你的斐波那契总数以及在同一个while
循环中找到下一个斐波那奇值,如下所示:
x= 1
y=1
total = 0
while x <= 4000000:
if x % 2 == 0:
total += x
x, y = y, x + y
print (total)
输出:
4613732
由于这看起来像是一项家庭作业,我加入了一些有趣的Python
from math import sqrt
# Using Binet's formula
def fib(n):
return int(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5)))
def sum_even_terms(limit = 4000000):
n = total = 0
while True:
term = fib(n)
n += 1
if term > limit: break
if term % 2 == 0:
total += term
return total
print sum_even_terms()
def is_nth_term_even(n):
return (fib(n) % 2 == 0)
print is_nth_term_even(30)
为了好玩,这里有一个非常简短的解决方案:
def fib_even_sum(limit=4*10**6):
"""Sum of the even Fibonacci numbers up to the given limit."""
b, c = 1, 2
while c <= limit:
a = b + c; b = c + a; c = a + b
return b // 2
print fib_even_sum() # outputs 4613732
它基于以下事实:
每三个斐波那契数是偶数。
如果
Fib(n)
是偶数,则直到Fib(n)
的偶数斐波那契数之和等于直到Fib(n)
的奇费波那契号之和(因为每个偶数费波那契号都是前面两个奇费波那奇号之和)。直到并包括
Fib(n)
的所有斐波那契数(偶数和奇数)的和是Fib(n+2) - 1
(通过简单的归纳证明)。
因此,如果Fib(n)
是最后一个包含在和中的偶数,那么你想要的总数只是CCD_ 10。
您也可以使用生成器并添加数字
def fib():
a, b = 0, 1
while 1:
yield a
a, b = b, a + b
f = fib()
total = 0
while total <= 4000000:
current = f.next()
if current % 2 == 0:
total += current
print total