斐波那契-大数加法-数组解法

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2（n>=2，n∈N*),前几项为，（1，1，2，3，5，8，13。。。）

用longlong来递推在第93项就会溢出，因此采用数组解法求斐波那契的前n项

#include<bits/stdc++.h>
using namespace std;
#define  MLEN 400//定义最大长度 
int len( int a[][MLEN],int i ){//确定数据长度 
	int len=0;
	while(a[i][++len]!=-1);
	return len;
}
void add(int a[][MLEN],int i){
	int tmp=0;//进位值 
	int len1=len(a,i-1);
	int len2=len(a,i-2);
//	printf("len1=%d len2=%d
",len1,len2);
	a[i][len1]=-1;//注意是len1!! 
	for(int j=1;j<=len2;j++){
		int t=a[i-1][len1-j]+a[i-2][len2-j];
		a[i][len1-j]=(tmp+t)%10;
		tmp=(tmp+t)/10;//进位值 
	}
	if(len1>len2){
		int t=a[i-1][0]+tmp;
		if(t>=10){//len1进位 
			a[i][0]=t%10;
			for(int j=len1+1;j>0;j--){//后移一位 
				a[i][j]=a[i][j-1];
			} 
			a[i][0]=t/10;
		}else{
			a[i][0]=t;
		}
	}else if(len1==len2){
		if(tmp>0){
			for(int j=len1+1;j>0;j--){//后移一位 
				a[i][j]=a[i][j-1];
			} 
			a[i][0]=tmp;
		}
	} 
	
}
void print(int a[][MLEN],int i){//输出打印
	int j=0;
	while(a[i][j]!=-1){
		cout<<a[i][j++];
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	int  a[n][MLEN]={
         
  {1,-1},{1,-1},{2,-1},{3,-1},{5,-1},{8,-1},{1,3,-1},{2,1,-1}};//前8项 
	for(int i=8;i<n;i++){
		add(a,i); 
	}
	for(int i=0;i<n;i++){
		printf("第%4d项= ",i+1);
		print(a,i);
		cout<<"
";
	}

 return 0;
}