本文共 1507 字，大约阅读时间需要 5 分钟。

原文地址：

Input  : n  = 3Output : 34Input  : n  = 4Output : 144Input : n = 7Output : 10946

下面的数字序列就是斐波那契数列：

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

对于序列中任意一个数字有：

Fn = Fn-1 + Fn-2       with seed values      F0 = 0 and F1 = 1.

偶数的斐波那契数列是：0, 2, 8, 34, 144, 610, 2584….，我们要找的是这个序列的第n个数字。

如果我们再仔细看下这个斐波那契数列，我们就可以注意到在这个序列中每隔三个数字就出现一个偶数，而且偶数的序列可以用下面的递归式子表示。

偶斐波那契数列的递归描述为:     EFn = 4EFn-1 + EFn-2with seed values     EF0 = 0 and EF1 = 2.EFn表示偶斐波那契数列的第n个项。

上面的式子是如何工作的呢？

我们先看下原来的斐波那契公式，用这样的方法写写Fn-3与Fn-6，因为事实上每三个斐波那契数就出现一个偶数。

Fn = Fn-1 + Fn-2 [Expanding both terms]   = Fn-2 + Fn-3 + Fn-3 + Fn-4    = Fn-2 + 2Fn-3 + Fn-4 [Expending first term]   = Fn-3 + Fn-4 + 2Fn-3 + Fn-4   = 3Fn-3 + 2Fn-4  [Expending one Fn-4]   = 3Fn-3 + Fn-4 + Fn-5 + Fn-6 [Combing Fn-4 and Fn-5]   = 4Fn-3 + Fn-6  因为每隔三个斐波那契数就出现一个偶数, 所以如果Fn是偶数，那么Fn-3就是偶数，Fn-6也是偶数。假设Fn是第x个偶数，并将其标记为EFx。如果Fn是EFx，那么Fn-3就是前一个偶数。例如EFx-1与Fn-6是EFx-1前面的元素。例如EFx-2所以Fn = 4Fn-3 + Fn-6也就是说EFx = 4EFx-1 + EFx-2

下面是上述递归公式的C++实现。

// Even Fibonacci Series using normal Recursion#include
   
    using namespace std;/* Function which return nth even fibonnaci number */long int evenFib(int n){    if (n < 1)       return n;    if (n == 1)        return 2;    // calculation of Fn = 4*(Fn-1) + Fn-2    return ((4*evenFib(n-1)) + evenFib(n-2));  }/* Driver program */int main (){    int n = 7;    cout << evenFib(n);      return 0;}
   

输出：

10946

上述实现的时间复杂度是指数级的。我们可以用动态规划在线性的时间内解决这个问题，我们也可以用EFn = F3n在O(Log n)的时间内得到答案。注意我们可以在O(Log n)的时间内找到第n个斐波那契数。请看

转载地址：http://jzhii.baihongyu.com/