[Project Euler] 来做欧拉项目练习题吧: 题目002（转）

[Project Euler] 来做欧拉项目练习题吧: 题目002

                                                      周银辉 

来看看第二题吧

问题描述：

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. 

 (先思考，如果有兴趣先编程试试，然后才看下面的内容)  

问题分析：

大家非常熟悉的Fibonacci数列，求最大项小于等于四百万的数列中，所有偶数值的和。

一个很直观的做法是求数列的各项，然后累加偶数项。这是可行的，但不是最优的。

要找到更节省计算机资源的方法，则需要一点点观察能力。

观察 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...

其中的偶数值项构成一个新数列 2 8 34 144 610 ...

从第第3项开始

34  = 4*8  + 2

144 = 4*34 + 8

610 = 4*144+ 34 

哈哈哈，有规律， 所以对于偶数值项构成的新数列通项可以表示为 a(n) = 4*a(n-1) + a(n-2)

所以问题就演变成依此求a(1), a(2)...a(n),其中a(n)小于等于四百万，并在计算的过程中顺便把它们累加一下. 

由于新数列仅仅保护Fibonacci数列的偶数项，那么其运算量将比Fibonacci数列减少一半的运算量 

另外，对于类似于Fibonacci数列的数列a(n)的一些计算，不要使用递归哈，虽然递归比较容易书写，但存在大量重复运算(除非将运算结果缓存起来，但浪费空间）。采用递推，即从首项开始让后依次累加则更简单，可以参考下面的代码。

参考代码：

#include <stdio.h>

int test(int max)

{

if(max<2)

{

return 0;

}

else if(max<8)

{

return 2;

}

int a = 8;      //a(n-1)

int b = 2;      //a(n-2)

int sum = a+b;

int c;          //a(n)

do

{

c = a*4+b;

sum += c;

b = a;

a = c;

}while(c<=max);

sum -= c; //the last c must have exceeded max, remove it.

return sum;

}

int main()

{

int max = 4000000;

printf("%d\n", test(max));

return 0;

}

注：当完成题目后，对于某些题，官方网站会给出参考答案，在我的博客里不会将官方答案贴出来，仅仅会写下我自己当时的思路，除非两者不谋而合。另外，如果你有更好的思路，请留言告诉我，我非常乐意参与到讨论中来。 

分类: Algorithm