6L

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

1
1
2
3
5

// 第1000个Fibonacci数约为4.3*10^208
// 复习一下__intx：https://www.cnblogs.com/goldenretriever/p/10356654.html

// double可以表示十进制的15或16位有效数字，可完全保证15位，
// 负值取值范围为 -1.7976E+308 到 -4.94065645841246544E-324，
// 正值取值范围为 4.94065645841246544E-324 到 1.797693E+308

 1 #include<stdio.h>
 2 double f[1000]={1,1};
 3 void table()
 4 {
 5     for(int i=2;i<1000;i++)
 6         f[i]=f[i-1]+f[i-2];
 7 }
 8 int main()
 9 {
10     int n, pi;
11     table();
12     scanf("%d", &n);
13     while(n--)
14     {
15         scanf("%d", &pi);
16         printf("%.0f
", f[pi-1]);
17     }
18 }

// 用二维字符串打表

 1 #include<stdio.h>
 2 #include<string.h>
 3 char f[1000][250];
 4 void add(char num1[], char num2[], char num[])
 5 {
 6     int len1=strlen(num1), len2=strlen(num2);
 7     int min=len1>len2?len2:len1, i,k;
 8     k=0;
 9     for(i=0;i<min;i++)
10     {
11         num[i]=(num1[i]+num2[i]+k-2*'0')%10+'0';
12         k=(num1[i]+num2[i]+k-2*'0')/10;
13     }
14     num[i]='';
15     if(len1>len2) strcat(num,num1+min);
16     if(len1<len2) strcat(num,num2+min);
17     if(len1!=len2&&k) ++num[min];
18     if(len1==len2&&k)
19     { num[min++]='1'; num[min]=''; }
20 }
21 void table()
22 {
23     f[0][0]=f[1][0]='1'; f[0][1]=f[1][1]='';
24     for(int i=2;i<1000;i++)
25         add(f[i-1],f[i-2], f[i]);
26 }
27 int main()
28 {
29     int n, pi;
30     table();
31     scanf("%d", &n);
32     while(n--)
33     {
34         scanf("%d", &pi);
35         for(int i=strlen(f[pi-1])-1;i>=0;i--)
36             printf("%c", f[pi-1][i]);
37         printf("
");
38     }
39     return 0;
40 }