首页 > 代码库 > HDU　1715 大菲波数

HDU　1715 大菲波数

2024-07-15 03:18:44   221人阅读

/*
中文题意：
中文翻译：
题目大意：
解题思路：
难点详解：
关键点：
解题人：lingnichong
解题时间：2014/7/31    20:42
解题感受：
*/



大菲波数

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


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
 


#include<stdio.h>
#include<string.h>
#define Pi 1010
#define MAXN 2500
int f[Pi][MAXN];
int main()
{
	int i,j,k;
	memset(f,0,sizeof(f));
	f[1][0]=f[2][0]=1;
	for(i=3;i<Pi;i++)
	{
		for(j=MAXN-1;j>=0;j--)
		if(f[i-1][j]!=0)  break;
		for(k=0;k<=j;k++)
		{
			f[i][k]+=(f[i-1][k]+f[i-2][k]);
			if(f[i][k]>=10)
			{
				f[i][k]-=10;
				f[i][k+1]+=1;
			}
		}	
	}
	int T,n;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=MAXN-1;(i>=0)&&(f[n][i]==0);i--);
		for(;i>=0;i--)
		printf("%d",f[n][i]);
		printf("\n");
	}
	return 0;
}




联系
我们