400万以下偶数斐波那契数之和 - Python

Question

我正在用Python尝试做Project Euler的第二个问题，想弄明白为什么我的代码不管用。

这段代码是用来计算小于400万的偶数斐波那契数的总和。

counter = 2
total = 0
while counter <= 4000000:
    if counter % 2 == 0:
        total+= counter    
    counter+= (counter -1)
print total

这段代码的输出结果是：2

如果我打印计数器，它的输出是：4194305

我猜可能是if语句出了问题，因为while循环运行得很好，计数器也在正确地增加。

Answer 1

其实有更简单的方法可以做到这一点（比如freakish的解决方案），不过这个版本的代码很清晰，做的事情也很明确 :-)

from itertools import takewhile

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


def even(it):
    for n in it:
        if n % 2 == 0:
            yield n


print sum(takewhile(lambda f: f <= 4000000, even(fibonacci())))

Answer 2

这是我用异或门写的Python解决方案。我先初始化了前两个数，然后在每次循环中，我会保存前两个数的状态。理论上，只有当两个数都是奇数或者都是偶数时，它们的和才会是偶数。

a = 1
b = 2

a_state = 1 #odd = 1 
b_state = 0 #even = 0

sum = b
output = []
while (a+b) < 1000:
    c = a+b
    a = b
    b = c
    
    if (a_state ^ b_state) == 0:
        sum += c
        a_state = b_state
        b_state = 0
    else:
        a_state = b_state
        b_state = 1
print(sum)

Answer 3

如果你仔细观察，你会看到以下的数字序列：

1 1 2 3 5 8 13 21 34 55 89 144 ...

这个序列叫做斐波那契数列，它的计算公式是：

而你只想要其中偶数的和，比如：

1 1 2 3 5 8 13 21 34 55 89 144 ...

所以你可以用一个新的公式来计算：

这样你就会得到以下的序列：

2 8 34 144 ...

下面是一个代码示例（使用Go语言）：

package main

import "fmt"

func fibonacci() func() int {
    first, second := 0, 2
    return func() int {
        ret := first
        first, second = second, first+(4*second)
        return ret
    }
}

func main() {
    sum := 0
    f := fibonacci()
    for i := 0; sum < 4000000; i++ {
        sum += f()
    }
    fmt.Println(sum)
}

在这种情况下，你就不需要使用if条件判断了。

希望这对你有帮助！祝好！

Answer 4

你的代码计算的 counter 序列是这样的：

2 # solid start
3 # good
5 # this is going great
9 # wait, what?
17 # this is going really badly

你不能每次只加 counter - 1，你需要加上 序列中的前一个数字。

那么，为什么你的 total 会这么小呢？因为奇数减去一总是偶数，而奇数加上偶数总是奇数；所以你生成的唯一偶数就是 2，这就是你的 total。

生成斐波那契数通常用两个变量 a 和 b，我们从这里开始：

a = b = 1

每次循环看起来像这样：

a, b = b, a + b

Answer 5

问题出在这一行 counter+= (counter -1)。你把它自己（减去1）加到自己身上了，其实你应该这样做：

a, b = 1, 1
total = 0
while a <= 4000000:
    if a % 2 == 0:
        total += a
    a, b = b, a+b  # the real formula for Fibonacci sequence
print total