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

时间:2023-02-03 19:03:47

                                [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;
}

 

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