大数斐波那契数列

原题为洛谷p2437

利用string的加法特性

f[i]=f[i-1]+f[i-2]

#include<bits/stdc++.h>
using namespace std;
string fb[1005]={"1","1"};
long long a[1005],b[1005],c[1005];
void fib(int n)
{
	for(int i=0;i<n;i++)
	{
		memset(c,0,sizeof(c));//注意清零
		for(int j=0;j<fb[i].length();j++)//将f[i-2]取出
		{
			a[j]=fb[i][fb[i].length()-1-j]-'0';//注意是从后往前因为string类中是位数大的在前
		}
		for(int j=0;j<fb[i+1].length();j++)//将f[i-1]取出
		{
			b[j]=fb[i+1][fb[i+1].length()-1-j]-'0';//同理
		}
		int l=fb[i+1].length()//取当前最大位
		for(int j=0;j<l;j++)//计算f[i]
		{
			c[j]+=a[j]+b[j];
			if(c[j]>=10)
			{
				c[j+1]+=c[j]/10;
				c[j]%=10;
			}
		}
		if(c[l]!=0)//若f[i]比f[i-1]的值多一位
		{
			l++;
		}
		for(int j=l-1;j>=0;j--)//将f[i]保持到string类中
		{
			fb[i+2]+=char(c[j]+'0');
		}
	}
}
int main()
{
    
    int n,m;
    cin>>m>>n;
    int ans=n-m;
    if(ans<=2)
    {
    	if(ans==0)
    	{
    		cout<<0;
		}
		else
		{
			cout<<1;
		}
	}
    fib(ans-1);//因为我代码的特性，传入fib的值为1时就已经把f[2](下标从0开始)算出来了
    cout<<fb[ans];
	return 0;
}