斐波那契数低于 400 万

Question

可能的重复：
用于查找斐波那契数列的 Python 程序。更多 Pythonic 方式。

嘿，我正在尝试编写一个脚本，将“斐波那契数列”中的所有偶数项求和到 400 万以下。

Fibonacci1 = 1
Fibonacci2 = 2
a = 2
i = 4
for i in range(1,4000000):
 Fibonacci1 = Fibonacci1 + Fibonacci2
 if Fibonacci1 % 2 == 0:
  a = a + Fibonacci1
 Fibonacci2 = Fibonacci1 + Fibonacci2
 if Fibonacci2 % 2 == 0:
  a = a + Fibonacci2
print a
raw_input()

本来应该不到一分钟的时间，但是花了一整晚都没有解决！

---

编辑：对不起，我误解了这个问题。我认为这意味着我必须将所有偶数项相加至 400 万！但解决方案是将所有偶数项相加，直到 400 万。

工作代码（不到一秒完成）：

Fibonacci1 = 1
Fibonacci2 = 2
a = 2
while a < 4000000:
 Fibonacci1 = Fibonacci1 + Fibonacci2
 if Fibonacci1 % 2 == 0:
  a = a + Fibonacci1
 Fibonacci2 = Fibonacci1 + Fibonacci2
 if Fibonacci2 % 2 == 0:
  a = a + Fibonacci2
print a
raw_input()

Answer 1

您的代码存在一些问题：

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

大多数人在开始学习 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)))

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

Answer 2

你确定你要的是i小于400万吗？

Answer 3

您可能有兴趣了解整数序列在线百科全书！

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

如果您搜索 0,2,8,34 或“偶数斐波那契”，您将被重定向到序列 A014445

在那里你可以找到很多信息，包括公式，
由此编写一个直接生成偶数斐波那契数的生成器很容易。

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

Answer 4

循环条件不对，应该是这样的：

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

Answer 5

目前，您对所有前 200 万个偶数斐波那契数求和。

但这不是任务。您必须将所有低于 400 万的偶数斐波那契数相加。

Answer 6

注意：这已被大量修改以解决实际问题

这是一种替代方法（非常快，但未经测试的方法）。
它依赖于一些属性：

1. 每个斐波那契数都可以直接计算为 Floor( pow( phi, n ) + 0.5 ) （请参阅 http://en.wikipedia.org/wiki/Fibonacci_number ）。相反，小于 i 的最大斐波那契数的索引由下式给出： Floor( log(i*sqrt(5)) / log(phi) )
2. 前 N 个斐波那契数之和为第 N+2 个斐波那契数减 1（参见同一维基百科页面上的第二恒等式）
3. 偶数斐波那契数是每三个数字。 （看看序列 mod 2，结果是微不足道的）
4. 偶数斐波那契数之和是奇数斐波那契数之和的一半，直到序列中的同一点。 （这是从 3 得出的，并且具有 F(3N) = F(3N-1) + F(3N-2) 的性质，因此 F(3N-2) + F(3N-1) + F(3N) = 2 F (N) ..然后将两边相加，

因此转换我们的最大值 4000000 计算最高斐波那契数的索引。
小于它。

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) 算法，并且适用于双打..因此我们可以计算非常大的值的总和。

Answer 7

我不太明白你的算法，但似乎smerriman有一个观点，4000000个斐波那契数列肯定会增长到4M以上。我想更快的方法是生成高达 4M 的序列，然后将偶数相加。

Answer 8

还有其他技巧可以使这一过程比简单地计算斐波那契数列的完整列表，然后对列表中的偶数求和更有效。

如果是我试图解决这个问题，我会列出偶数斐波那契数列。该列表有什么有趣的特征吗？你能说服自己这种模式总体上是正确的吗？

接下来，我可能会寻找一种方法来计算该列表的成员，并且仅计算那些需要的元素。我什至可能会看看是否有任何公式可以得出斐波那契数列的总和。

当然，所有这些都会占用您更多的时间，而不是简单地编写暴力解决方案，但欧拉项目就是为了找到漂亮的解决方案而不是暴力解决方案。最后，如果你学到了一些关于数学、关于计算的知识，那么你就已经有所收获。

Answer 9

## 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

Answer 10

来吧，计算斐波那契数列的最佳方法是使用 2 个技巧：

已编辑，对之前的错误表示歉意

1：

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

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

矩阵 N*M^(n/3) 具有前 n 个斐波那契数的总和 （仅过滤到偶数） 是右上元素。

2：

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

所以你可以在 O(log n) 内解决我们的问题