HDU——1715大菲波数（大数加法）

发布时间：2020-12-14 02:04:15 所属栏目：大数据来源：网络整理

导读：大菲波数 Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16125????Accepted Submission(s): 5355 Problem Description Fibonacci数列，定义如下： f(1)=f(2)=1 f(n)=f(n-1)+f(n-2) n=3。计算

大菲波数

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16125????Accepted Submission(s): 5355

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

网上查了下第1000个数字有200+位数，因此只能用大数加法模版

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
void Add(char a[],char b[],char d[])
{
    char c[500];
    int lena=strlen(a),lenb=strlen(b);
    int i,j,len;
    len=lena>lenb?lena:lenb;
    len++;
    c[0]='';
    for(i=1;i<=len;i++)
		c[i]='0';
    for(i=1;i<=lena;i++)
		c[i]+=a[lena-i]-48;
    for(i=1;i<=lenb;i++)
		c[i]+=b[lenb-i]-48;
    for(i=0;i<=len;i++)
        if(c[i]>57)
    	{
            c[i]-=10; 
            c[i+1]++;
        }
    for(i=len;i>1;i--)
        if(c[i]==48)
			len--;
        else 
			break;
     for(i=0;i<=len;i++)
        d[i]=c[len-i];
}
char list[1001][1000]={"0","1","1"};
int main(void)
{
	int t,n;
	cin>>t;
	while (t--)
	{
		cin>>n;
		for (int i=3; i<=n; i++)
			Add(list[i-1],list[i-2],list[i]);
		cout<<list[n]<<endl;
	}
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!