欧拉项目【ProjectEuler】系列-第二题
----人既无名
Problem2：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.
意思是，对于斐波拉切数列，求出不超过4000000的所有值为偶数的项的和。
首先我想介绍一些斐波拉切数列的一些基本介绍,因为斐波拉切数列是一个非常奇特的数列.
如果定义第一项F（0）=0，第二项F（1）=1，以后每一项都是前两项的和。
F(n+2)=F(n) + F(n+1), 其中n=0,1,2,3,...
斐波拉切数列的一些基本特性：
1. F(0)+F(1)+F(2)+...+F(n)=F(n+2)-1
2.F(1)+F(3)+F(5)+...+F(2n-1)=F(2n)
3.F(0)+F(2)+F(4)+...+F(2n)=F(2n+1)-1
4.F(m+n-1)=F(m-1)F(n-1)+F(m)F(n)（利用该项可以构造复杂度为O(logn)的程序）
5.F(n)^2=F(n+1)F(n-1)+(-1)^(n-1)（斐波那契数列中任一项的平方数都等于跟它相邻的前后两项的乘积加1或减1）
6.F(n+2)F(n-1)-F(n+1)F(n)=1(相邻的四个斐波那契数，中间两数之积（内积）与两边两数之积（外积）相差1)
此外，斐波那契数列的通项公式为
Fn 看似是无理数，但当 n ≧0 時，Fn 都是整数
利用斐波那契数列來做出一個新的数列：
方法是把数列中相邻的数字相除，以组成新的数列如下：
0/1,1/1,1/2,2/3,...,F(n)/F(n-1)
當 n 無限大時，數列的極限是：
這個數值稱為黃金分割比，它正好是方程式 x^2+x-1=0 的一個根.
分析1：
其实不用了解太多也可以把这个题目解出来，但是了解一下这个奇特的数列还是很有趣的。现在我们开始对题目进行分析，首先要说的是题目说的是求出所有值为偶数的项（F(n)<4000000）的和.也就是要求F(n)%2==0,而不是F(2n)。
因此最简单的办法是遍历小于4000000 的所有项，是偶数的时候就加起来
int Fuc1()
{
int a=1;
int b=2;
int c=2;
int sum=0;
for(;c<400000000;)
{
if(c%2==0)
sum+=c;
c=a+b;
a=b;
b=c;
}
return sum;
}
分析2：
在论坛中看到还有这样一种思路，因为
Fn/Fn-1 → Φ （Φ为黄金分割比）
Fn/Fn-2 = (Fn/Fn-1)/(Fn-2/Fn-1) → Φ/(1/Φ) = Φ2
Fn/Fn-3 = (Fn/Fn-2)/(Fn-3/Fn-2) → Φ2/(1/Φ) = Φ3
Φ3=4.236068，因为不需要完全的精确，因此可以用这种方法来解决这个问题。这个思路真的很不错，因为它简化了我们的操作步骤，可以加快运算的速度。
int Fuc2()
{
int sum=0;
for(int i=2;i<400000000;i=i*4.236068)
{
sum+=i;
}
return sum;
}
看到如此简单的运算我自己也震惊了，虽然运算的结果与实际的正确结果并不完全一致，但是步骤是如此的简单。不得不感叹别人的想法就是比我聪明啊。
还有一种思路是这样的，因为斐波拉切数列特点(x=y=1)
1,1, 2, 3, 5, 8,....
x,y,x+y,x+2y,2x+3y,3x+5y,...
则
int Fuc3()
{
int x=1;
int y=1;
int sum=0;
int r;
while (sum < 4000000)
{
sum += (x + y);
r=x;
x= r + 2*y;
y=2*r + 3*y;
}
return sum;
}
最后
对于本题数列的起始是1 ，2 。
1
2 3 5 8 13 21
34 55 89 144，...
这些偶数组成一个新的数列
2,8，34,144，...
根据递推公式
F(n)=F(n-1)+F(n-2)=2F(n-2)+F(n-3)
=2F(n-2)+F(n-3)=3F(n-3)+2F(n-4)
=3F(n-3)+F(n-4)+F(n-5)+F(n-6)
=4F(n-3)+F(n-6);
这是个高中的递推公式啊！！！
int Fuc4()
{//Fn=4*F(n-3)+F(n-6)
int sum=0;
int fn;
int fn_3=8;
int fn_6=2;
while(fn_6<4000000)
{
sum+=fn_6;
fn=4*fn_3+fn_6;
fn_6=fn_3;
fn_3=fn;
}
return sum;
}