?? stein.cpp
字號:
#include<iostream.h>
#include<strstrea.h>
#include<string.h>
#include<stdlib.h>//atoi函數
#include<fstream.h>
class BigInterger
{
int *IntData;
int ILength;
public:
BigInterger(char* CharData);
BigInterger(BigInterger&);
~BigInterger();
BigInterger& operator = (BigInterger& bi);
BigInterger& operator /= (int div);
BigInterger& operator *= (int mul);
BigInterger& operator *= (BigInterger&);
friend bool operator > (BigInterger& bi1,BigInterger& bi2);
BigInterger& operator -= (BigInterger& bi);//將兩對象相減,取絕對值
int operator % (int res);//求余
bool operator != (int zero);
bool operator == (int zero);
int* GetIntData(void )
{
return IntData;
}
int GetILength(void )
{
return ILength;
}
};
BigInterger::BigInterger(char* CharData)//大整數的構造函數,從參數CharData中得到輸入,并把其值存入IntData數組中
{
char buf[5];//緩存CharData的4個字符,后面的istrstream類要求其大小必須設為5
istrstream DivideStr(CharData);
int slen=strlen(CharData);
int i;
if(slen%4)
{
IntData=new int[slen/4+1];//萬進制
ILength=slen/4+1;
DivideStr.get(buf,slen%4+1);
IntData[0]=atoi(buf);
for(i=1;i<ILength;i++)
{
DivideStr.get(buf,5);
IntData[i]=atoi(buf);
}
}
else
{
IntData=new int[slen/4];//萬進制
ILength=slen/4;
for(i=0;i<ILength;i++)
{
DivideStr.get(buf,5);
IntData[i]=atoi(buf);
}
}
}
BigInterger::~BigInterger()
{
if(this->IntData)
delete[] this->IntData;
this->ILength=0;
}
BigInterger::BigInterger(BigInterger& bi)//復制構造函數
{
this->ILength=bi.ILength;
this->IntData=new int[this->ILength];
for(int i=0;i<this->ILength;i++)
{
this->IntData[i]=bi.IntData[i];
}
}
BigInterger& BigInterger::operator = (BigInterger& bi)
{
if(this->IntData)
{
delete[] this->IntData;
}
this->IntData=new int[bi.ILength];
this->ILength=bi.ILength;
for(int i=0;i<this->ILength;i++)
{
this->IntData[i]=bi.GetIntData()[i];
}
return *this;
}
BigInterger& BigInterger::operator /= (int div)
{
int OneResidue=0;//數組IntData的每一元素除參數div后的余數
int temp;
for(int i=0;i<this->ILength;i++)
{
temp=(this->IntData[i]+OneResidue*10000)/div;//萬進制
OneResidue=(this->IntData[i]+OneResidue*10000)%div;
this->IntData[i]=temp;
}
//當大整數對象長度大于1而且高位又有0時,處理高位,如果大整數對象長度＝1,就不需要
if(this->ILength>1)
{
for( i=0;i<this->ILength;i++)//用i來得到為0的高位數
{
if(this->IntData[i]!=0)
break;
}
if(i!=0)//如果IntData的高位為0
{
int count=i;
for(int j=0;i<this->ILength;i++)//去掉高位的0
{
this->IntData[j]=this->IntData[i];
j++;
}
this->ILength-=count;//將大整數對象長度變小
}
}
return *this;
}
BigInterger& BigInterger::operator *= (int mul)
{
//先乘,結果使得IntData的元素可能大于10000
for(int i=this->ILength-1;i>=0;i--)
{
this->IntData[i]*=mul;
}
//后進位,由于是萬進制,如果IntData的元素大于10000,就要逢萬要進位.
for(i=this->ILength-1;i>=0;i--)
{
if(this->IntData[i]>=10000)//在最高的那位(i=0時)不需要也不能進位,這種情況留在后面處理
if(i>0)
{
this->IntData[i-1]+=this->IntData[i]/10000;
this->IntData[i]%=10000;
}
}
//如果最高的那位(i=0時)的值IntData[0]>=10000,那么要處理進位就要重新分配空間
if(this->IntData[0]>=10000)
{
ILength+=1;//長度加1
int* TempIntData=new int[ILength];//用一個名為TempInt的數組緩存this->IntData
TempIntData[0]=this->IntData[0]/10000;
this->IntData[0]%=10000;
for(i=1;i<ILength;i++)//將IntData[0...ILength-1]拷貝到TempIntData[1...ILength]
{
TempIntData[i]=this->IntData[i-1];
}
delete[] this->IntData;
this->IntData=new int[ILength];
for(i=0;i<ILength;i++)
{
this->IntData[i]=TempIntData[i];
}
delete[] TempIntData;
}
return *this;
}
BigInterger& BigInterger::operator *= (BigInterger& c)
{
int i,j,k;
int ResultLen=this->ILength+c.ILength-1;
int* result=new int[ResultLen];//采用result數組來緩存結果
for(i=0;i<ResultLen;i++)
{
result[i]=0;
}
int* mul=new int[c.ILength];
//先乘,兩個大數相乘,結果使得IntData的元素可能大于10000
for(j=0;j<this->ILength;j++)
{
for(i=0;i<c.ILength;i++)
mul[i]=c.IntData[i]*this->IntData[j];
for(k=j;k<c.ILength+j;k++)
{
result[k]=result[k]+mul[k-j];
}
}
//后進位,由于是萬進制,如果IntData的元素大于10000,就要逢萬要進位.
for(i=ResultLen-1;i>=0;i--)
{
if(result[i]>=10000)//在最高的那位(i=0)不進位
if(i>0)
{
result[i-1]+=result[i]/10000;
result[i]%=10000;
}
}
//將值從result復制到this->IntData
delete[] this->IntData;
if(result[0]>=10000)
{
this->ILength=ResultLen+1;
this->IntData=new int[this->ILength];
this->IntData[0]=result[0]/10000;
this->IntData[1]=result[0]%10000;
for(i=2;i<this->ILength;i++)
{
this->IntData[i]=result[i-1];
}
}
else
{
this->ILength=this->ILength+c.ILength-1;
this->IntData=new int[this->ILength];
for(i=0;i<this->ILength;i++)
this->IntData[i]=result[i];
}
delete[] result;
delete[] mul;
return *this;
}
bool operator > (BigInterger& bi1,BigInterger& bi2)
{
if(bi1.ILength>bi2.ILength)
return true;
else if(bi1.ILength<bi2.ILength)
return false;
else
{
for(int i=0;i<bi1.ILength;i++)
{
if(bi1.IntData[i]>bi2.IntData[i])
return true;
if(bi1.IntData[i]<bi2.IntData[i])
return false;
}
return false;//此時兩對象的IntData相等
}
}
BigInterger& BigInterger::operator -= (BigInterger& bi)//－(減號運算)重載為相減并求絕對值的運算
{
int i,j;
if((*this)>bi)
{
i=bi.ILength-1;
j=this->ILength-1;
while(i>=0)
{
if(this->IntData[j]-bi.IntData[i]<0)
{
this->IntData[j-1]--;
this->IntData[j]+=10000;
}
this->IntData[j]-=bi.IntData[i];
i--;
j--;
}
}
else//this小于bi
{
int* TempInt=new int[this->ILength];
int TempLen=this->ILength;
for(i=0;i<this->ILength;i++)
{
TempInt[i]=this->IntData[i];
}
*this=bi;//調用重載賦值符函數
i=TempLen-1;
j=this->ILength-1;
while(i>=0)
{
if(this->IntData[j]-TempInt[i]<0)
{
this->IntData[j-1]--;
this->IntData[j]+=10000;
}
this->IntData[j]-=TempInt[i];
i--;
j--;
}
delete[] TempInt;
}
//整理,如果IntData的高位元素為0,就必須去掉
if(this->ILength>1)
{
for( i=0;i<bi.ILength;i++)
{
if(this->IntData[i]!=0)
break;
}
if(i!=0)//如果IntData的高位為0
{
int count=i;
for(int j=0;i<this->ILength;i++)//去掉高位的0
{
this->IntData[j]=this->IntData[i];
j++;
}
this->ILength-=count;//將長度變小
}
}
return *this;
}
int BigInterger::operator % (int res)//求余,res參數限制在9999以內
{
return this->IntData[this->ILength-1]%res;
}
bool BigInterger::operator != (int zero)//判斷大整數對象和參數zero(一般為0)的大小,當然,zero還可以為其它整數值
{
if(this->IntData[0]!=zero)
return true;
else
return false;
}
bool BigInterger::operator == (int zero)//判斷大整數對象和參數zero(一般為0)的大小,當然,zero還可以為其它整數值
{
if(this->IntData[0]==zero)
return true;
else
return false;
}
BigInterger gcd(BigInterger& m,BigInterger& n)
{
BigInterger c=("1");//創建大整數c,并賦初值1
while(m!=0&&n!=0)
{
if (m%2==0&&n%2==0)
{
m/=2; //不可用"/"號,如果寫成m=m/2形式,那么當m/2返回時,還要調用operator=,
n/=2; //然而在operator=函數中,對每個對象是做深拷貝,(詳見operator=)
c*=2;//同"/"號
}
if (m%2==0&&n%2!=0)
{
m/=2;
}
if (m%2!=0&&n%2==0)
{
n/=2;
}
if (m%2!=0&&n%2!=0)
{
BigInterger i=m;
m-=n; //－(減號運算)重載為相減并求絕對值的運算,不可用"-"號,同理"/"號
if(n>i)//只重載了>運算符
n=i;
}
}
if (m==0)
{
return n*=c;
}
if (n==0)
{
return m*=c;
}
}
void main(int argc,char *argv[])
{
char buf1[100],buf2[100];
cout<<"程序開始運行..."<<endl;
char c;
do{
cout<<"選擇從文本文件inputdata.txt輸入值,請按f,選擇從控制臺輸入值按其它鍵"<<endl;
// c=cin.get();
c=cin.get();
char OutPutBuf[100];//將最終結果輸入到一個字符型數組中并輸出,數組大小可以任意調整
if(c=='f'||c=='F')
{
ifstream fin(".\\debug\\inputdata.txt");
ofstream fout(".\\debug\\outputdata.txt",ios::out);
if(!fout)
cout<<"error";
for(int i=0;i<10;i++)
fin.getline(buf1,sizeof(buf1));
while(fin.good())//
{
fin.getline(buf1,sizeof(buf1));//得到第一個大整數
fin.getline(buf2,sizeof(buf2));//得到第二個大整數
BigInterger m(buf1);
BigInterger n(buf2);
BigInterger result=gcd(m,n);
ostrstream OutPut(OutPutBuf,sizeof(OutPutBuf),ios::out);
for(i=0;i<result.GetILength();i++)
{
int temp=result.GetIntData()[i];
if(i>0)//如果IntData中的某一位長度小于4位，就應該在這個數前相應補0
{
if(temp<10)
OutPut<<"000";
else if(temp<100)
OutPut<<"00";
else if(temp<1000)
OutPut<<"0";
}
OutPut<<result.GetIntData()[i];
}
OutPut<<'\0';
fout.write("第一個大整數:",13);
fout.write(buf1,strlen(buf1));
fout.write("\n",1);
fout.write("第二個大整數:",13);
fout.write(buf2,strlen(buf2));
fout.write("\n",1);
fout.write("最大公因數:",11);
fout.write(OutPutBuf,strlen(OutPutBuf));
fout.write("\n",1);
}//while
cout<<"程序保存在outputdata.txt中"<<endl;
}
else
{
cout<<"輸入一個大整數:";
cin>>buf1;
cout<<"輸入另一個大整數:";
cin>>buf2;
BigInterger m(buf1);
BigInterger n(buf2);
BigInterger result=gcd(m,n);
ostrstream OutPut(OutPutBuf,sizeof(OutPutBuf),ios::out);
for(int i=0;i<result.GetILength();i++)
{
int temp=result.GetIntData()[i];
if(i>0)
{
if(temp<10)//如果IntData中的某一位長度小于4位，就應該在這個數前相應補0
OutPut<<"000";
else if(temp<100)
OutPut<<"00";
else if(temp<1000)
OutPut<<"0";
}
OutPut<<result.GetIntData()[i];
}
OutPut<<'\0';
cout<<"OK,The Result is:"<<endl;
cout<<OutPutBuf<<endl;
}
cout<<"按e鍵退出,按其它鍵繼續測試"<<endl;
cin.get();
c=cin.get();
cin.get();
}while(c!='e');
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -