hdu1715 大菲波数（高精度）

大菲波数

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6601    Accepted Submission(s): 2169

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

5
1
2
3
4
5

 

Sample Output

1
1
2
3
5

 

Source

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

 

Recommend

lcy

 

注意这道题要求最大输出的菲波数是第1000个，也就是可以在网络上查出斐波那契数列的第1000位有多少，我在百度上查了了一下看到2008位才300位数，所以说可以用一个比300大的数作为数组容量，然后就是因为要存储数表，所以是需要二维数组的，算法的复杂度是O(n^2)，所以是不会TLE的。还有注意最好是先把表算出来，再查表，那样时间复杂度会低些。其余的计算就是类似于两个大数相加的算法。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define maxe 1004
using namespace std;
int a[1005][1005];

int main()
{
    int t;
    scanf("%d",&t);
    int i,j;
    memset(a,0,sizeof(a));
    a[1][1]=1;
    a[2][1]=1;
    int s;
    int plus=0;
    for(i=1;i<=997;i++)
    {
       for(j=1;j<=maxe;j++)
       {
          s=a[i+1][j]+a[i][j]+plus;
          a[i+2][j]=s%10;
          plus=s/10;
          //if(plus==0 && s==0)break;之所以去掉是因为存在这种情况而不能跳出的情况，
          //例如10+10=20，如果按照这种算法就 
       }
    }
    while(t--)
    {
       int p;
       scanf("%d",&p);
       for(i=maxe;i>=1;i--) if(a[p][i])break;
       for(;i>=1;i--)
          printf("%d",a[p][i]);
       printf("\n");
    }
    
    system("pause");
    return 0;
}