Project Euler——Problem 25

daybreakcx posted @ 2009年7月25日 08:39 in Prject Euler , 996 阅读

原题与答案：

Problem 25

30 August 2002

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n-1 + F_n-2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Answer:4782

分析与解答：

这个题目是求斐波那契数列的第几项开始是不小于1000位的，先整体估计一下，由于一个数s的位数为 $\lfloor s \rfloor +1$ ，那么根据斐波那契数列的通项公式 $F_n=\dfrac{({\dfrac{1+\sqrt{5}}{2}})^n-({\dfrac{1-\sqrt{5}}{2}})^n}{\sqrt{5}}$ ，大概估计一下 $\lfloor F_n \rfloor +1$ 的范围，不是很大，在我们可以容忍的范围之内，于是我们可以利用高精度来进行计算，当然我们计算某一项的时候需要的值只有前两项，于是我们可以辗转迭代，最后就能获得结果，具体实现的源代码如下：

#include<stdio.h>
#include<string.h>
int f[2][2000],i,j,t,x;
int main()
{
memset(f,0,sizeof(f));
f[0][0]=f[0][1]=f[1][0]=f[1][1]=1;
for (i=3;;i++)
{
t=0;
x=1-(i&1);
f[x][0]=f[1-x][0];
for (j=1;j<=f[1-x][0];j++)
{
f[x][j]+=t+f[1-x][j];
if (f[x][j]>=10)
{
t=1;
f[x][j]-=10;
}
else t=0;
}
if (t) f[x][++f[x][0]]=1;
if (f[x][0]>=1000) break;
}
printf("%d\n",i);
return 0;
}