HDUOJ----1250 Hat's Fibonacci
Hat's Fibonacci
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5800 Accepted Submission(s): 1926
Problem Description
A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1. F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4) Your task is to take a number as input, and print that Fibonacci number.
Input
Each line will contain an integers. Process to end of file.
Output
For each case, output the result in a line.
Sample Input
100
Sample Output
4203968145672990846840663646 Note: No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.
Author
戴帽子的
Recommend
Ignatius.L
http://acm.hdu.edu.cn/showproblem.php?pid=1250
大数题，我先是用打表的方法，发现数字到达7037的时候，数字规模才能达到2005 ...然后用7037*2005 ---->已经超过内存，所以这条路实不可取的。。。唯一的方法，只好暴力法，但又担心会超时，可是，喜感就是，竟然过了，还应458ms。。。。哎!！！。
贴下代码：
1 1 #include<stdio.h>
2 2 #include<string.h>
3 3 #define maxn 2006
4 4 int a[maxn],b[maxn],c[maxn],d[maxn],ans[maxn];
5 5 int main()
6 6 {
7 7 int i,j,e,s,up,num;
8 8 while(scanf("%d",&num)!=EOF)
9 9 {
10 10 if(num<=4)
11 11 printf("1");
12 12 else
13 13 {
14 14 memset(a,0,sizeof a);
15 15 memset(b,0,sizeof b);
16 16 memset(c,0,sizeof c);
17 17 memset(d,0,sizeof d);
18 18 memset(ans,0,sizeof ans);
19 19 a[0]=b[0]=c[0]=d[0]=1;
20 20 for(i=4,up=1;i<num;i++)
21 21 {
22 22 for(j=0,e=0;j<=up;j++)
23 23 {
24 24 s=a[j]+b[j]+c[j]+d[j]+e;
25 25 ans[j]=s%10;
26 26 e=(s-ans[j])/10;
27 27 if(s>9&&j==up) up++;
28 28 a[j]=b[j];
29 29 b[j]=c[j];
30 30 c[j]=d[j];
31 31 d[j]=ans[j];
32 32 }
33 33 }
34 34 for(j=maxn;ans[j]==0;j--);
35 35 for(i=j;i>=0;i--)
36 36 {
37 37 printf("%d",ans[i]);
38 38 }
39 39 }
40 40 printf("\n");
41 41 }
42 42 return 0;
43 43 }View Code