偶斐波那契数之和小于X

Question

我正在处理这个问题，看起来我有一个可行的解决方案，但是我很难理解它的行为。

以下是我所拥有的。

#!/usr/bin/python



def even_fib_sums(limit):
    number = 1
    last = 0
    before_last = 0
    total = 0
    for counter in range (0,limit):
     before_last = last
     last = number
     number = before_last + last
     if not number % 2:
        total += number
        yield total

print sum(even_fib_sums(4000000))

我刚开始学编程，但我认为这种方法并不是很有效，因为需要遍历范围内的所有4000000个数字。

如果我使用相同的方法生成斐波那契数列，直到5，结果如下所示。

def generate_fib(limit):
    number = 1
    last = 0
    before_last = 0
    total = 0
    for counter in range (0,limit):
     before_last = last
     last = number
     number = before_last + last
     print number

generate_fib(5)

结果：1、2、3、5、8

在这些结果中，只有2和8 % 2 == 0。 如果使用上面的第一个片段，总和应该是10，但我返回的是12。为什么呢？

- mutantChickenHer0

---

你正在尝试解决哪个欧拉计划问题？问题2要求您找到不超过400万的偶数斐波那契数之和。您的代码似乎在计算连续四百万个斐波那契数，这将涉及大量的计算（以及一些巨大的数字）。 - r3mainer

Answer 1

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

您只需要循环直到遇到大于400000的fib，而不是寻找第四百万个斐波那契数，您可以使用生成器函数和求和简化代码，仅产生偶数并在遇到大于4000000的斐波那契数时退出循环。

def fib(n):
    a, b = 0, 1
    while a <= n:
        a, b = b, a + b
        if not b & 1:
            yield b


print(sum(fib(4000000)))

计算只需要几分之一秒的时间：

In [5]: timeit sum(fib(4000000))

100000 loops, best of 3: 6 µs per loop

尝试使用timeit even_fib_sums(4000000)，几分钟后仍然在运行。

- Padraic Cunningham

---

这真的很有帮助 - 我之前像个僵尸一样处理它。虽然这更有效率，但为了学习目的，我将三个核心要求分成了三个函数。谢谢。 - mutantChickenHer0

@mutantChickenHer0，不用担心，fib函数的逻辑很简单，每个fib数是前两个fib数的和，因此通过保留变量a和b，我们只需要将前一个a加上b即可得到这两个前面的fib数的总和。 - Padraic Cunningham

Answer 2

通过使用for counter in range(0, limit)，您的函数将会有'limit'次迭代。例如，如果您的'limit'变量是10，那么您将不会得到小于10的偶数斐波那契数的总和，但您将得到前10个偶数斐波那契数的总和。

要使您的代码正常工作，您需要用while last < limit替换for counter in range(0, limit)，并且每当您发现last是偶数时，就将其添加到总数中。

- Sidahmed

Answer 3

你可能可以稍微简化一下那个生成函数。以下是我写的方式。

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

这将为您提供一个生成函数，该函数将为您提供小于或等于x的所有斐波那契数（我们应该在此处更加小心，因为无论如何我们都会返回前两个数字）。

然后我们只需要执行：

sum(x for x in fib(4000000) if x%2==0)

- Matthew

Answer 4

你应该将代码更改为仅产生数字，而不是总和，或者将yield更改为return，并删除sum()关键字，如下所示：

def even_fib_sums(limit):
    number = 1
    last = 0
    before_last = 0
    total = 0
    for counter in range (0,limit):
        before_last = last
        last = number
        number = before_last + last
        if not number % 2:
            total += number
    return total

打印 even_fib_sums(5)

- João André Prudêncio da Silva

Answer 5

在第一个代码片段中，您对取整数的总和进行了求和，而不只是产生该数字。如果您期望在输入为5时在第一个片段中获得10，则应以以下任一方式修改代码（这里不试图提高效率，只是修复问题）：

     ...
     number = before_last + last
     if not number % 2:
        yield number

print sum(even_fib_sums(4000000))

或者

     ...
     number = before_last + last
     if not number % 2:
        total += number
  return total

print even_fib_sums(4000000)

- micromoses