一个简单的大数实现方案，计算斐波纳契数列

计算斐波那契数列Fn=Fn_1+Fn_2，（PS：千万不要递归）！！！！

《编程之美》2.9计算Fn，提出了三种方案计算Fn，方案一，有线性时空复杂度；方案二，求通项公式，但是好像对于一些编程语言来说没有什么实用性；方案三，引入了矩阵计算有最优的时间复杂度！！！

当然，这里我关心的不是时间复杂度，而是一般计算机能算到斐波那契数列的第几位？

众所周知，long long类型的变量能表示20位无符号整形，利用常规的循环计算，大概能完整的计算出F93

上网百度一个大数解决方案(参考自：http://www.voidcn.com/article/p-mdoamqoa-nv.html?)，好好学习了大数的四则运算，大概能算很多位了～～～！

#include<iostream>
#include<cstring>
#include<cassert>
using namespace std;
#define  MAXLENGTH 1000
struct BigInt
{
	//bool isPositive;//表示该数的符号
	int length;
	int s[MAXLENGTH];
};
void Str2BigInt(const char * str,BigInt & x)
{
	x.length=strlen(str);
	for(int i=0;i<x.length;i++)
	{
		assert(str[i]>='0'&& str[i]<='9');//断言
		x.s[x.length-1-i]=str[i]-'0';
	}
	if(x.length==0)
	{
		x.length=1;
		x.s[0]=0;
	}
}
void PrintBigInt(const BigInt& x)
{
	for(int i=x.length-1;i>=0;i--)
		cout<<x.s[i];
}
//大数加法(两个正数的相加)
void PlusBigInt(const BigInt& A,const BigInt& B,BigInt & C)
{
	int i;
	C.s[0]=0;
	for(i=0;i<A.length || i<B.length;i++)//此处用||比用&&程序简洁很多
	{
		if(i<A.length)C.s[i]+=A.s[i];
		if(i<B.length)C.s[i]+=B.s[i];
		C.s[i+1]=C.s[i]/10;//注意里，既计算了该位的值也为下一步的的计算进行了初始化，初始化为零或以1；
		C.s[i]=C.s[i]%10;
	}
	C.length=C.s[i]>0?i+1:i;
}
//大数减法(大数减小数)
void SubBigInt(const BigInt& A,BigInt & C)
{
	//对应为相减A[i]-B[i]-borrow;第i+1位的借位通过上一位的结果判断
	int i=0,borrow=0;
	while(i<A.length)//B是小数
	{
		if(i<B.length)
		    C.s[i]=A.s[i]-B.s[i]-borrow;//正里假象A,B位数相同，（B前面不足的认为是零） 
		else
			C.s[i]=A.s[i]-borrow;
		if(C.s[i]<0)
		{
			borrow=1;
			C.s[i]+=10;
		}
		else
			borrow=0;
		i++;
	}
	while(i>0&&C.s[i]<=0) i--;
	C.length=i+1;
}
//大数乘法
void MultiBigInt(const BigInt& A,BigInt & C)
{
	C.length=A.length+B.length;
	for(int i=0;i<C.length;i++)
		C.s[i]=0;
	int i,j;
	for(i=0;i<B.length;i++)
		for(j=0;j<A.length;j++)
			C.s[i+j]+=A.s[j]*B.s[i];//注意这里是累加
	i=0;
	while(C.s[i]>0)
	{
		C.s[i+1]+=C.s[i]/10;
		C.s[i]=C.s[i]%10;
		i++;
	}
	C.length=i;
}
//大数比较
int CMPBigInt(const BigInt& A,const BigInt& B)
{
	if(A.length>B.length)
		return 1;
	if(A.length<B.length)
		return -1;
	int i=A.length-1;
	while(i>0&&A.s[i]==B.s[i]) i--;
	return A.s[i]-B.s[i];

}

//大数除法
void DivideBigInt(const BigInt& A,BigInt & C,BigInt &D)
{
	//C是商，D是余数
	//类比除法计算
	D.length=1;D.s[0]=0;
	int i,j;
	for(i=A.length-1;i>=0;i--)
	{
		//不断增大D直到大于B
		if(!(D.length==1&&D.s[0]==0))//刚开始时不需要左移
		{
			//需要左移D
			for(j=D.length-1;j>=0;j--)
				D.s[j+1]=D.s[j];
			D.length++;
		}
		//扩充一位
		D.s[0]=A.s[i];
		C.s[i]=0;
		while((j=CMPBigInt(D,B))>=0)
		{
			SubBigInt(D,B,D);
			C.s[i]++;
			if(j==0)
				break;//注意：这里十分巧妙;
		}
	}
	i = A.length - 1;  
    while (i>0 && !C.s[i]>=0) --i;  
    C.length = i+1;  
}
// 大整数置0  
inline void ZeroBigInt(BigInt& x)  
{  
	x.length = 1; x.s[0] = 0;  
}  
// 大整数置1  
inline void OneBigInt(BigInt& x)  
{  
	x.length = 1; x.s[0] = 1;  
}

int main(int argc,char *argv[])
{
	//求科波菲尔第4000项；
	BigInt Fn_1,Fn_2,Fn,zero;
	ZeroBigInt(zero);
	ZeroBigInt(Fn_2);
	OneBigInt(Fn_1);
	int N=2;
	while(N<=93)
	{
		PlusBigInt(Fn_1,Fn);
		PlusBigInt(zero,Fn_1,Fn_2);
		PlusBigInt(zero,Fn_1);
		N++;
	}
	PrintBigInt(Fn);
	cout<<endl;
	N=2;
	unsigned long long fn_1=1,fn_2=0;
	unsigned long long fn;
	while(N<=93)
	{
		fn=fn_1+fn_2;
		fn_2=fn_1;
		fn_1=fn;
		N++;
	}
	cout<<fn;
	system("pause");
	return 0;
}