【杭电oj】1715 - 大菲波数（大数递推）

FishWang

发布于 2025-08-26 18:46:03

7700

代码可运行

运行总次数：0

代码可运行

点击打开题目大菲波数

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

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

Sample Output

Source

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

第1000位的位数为209，注意精度就行了。

代码如下：

#include <cstdio>
int main()
{
	int k,n,u;
	int fi[1011][211] = {0};
	fi[1][1] = 1;
	fi[2][1] = 1;
	for (int i = 3 ; i <= 1000 ; i++)
	{
		for (int j = 1 ; j <= 210 ; j++)
		{
			fi[i][j] += fi[i-1][j] + fi[i-2][j];
			if (fi[i][j] >= 10)
			{
				fi[i][j] -= 10;
				fi[i][j+1]++;
			}
		}
	}
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d",&n);
		k = 210;
		for ( ; fi[n][k] == 0 ; k--);
		for ( ; k >= 1 ; k--)
			printf ("%d",fi[n][k]);
		printf ("\n");
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

int