脚本宝典收集整理的这篇文章主要介绍了斐波那契数列（加强版，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

• 这题（指P1255）卡得我挺难受的（指WA，TLE，MLE都出来了）

• 题目很简单就是个斐波那契数列

• 重点是数据范围(N<=5000)这真的不会累死人吗

• 这么大的数据自然该想到用高精度

  以及不能用递归（因为存在大量重复运算，(O(2^n))的时间复杂度可不是闹着玩的）要用递推

程序分析

1. 高精度部分

   struct BigNum{
   	int len;
   	int d[20000];
   }A[5];
   
   bool cmp(BigNum a,BigNum b){
   	if(a.len!=b.len) return a.len>b.len;
   	for(int i = 0;i<a.len;i++){
   		if(a.d[i]!=b.d[i]) return a.d[i]>b.d[i];
   	}
   	return true;
   }
   
   BigNum operator+(const BigNum b,const BigNum a){
   	BigNum t;
   	memset(t.d,0,a.len+5);
   	for(int i = 0;i<=b.len;i++){
   		t.d[i] = a.d[i] + b.d[i];
   	}
   	for(int i = 0;i<=b.len;i++){
   		if(t.d[i]>=10){
   			t.d[i] -= 10;
   			t.d[i+1] += 1;
   		}
   	}
   	if(t.d[b.len]!=0){
   		t.len = b.len+1;
   	}else{
   		t.len = b.len;
   	}
   	return t;
   }
   void output(BigNum a){
   	for(int i = a.len-1;i>=0;i--){
   		printf("%d",a.d[i]);
   	}
   }
   

   BigNum只开到5的原因是要用到滚动数组否则会MLE

   （其实这段没什么主要就是把高精加搬过来了）

   以及一个运算符重载

   我个人认为这里的运算符重载完全可以被替换掉

   BigNum operator+(const BigNum &a,const BigNum &b);
   BigNum add(BigNum a,BigNum b);
   

2. 递推部分

   void output(BigNum a){
   	for(int i = a.len-1;i>=0;i--){
   		printf("%d",a.d[i]);
   	}
   }
   
   int main(){
   	int n;
   	scanf("%d",&n);
   	
   	A[1].d[0] = 1;
   	A[1].len = 1;
   	A[2].d[0] = 2;
   	A[2].len = 2;
   	if(n<3){
   		printf("%d",n);
   		return 0;
   	}
   	for(int i = 3;i<=n;i++){
   		A[0] = A[1];
   		A[1] = A[2]; 
   		A[2] = A[0] + A[1];
           //滚动数组
   	}
   	output(A[2]);
   	return 0;
   }
   

脚本宝典总结

以上是脚本宝典为你收集整理的斐波那契数列（加强版全部内容，希望文章能够帮你解决斐波那契数列（加强版所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。