首页 > ACM题库 > HDU-杭电 > HDU 1715 大菲波数-高精度-[解题报告] C++
2013
12-21

HDU 1715 大菲波数-高精度-[解题报告] C++

大菲波数

问题描述 :

Fibonacci数列,定义如下:
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值。

输入:

输入第一行为一个整数N,接下来N行为整数Pi(1<=Pi<=1000)。

输出:

输出为N行,每行为对应的f(Pi)。

样例输入:

5
1
2
3
4
5

样例输出:

1
1
2
3
5

点击打开链接

//大数运算!!
#include"stdio.h"
#include"string.h"
int a[1001][1001];
int main()
{
	int i,j,k;
	int n,t;
	int carry;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		memset(a,0,sizeof(a));
		a[1][1]=1;a[2][1]=1;
		for(i=3,k=1;i<=n;i++)
		{
			for(j=1,carry=0;j<=k;j++)
			{
				a[i][j]=a[i-1][j]+a[i-2][j]+carry;;
				carry=a[i][j]/10;
				a[i][j]%=10;
			}
			while(carry)//这里容易忽略!!
			{
				a[i][++k]=carry;
				carry/=10;
			}
		}
		for(i=k;i>0;i--)
			printf("%d",a[n][i]);
		printf("\n");
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/yangyafeiac/article/details/7828437


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  3. [email protected]