Project Euler——Problem 25 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 24
Project Euler——Problem 26

Project Euler——Problem 25

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

原题与答案:

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) = 1 and F_(2) = 1.

Hence the first 12 terms will be:

F_(1) = 1
F_(2) = 1
F_(3) = 2
F_(4) = 3
F_(5) = 5
F_(6) = 8
F_(7) = 13
F_(8) = 21
F_(9) = 34
F_(10) = 55
F_(11) = 89
F_(12) = 144

The 12th term, F_(12), 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的范围,不是很大,在我们可以容忍的范围之内,于是我们可以利用高精度来进行计算,当然我们计算某一项的时候需要的值只有前两项,于是我们可以辗转迭代,最后就能获得结果,具体实现的源代码如下:

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int f[2][2000],i,j,t,x;
  4. int main()
  5. {
  6.         memset(f,0,sizeof(f));
  7.         f[0][0]=f[0][1]=f[1][0]=f[1][1]=1;
  8.         for (i=3;;i++)
  9.         {
  10.                 t=0;
  11.                 x=1-(i&1);
  12.                 f[x][0]=f[1-x][0];
  13.                 for (j=1;j<=f[1-x][0];j++)
  14.                 {
  15.                         f[x][j]+=t+f[1-x][j];
  16.                         if (f[x][j]>=10)
  17.                         {
  18.                                 t=1;
  19.                                 f[x][j]-=10;
  20.                         }
  21.                         else t=0;
  22.                 }
  23.                 if (t) f[x][++f[x][0]]=1;
  24.                 if (f[x][0]>=1000) break;
  25.         }
  26.         printf("%d\n",i);
  27.         return 0;
  28. }

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter