a.cpp

适合计算第n个Fibonacci数

#include<iostream>
//#include<stdlib.h>

#include <string>

	
#define NULL 0
#define N 1100
using namespace std;
   
short *temp;
class gaojingdu
{
private:
	short *a;
	int num;
public:
    gaojingdu();
	gaojingdu(short *head,int n);
	~gaojingdu();
	gaojingdu &operator +=(gaojingdu &x);
	gaojingdu &operator -=(gaojingdu &x);
	gaojingdu &operator *=(gaojingdu &x);
 	gaojingdu &operator /=(gaojingdu &x);
	gaojingdu &operator = (gaojingdu &x);
	void input(string str);
	void output();
    gaojingdu& liancheng(gaojingdu &x,gaojingdu &y,gaojingdu &H1);
};
gaojingdu::gaojingdu()
{
	num=0;
	a=new short[N];
}
gaojingdu::gaojingdu(short *head,int n)
{
	num=n;
	a=head;
}
gaojingdu::~gaojingdu()
{
   delete [] a;
}
gaojingdu &gaojingdu::operator +=(gaojingdu &x)
{
	int i;
	if (num<=x.num)
	{
		for (i=num+1;i<=x.num+1;i++)
			*(a+i)=0;
	}
	else 
	{
		for (i=x.num+1;i<=num+1;i++)
			*(x.a+i)=0;
		*(a+num+1)=0;
	}
	int temp=num>x.num?num:x.num;
	for (i=1;i<=temp;i++)
	{
		*(a+i)+=*(x.a+i);
		if (*(a+i)>=10)
		{
			*(a+i)-=10;
			*(a+i+1)+=1;
		}
	}
	if (*(a+temp+1)==0)
		num=temp;
	else num=temp+1;
    return *this;	
}
gaojingdu &gaojingdu::operator -=(gaojingdu &x)
{
	int i;
	for (i=x.num+1;i<=num;i++)
	    *(x.a+i)=0;
	for (i=1;i<=num;i++)
	{
		*(a+i)-=*(x.a+i);
		if (*(a+i)<0)
		{
			*(a+i)+=10;
			*(a+i+1)-=1;
		}
	}
	for (i--;i>=1;i--)
	{
		if (*(a+i)==0)
			num--;
		else break;
	}
	if (num==0) num=1;
	return *this;
}
gaojingdu &gaojingdu::operator *=(gaojingdu &x)
{
	short *temp,jin,i,j;
	temp=new short[N];;
	for (i=1;i<=num+x.num+1;i++)
	*(temp+i)=0;
	for (i=1;i<=x.num;i++)
	{
		jin=0;
		for (j=1;j<=num;j++)
		{
			*(temp+i+j-1)+=*(a+j)**(x.a+i)+jin;
			if (*(temp+i+j-1)>=10)
			{
				jin=*(temp+i+j-1)/10;
				*(temp+i+j-1)=*(temp+i+j-1)%10;
			}
			else jin=0;
			if (j==num)
				*(temp+i+j)+=jin;
			   
		}
		
	}
	for (i=1;i<=num+x.num;i++)
	{
		if (*(temp+i)>=10)
		{
			*(temp+i+1)+=*(temp+i)/10;
			*(temp+i)=*(temp+i)%10;
		}
	}
	if (*(temp+num+x.num)!=0)
		num=num+x.num;
	else num=num+x.num-1;
   	 delete[]a;
	a=temp;
	return *this;
}
gaojingdu &gaojingdu::operator /=(gaojingdu &x)
{
	int compare(short *x11,short *y11,int x1,int y1);
	short *x11,*y11,*temp0,*p;
	int x1,y1,flag,flag0,i,pos,ff;
	x11=a;
	y11=x.a;
	x1=num;
	y1=x.num;
	flag=compare(x11,y11,x1,y1);
	if (flag==1)
	{
		temp=new short[N];
		for (i=1;i<=x1-y1+1;i++)
			*(temp+i)=0;
		temp0=new short[N];
		for (i=1;i<=x1-y1;i++)
			*(temp0+i)=0;
		for (i=x1-y1+1;i<=x1;i++)
		    *(temp0+i)=*((x.a)+i-x1+y1);
		flag0=compare(x11,temp0,x1,x1);
        p=temp0;
		if (flag0==1||flag0==0)
			ff=pos=x1-y1+1;
		else  
		{
			ff=pos=x1-y1;
			p=temp0+1;
			--x1;
		}
	/*	gaojingdu H(p,x1); //内定
		while (flag0=compare(a,x.a,num,x.num),flag0==1||flag0==0)
		{
			
			while (compare(x11,H.a,num,H.num)==-1&&compare(H.a,x.a,H.num,x.num)==1)
			{
				H.a=++p;
				H.num--;
				pos--;
			
			}*this-=H;
			(*(temp+pos))++;
           //  if (H.num==x.num-1)
			//	break;
		}*/
		while (flag0=compare(a,x.a,num,x.num),flag0==1||flag0==0)
		{
			
			while (compare(x11,p,num,x1)==-1&&compare(p,x.a,x1,x.num)==1)
			{
				p++;
				x1--;
				pos--;

			}


	    	for (i=x1+1;i<=num;i++)
	            *(p+i)=0;
	       for (i=1;i<=num;i++)
		   {
		     *(a+i)-=*(p+i);
	        	if (*(a+i)<0)
				{
		        	*(a+i)+=10;
			        *(a+i+1)-=1;
				}
		   }
	            for (i--;i>=1;i--)
				{
		            if (*(a+i)==0)
			        num--;
		            else break;
				}
	          if (num==0) num=1;
			  (*(temp+pos))++;
		}
	  for (i=1;i<=ff;i++)
		  a[i]=temp[i];
		
		num=ff;
	}
	else if(flag==-1)
	{
		num=1;
		 delete[]a;
		a=new short[N];
		*(a+1)=0;
	}
	   else if (flag==0)
	   {	  
		   num=1;
		   delete[]a;
		   a=new short[N];
		   *(a+1)=1;
	   }
	return *this;

}
gaojingdu& gaojingdu::operator = (gaojingdu &x)
{
	int i;
	short* temp=new short[N];;
	(*this).num=x.num;
	for (i=1;i<=x.num;i++)
		*(temp+i)=*(x.a+i);
	(*this).a=temp;
	return *this;

}
void gaojingdu::input(string str)
{

	num=str.length();

	for (int i=1;i<=num;i++)
		a[i]=short(str[num-i]-('0'-0));


}
void gaojingdu::output()
{
	int i;
	for (i=num;i>=1;i--)
		cout<<*(a+i);
	cout<<endl;
}
gaojingdu& gaojingdu::liancheng(gaojingdu &x,gaojingdu &y,gaojingdu &H1)
{
    int compare(short *x11,short *y11,int x1,int y1);
	gaojingdu temp,temp1;
	temp=x;
	temp1=x;
	temp1-=H1;
	temp-=y;
    while(compare(temp1.a,temp.a,temp1.num,temp.num)==1)//problem;
	{
	    temp+=H1;
		x*=temp;
	
	}

	return x;
}
int compare(short *x11,short *y11,int x1,int y1)
{
	int i;
	if (x1>y1) return 1;
	else if (x1<y1) return -1;
	     else for(i=x1;i>=1;i--) 
		 { if (*(x11+i)==*(y11+i))  
			continue;
		 if (*(x11+i)>*(y11+i))  return 1;
		   else return -1;

		 }
	return 0;

}

int main()
{
	int n ,flag=1;
		while(cin>>n)
	{
	short *temp=new short[N];
	*(temp+1)=1;
	gaojingdu H1(temp,1);
	short *temp1=new short[N];
	*(temp1+1)=1;
	gaojingdu H2(temp1,1);

	n-=2;
	while (n>0)
	{
		H1+=H2;
		n--;
		if (!n) {flag=1;break;}
		H2+=H1;
			n--;
			if (!n) {flag=0;break;}

	}
	if (flag==1) H1.output();
	else H2.output();
	}
}