首页 > 代码库 > hdu1715 大菲波数

hdu1715 大菲波数

转载请注明出处:http://blog.csdn.net/u012860063

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1715

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   |   We have carefully selected several similar problems for you:  1753 1865 1063 1133 1250 

代码如下:

//HDU 1715
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1002
using namespace std;
char Fib[N][N];
int main()
{
    memset(Fib,'0',sizeof(Fib)); // 初始化
    Fib[0][0]='0';
    Fib[1][0]='1';
    Fib[2][0]='1';
    int i,j,d=1;
    for(i = 3 ; i < N ; i++) //大数相加
    {
        d++;
        int c=0,s;
        for(j = 0 ; j <= d ; j++)
        {
            s=Fib[i-1][j]-'0'+Fib[i-2][j]-'0'+c;
            c=s / 10;       //进位
            Fib[i][j] = s%10+'0';
        }
        
    }
    int t;
    //cin>>t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        // cin >> n;
        scanf("%d",&n);
        int k=N-1;
        while(k--)
        {
            if(Fib[n][k]!='0')
                break;    //去掉前面的0
        }
        for(i=k;i>=0;i--)
            printf("%c",Fib[n][i]);
        //cout<<Fib[n][i];
        // cout<<endl;
        printf("\n");
    }
    return 0;
}