HDOJ---1568 Fibonacci[式は前の4桁を求めます]

Fibonacci
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2113    Accepted Submission(s): 979
Problem Description
2007年が来ました.2006年1年間の修練を経て、数学の神童zouyuはついに0から1000000のFibonacciを数列に並べた.
(f[0]=0,f[1]=1;f[i]=f[i]+f[i-2](i>=2))の値はすべて暗記された.
次に、CodeStarは彼を試験することにしたので、彼に数字を聞くたびに、彼は答えを言わなければなりませんが、ある数字は長すぎます.だから4位を超えたのは上位4位を言えばいいのに、CodeStar自身は覚えていない.そこで彼はzouyuの言うことが正しいかどうかをテストするためにプログラムを書くことにした.
 
 
Input
数n(0<=n<=10000000)の数を入力し、1行ずつ入力します.ファイルの最後まで読みます.
 
 
Output
f[n]の最初の4つの数字を出力します(4つ未満の数字であれば、すべて出力します).
 
 
Sample Input
0 1 2 3 4 5 35 36 37 38 39 40
 
 
Sample Output
0 1 1 2 3 5 9227 1493 2415 3908 6324 1023
 
 
Author
daringQQ
 
 
Source
Happy 2007
 
 
Recommend
8600
 
 
 
 
 
標準のFibonacci数列F(0)＝0,F(1)＝1,F(n)＝F(n−1)＋F(n−2).一般式はF(n)=((1+Sqrt(5)/2)^n−(1−Sqrt(5)/2)^n)*1/Sqrt(5)であり、(1−sqrt(5))/2の絶対値が1未満であるため、iが大きい場合、このF(n)≒((1+Sqrt(5)/2)^n/sqrt(5)は無視されることが多い.だからFibonacciの前の30項は直接求めることができます.後ろの大きい数はlog 10を取って、整頓した後に左の4位を求めて、方法とHDOJ 1060はhttp://hi.baidu.com/racebug/blog/item/e3b5cdefeb485af2b2fb9537.htmlに類似します
これはFibonacciについてよく紹介した論文http://blog.163.com/baobao_zhang@126/blog/static/482523672008826103832368/です.
変換元:
http://hi.baidu.com/racebug/blog/item/54ad34ed3c3dfc3426979191.html
code :

 1 #include<iostream>

 2 #include<cmath>

 3 using namespace std;

 4 int main()

 5 {

 6     int n;

 7     int i;

 8     int f[31];

 9     double temp1=log10((1.0+sqrt(5.0))/2.0),temp2=log10(sqrt(5.0));

10     f[0]=0;

11     f[1]=1;

12     for(i=2;i<31;i++)

13         f[i]=f[i-1]+f[i-2];

14     while(~scanf("%d",&n))

15     {

16         if(n<31)

17         {

18             int temp=f[n];

19             while(temp>=10000)

20                 temp/=10;

21             printf("%d
",temp);

22         }

23         else

24         {

25             double t;

26             int ans;

27             t=(n*temp1-temp2);

28             t-=(int)t;

29             ans=pow(10.0,t)*1000.0;

30             printf("%d
",ans);

31         }

32     }

33     return 0;

34 }