002. 偶数斐波那契数(even Fibonacci numbers)

斐波那契序列中的数都是由前两项加总得出,假设第一与第二项为1与2,则前十项分别为:

$$ 1,2,3,5,8,13,21,34,55,89 $$
考虑不超过四百万的斐波那契数,计算其中偶数斐波那契数的和。

分析:此题至少有三种解法:第一种我们可以编写一个计算斐波那契数的函数,然后筛选出不超过四百万的数并对其中的偶数求和;第二种思路是我们可以直接得到一个求偶数的斐波那契数的公式,避免筛选的过程;第三种思路我们可以使用斐波那契数列的通项公式,从而可以不使用循环来求和。这里我同时简单介绍下三种思路。

计算斐波那契数是一个经典的编程问题,可以使用多种方法求解,从最简单的递归函数解法,到迭代计算和动态规划的解法,以至矩阵乘法的解法,当然还可以直接用通项公式求解。以上方法中,递归函数的方法效率最低,通常不会使用。而通项公式的算法由于涉及到无理数,存在浮点计算误差的问题,这里我们也不涉及。至于迭代计算、动态规划和矩阵乘法这三种方法在问题规模较小时运行时间没有太大的差别,所以这里我只介绍迭代计算的方法,其它方法相关的详细资料大家可以上网查询,很容易就可以找到。

首先看第一种思路。我们都知道斐波那契数列的定义,在设定了第一项和第二项后(题目假设这两项分别是一和二),之后每一项都等于其前两项之和,因此我们使用临时变量来保存中间的计算过程,并通过迭代计算得到最后的结果。假设开始时\(a=1,b=2\),则在下一步将\(b\)赋值给\(a\),将\(a+b\)的值赋值给\(b\),如此迭代计算实际上就是斐波那契数列的生成过程。要解决题目中的问题,只需要生成一个足够长的斐波那契数列,筛选其中小于四百万的偶数再加总即可。

第二种思路则是考虑到题目只要求对偶数斐波那契数进行加总,这时候求出所有的斐波那契数显得不太经济,有没有办法只求偶数斐波那契数?观察一下上面的斐波那契数列,我们可以发现第二项是偶数,间隔两个奇数第五项也是偶数,再间隔两项第八项也是偶数。之所以会表现出这样的规律,是因为加法的奇偶性法则导致的。我们知道一个奇数加上一个奇数必定是一个偶数,一个偶数加上一个偶数也是一个偶数,然而一个奇数加上一个偶数则必定是一个奇数。在上面的数列中,第一项是奇数,第二项是偶数,则第三项是奇数,第四项等于第二项加上第三项,也就是一个奇数加上一个偶数,所以第四项也是奇数;第五项等于第三项加第四项,这两项都是奇数,所以第五项必定是偶数。依次类推,第八、十一、十四等等项也是偶数。根据题意我们设\(F_1=1,F_2=2\),则有:

$$ \begin{aligned} F_n&=F_{n-1}+F_{n-2}\\ &=F_{n-2}+F_{n-3}+F_{n-3}+F_{n-4}\\ &=2F_{n-3}+F_{n-2}+F_{n-4}\\ &=2F_{n-3}+(F_{n-3}+F_{n-4})+(F_{n-5}+F_{n-6})\\ &=3F_{n-3}+F_{n-4}+F_{n-5}+F_{n-6}\\ &=4F_{n-3}+F_{n-6} \end{aligned} $$

显然,由我们上面的推理可知,\(F_n,F_{n-3},F_{n-6}\)都为偶数,则我们可以把它们表示成为一个新的数列,称为偶数斐波那契数列,第一项为二,第二项为八,递推公式如下:

$$ EF_n=4EF_{n-1}+EF_{n-2}\quad(EF_1=2,EF_2=8) $$

则我们可以根据这个递推公式,使用上面的迭代计算方法计算所有的偶数斐波那契数,省略一半的计算量。

第三种思路是直接使用斐波那契数列的通项公式计算各项斐波那契数,并筛选其中不超过四百万的偶数并求和。这种方法的好处是其时间复杂度为\(O(1)\),是效率最高的算法。坏处是斐波那契数列的通项公式涉及到无理数,从而会出现浮点计算影响精度的问题,当N越大,这种浮点误差就会越严重。虽然我们可以使用更高精度有浮点数或者专门的外部库来解决这个问题,但无疑引入了更多的复杂度,所以这里我们不再详细介绍这种方法。感兴趣的同学可以参见维基百科

第二种思路的实现代码如下:

def main(N=4e6):
    a,b = 2,8
    arr = [a,b]
    while True:
        a,b = b,4*b+a
        arr.append(b)
        if b > N:
            return sum(arr[:-1])