计算斐波拉切数列中偶数数列的和

斐波拉切数列的定义为：起始元素为1和2，从第三个元素开始每一个元素为前两个元素的和，比如前10个斐波拉切元素为 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...。现在我们需要你计算区间[1, 4000, 000]之间的所有偶数斐波拉切元素的和。

这个数列看上去很简单，那么我们就按照最普通的方法计算一下。

#coding=utf-8
from datetime import datetime
LIMIT = 4000000
t_start = datetime.now()
elem1 = 1
elem2 = 2
sum = elem2
elem3 = elem1 + elem2
while elem3 <= LIMIT:
    if elem3 % 2 == 0:
        sum += elem3
    elem1 = elem2
    elem2 = elem3
    elem3 = elem1 + elem2
t_end = datetime.now()
time_delta = t_end - t_start
#计算程序运行时间
last_seconds = time_delta.seconds + (time_delta.microseconds) / 100000.0
print(sum)
print(last_seconds)

可以很快地得到结果不是吗？而且运行速度也很快。i

但是如果我们就这样把这个问题解决了，很明显没有发现斐波拉切数列的有趣之处。

对于这个题目来讲，我们是从1和2开始作为斐波拉切数列的起始元素的并且依次遍历所有的元素并判断奇数偶数的。但是考虑到问题的本身是对斐波拉切数列中所有偶数元素求和，那么我们再仔细观察一下这些元素，看看还有什么规律可以利用的。来认真看一下。

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
仔细看那些偶数元素所在的位置，2位置是2，8位置是5，34位置是8，144位置是11，看出来了么，这些偶数元素的所在位置呈一种等差数列排布啊！这个就等于是从1和2开始，连续获取三次斐波拉切元素就是一个偶数，比如 1+2得到3，2+3得到5，3+5得到8，8 就是一个偶数。那么这样的话，改进一下代码：

#coding=utf-8
from datetime import datetime
def get_next_even_number(e1, e2):
    #第一次计算
    e3 = e1 + e2
    #第二次计算
    e1 = e2
    e2 = e3
    e3 = e1 + e2
    #第三次计算
    e1 = e2
    e2 = e3
    e3 = e1 + e2
    e1 = e2
    e2 = e3
    return e3, e1, e2
LIMIT = 4000000
t_start = datetime.now()
elem1 = 1
elem2 = 2
sum = elem2
#起始元素所在位置
pos = 2
e_next_even, elem1, elem2 = get_next_even_number(elem1, elem2)
while e_next_even <= LIMIT:
    sum += e_next_even
    e_next_even, elem1, elem2 = get_next_even_number(elem1, elem2)
t_end = datetime.now()
time_delta = t_end - t_start
#计算程序运行时间
last_seconds = time_delta.seconds + (time_delta.microseconds) / 100000.0
print(sum)
print(last_seconds)

当然了还有其他的一些方法，大家可以自己探索，欢迎将你的探索结果公布出来，大家一定会赞赏不已。

相关扩展阅读

1. 维基百科 斐波拉切数列
2. 网易公开课 斐波那契数列与黄金分割