400万以下的斐波那契[duplicate]

循环条件错误,应该是这样的:

while True:
    Fibonacci1 = Fibonacci1 + Fibonacci2
    if Fibonacci1 % 2 == 0:
        if a + Fibonacci1 > 4000000:
            break
        a = a + Fibonacci1
    Fibonacci2 = Fibonacci1 + Fibonacci2
    if Fibonacci2 % 2 == 0:
        if a + Fibonacci2 > 4000000:
            break
        a = a + Fibonacci2

您的代码有几个问题:

• 你循环了四百万次而不是直到条件成立。
• 循环体中有重复的代码。

大多数人在开始学习Python时只学习命令式编程。这并不奇怪,因为Python是一种命令式语言。但是Python在某种程度上也支持函数式编程,在我看来,函数式编程方法对这类练习更具启发性。

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

为了使用这个生成器,我们可以从itertools导入一些有用的函数。要打印前几个数字,请使用 islice :

from itertools import ifilter, islice, takewhile

for x in islice(fib(), 5):
    print x

1
1
2
3
5

ifilter 生产新发电机:

def is_even(x):
    return x % 2 == 0

evenfibs = ifilter(is_even, fib())

for x in islice(evenfibs, 5):
    print x

2
8
34
144
610

从生成器获取数字,直到一个数字超过四百万 takewhile :

for x in takewhile(lambda x: x < 4000000, evenfibs):
    print x

要解决这个问题,可以使用sum:

sum(list(takewhile(lambda x: x < 4000000, evenfibs)))

我希望这表明函数式编程方法并不困难,而且是解决某些类型问题的更优雅的方法。

你确定是吗 i 你想不到400万?

The On-Line Encyclopedia of Integer Sequences!

您可以按名称或顺序搜索信息。

A014445

因此,编写一个直接产生偶数斐波那契数的生成器是很容易的。

def evenfib():
    """ Generates the even fibonacci numbers """
    a, b = 2, 0
    while True:
        a, b = b, a+4*b
        yield a  

但这不是任务。你必须把所有小于400万的偶数斐波那契数相加。

这里有一个替代方法(非常快,但未经测试)。 它依赖于几个属性:

1. 每个斐波那契数可以直接计算为floor(pow(phi,n)+0.5)(请参阅中的四舍五入计算) http://en.wikipedia.org/wiki/Fibonacci_number ). 相反地,小于i的最大斐波那契数的指数由floor(log(i*sqrt(5))/log(phi))给出
2. 前N个Fibonacci数之和等于第N+2个Fibonacci数减去1(参见同一维基百科页面上的第二个标识)
4. 偶数斐波那契数之和是奇数斐波那契数之和的一半,直到序列中的同一点(这是从3开始的。给出了F(3N)=F(3N-1)+F(3N-2)的性质,从而得到F(3N-2)+F(3N-1)+F(3N)=2f(N)。。然后两边相加。

比它小。

int n = floor(log(4000000*sqrt(5))/log(phi)) = 33. 

33可以被3整除,所以它是一个偶数斐波那契数,如果不是,我们需要这样调整n。

n = (n/3)*3

到目前为止所有斐波那契数的和,如果由

sum = floor( pow( phi, n+2 )/sqrt(5) + 0.5 ) - 1 = 9227464

所有偶数之和是这个数的一半:

sum_even = 4613732

好的一点是,它是一个O(1)(或者O(log(N)),如果你包括pow/log的开销)算法,并且适用于double。。所以我们可以计算非常大的值的和。

还有其他一些技巧使这比简单地计算Fibonacci数的完整列表,然后对列表中的偶数求和更有效。

当然,所有这些都会占用您自己的时间,而不是简单地编写暴力解决方案,但是Project Euler只需要找到漂亮的解决方案,而不是暴力解决方案。最后,如果你学会了一些数学和计算的知识,那么你就有了收获。

## nice simple generator Mark Byers
def fib():
    a = b = 1
    while True:
        yield a
        a, b = b, a + b

## does same as takewhile 5
for fibonacci in zip(range(1,1+5),fib()):
    print "fib(%i) = %i" %  fibonacci

## we can slice to take every second
print "even sequence upto 100th"
total=0
for fibonacci in zip(range(1,1+100),fib())[::2]:
    print "fib(%i) = %i" %  fibonacci
    total+=fibonacci[1] ## to double check
print "Has sum: ", sum( b for a,b in zip(range(1,1+100),fib())[::2] ),'that is ',total

print "odd sequence upto 100th"

total=0
for fibonacci in zip(range(1,1+100),fib())[1::2]:
    print "fib(%i) = %i" %  fibonacci
    total+=fibonacci[1] ## to double check

print "Has sum: ", sum( b for a,b in zip(range(1,1+100),fib())[1::2] ),'that is ',total

算了吧,计算斐波那契数列的最佳方法是使用两个技巧:

对不起,刚才的错误

1:

N =|2 0 0|
   |1 0 0|
   |0 0 0|

M =|3 2 1|
   |2 1 0|
   |0 0 1|

是右上角的元素。

2:

你可以用 http://en.wikipedia.org/wiki/Exponentiation_by_squaring ,因为矩阵乘法是一个环。

所以你可以用O(logn)来解决我们的问题