hdu1715 大菲波数

时间:2024-07-30 19:07:38

转载请注明出处:http://blog.****.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
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;
}