hdu_hpu第八次周赛_1002 大菲波数

hdu_hpu第八次周赛_1002 大菲波数_201310270958

大菲波数

Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 95 Accepted Submission(s) : 39

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Fibonacci数列，定义如下： f(1)=f(2)=1 f(n)=f(n-1)+f(n-2) n>=3。计算第n项Fibonacci数值。

Input

输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。

Output

输出为N行，每行为对应的f(Pi)。

Sample Input

Sample Output

Source

2007省赛集训队练习赛（2）

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 char s[1010][500];
 5 int an1[500],an2[500],an3[500];
 6 
 7 int main()
 8 {
 9     int i,j,k,t,N,len,aa;
10     memset(s,0,sizeof(s));
11     memset(an1,0,sizeof(an1));
12     memset(an2,0,sizeof(an2));
13     memset(an3,0,sizeof(an3));
14     an1[0]=1;
15     an2[0]=1;
16     an3[0]=1;
17     len=0;t=0;
18     strcpy(s[1],"1");strcpy(s[2],"1");
19     for(j=3;j<=1000;j++)
20     {
21         for(i=0;i<=len;i++)
22         {
23             an3[i]=an1[i]+an2[i]+t;
24             if(an3[i]>=10)
25             {
26                 an3[i]-=10;
27                 t=1;
28             }
29             else
30             t=0;
31             if(i==len&&t==1)
32             len+=1;
33             an1[i]=an2[i];
34             an2[i]=an3[i];
35         }
36         //for(aa=99;(aa >= 0)&&(an3[aa] == 0);aa--);
37         for(k=0,aa=i-1;aa >= 0;aa--){
38         s[j][k++]=an3[aa]+'0';
39         //printf("%d",an3[aa]);
40     }
41     //printf("
");
42     }
43     scanf("%d",&N);
44     while(N--)
45     {
46         int pi;
47         scanf("%d",&pi);
48         printf("%s
",s[pi]);
49     }
50     return 0;
51 }

//在网上找的比较简洁的做法

//大数运算！！ 
 #include"stdio.h" 
 #include"string.h" 
 int a[1001][1001]; 
 int main() 
 { 
     int i,j,k; 
     int n,t; 
     int carry; 
     scanf("%d",&t); 
     while(t--) 
     { 
         scanf("%d",&n); 
         memset(a,0,sizeof(a)); 
         a[1][1]=1;a[2][1]=1; 
         for(i=3,k=1;i<=n;i++) 
         { 
             for(j=1,carry=0;j<=k;j++) 
             { 
                 a[i][j]=a[i-1][j]+a[i-2][j]+carry;; 
                 carry=a[i][j]/10; 
                 a[i][j]%=10; 
             } 
             while(carry)//这里容易忽略！！ 
             { 
                 a[i][++k]=carry; 
                 carry/=10; 
             } 
         } 
         for(i=k;i>0;i--) 
             printf("%d",a[n][i]); 
         printf("
"); 
     } 
     return 0; 
 }