主题:用高精度实现整数+—×/,并计算catalan数和大组合数2
接1
cata &cata::operator +(const cata &y)
{
int len_x=length(),len_y=y.length();
int len_max=len_x>len_y? len_x:len_y,len_min=len_x<len_y? len_x:len_y;
int *result=new int[len_max+1]; //result存放高精度加法结果
for(int i=0;i<len_max+1;i++) //将result全部置0
{
result[i]=0;
}
int carry=0,temp_1,temp_2; //carry为进位
for(i=0;i<len_min;i++) //按位加,分两步做
{
temp_2=temp_1=data[i]+y.data[i]+carry;
carry=temp_1/10;
if(carry)
result[i]=temp_2%10;
else result[i]=temp_2;
}
if(len_x>=len_y)
{
for(i=len_min;i<len_max;i++)
{
temp_2=temp_1=data[i]+result[i]+carry;
carry=temp_1/10;
if(carry)
{
result[i]=temp_2%10;
}
else
{
result[i]=temp_2;
}
}
}
else
{
for(i=len_min;i<len_max;i++)
{
temp_2=temp_1=y.data[i]+result[i]+carry;
carry=temp_1/10;
if(carry)
{
result[i]=temp_2%10;
}
else
{
result[i]=temp_2;
}
}
}
if(carry)
{
result[len_max]=carry;
n=len_max+1;
}
else
{
n=len_max;
}
int *temp=result; //指针的交换
result=data;
data=temp;
delete [] result;
return *this;
}///:p
cata &cata::operator -(const cata &y)
{
int len_max=length(),len_y=y.length();
int *result=new int [len_max]; //result用于存放高精度减法的结果
if(NULL==result)
{
cout<<"the error take place in -"<<endl;
exit(1);
}
for(int i=0;i<len_max;i++)
{
result[i]=0;
}
int borrow=0,temp; //borrow位借
int displace=y.displacement;
for(i=0;i<len_y;i++) //按位减,分两步做
{
temp=data[i]+10-y.data[i+displace]-borrow;
if(temp>=10)
{
temp=temp-10;
borrow=0;
}
else
{
borrow=1;
}
result[i]=temp;
}
for(int j=len_y;j<len_max;j++)
{
temp=data[j]+10-result[j]-borrow;
if(temp>=10)
{
temp=temp-10;
borrow=0;
}
else
{
borrow=1;
}
result[j]=temp;
}
n=len_max;
i=1;
while(result[n-i]==0&&i<n) //由于减法会在高位产生0,i的回溯相当于去掉无用的高位0
{
i++;
}
n=n-i+1; //i回溯后,重新计算n
int *temp_sub=result; //交换指针,保证结果实在*this对象中
result=data;
data=temp_sub;
delete [] result;
return *this;
}///:p
cata &cata::operator *(const cata &y)
{
int len_x=length(),len_y=y.length();
int len_z=len_x+len_y;
int *result=new int [len_z]; //result存放高精度*的结果
int *temp=new int [len_z];
if(NULL==result||NULL==temp)
{
cout<<"the error take place in *"<<endl;
exit(1);
}
for(int j=0;j<len_z;j++)
{
result[j]=0;
}
int carry,temp1,temp2; //carry为进位
for(j=0;j<len_y;j++) //模拟手工方法,实现乘法
{
for(int i=0;i<len_z;i++)
{
temp[i]=0;
}
carry=0;
for(i=0;i<len_x;i++)
{
temp2=temp1=data[i]*y.data[j]+carry;
carry=temp1/10;
if(carry)
{
temp[i+j]=temp2%10;
}
else
{
temp[i+j]=temp2;
}
}
if(carry)
{
temp[len_x+j]=carry;
}
int carry_add=0,temp1_add,temp2_add; //乘法中的加法
for(i=0;i<len_z;i++)
{
temp2_add=temp1_add=temp[i]+result[i]+carry_add;
carry_add=temp1_add/10;
if(carry_add)
{
result[i]=temp2_add%10;
}
else
{
result[i]=temp2_add;
}
}
}
this->n=len_z;
int i=1;
while(result[n-i]==0&&i<n)
{
i++;
}
n=n-i+1;
int *temp_change=result; //交换指针
result=data;
data=temp_change;
delete [] result;
return *this;
}///:p
cata &cata::operator +(const cata &y)
{
int len_x=length(),len_y=y.length();
int len_max=len_x>len_y? len_x:len_y,len_min=len_x<len_y? len_x:len_y;
int *result=new int[len_max+1]; //result存放高精度加法结果
for(int i=0;i<len_max+1;i++) //将result全部置0
{
result[i]=0;
}
int carry=0,temp_1,temp_2; //carry为进位
for(i=0;i<len_min;i++) //按位加,分两步做
{
temp_2=temp_1=data[i]+y.data[i]+carry;
carry=temp_1/10;
if(carry)
result[i]=temp_2%10;
else result[i]=temp_2;
}
if(len_x>=len_y)
{
for(i=len_min;i<len_max;i++)
{
temp_2=temp_1=data[i]+result[i]+carry;
carry=temp_1/10;
if(carry)
{
result[i]=temp_2%10;
}
else
{
result[i]=temp_2;
}
}
}
else
{
for(i=len_min;i<len_max;i++)
{
temp_2=temp_1=y.data[i]+result[i]+carry;
carry=temp_1/10;
if(carry)
{
result[i]=temp_2%10;
}
else
{
result[i]=temp_2;
}
}
}
if(carry)
{
result[len_max]=carry;
n=len_max+1;
}
else
{
n=len_max;
}
int *temp=result; //指针的交换
result=data;
data=temp;
delete [] result;
return *this;
}///:p
cata &cata::operator -(const cata &y)
{
int len_max=length(),len_y=y.length();
int *result=new int [len_max]; //result用于存放高精度减法的结果
if(NULL==result)
{
cout<<"the error take place in -"<<endl;
exit(1);
}
for(int i=0;i<len_max;i++)
{
result[i]=0;
}
int borrow=0,temp; //borrow位借
int displace=y.displacement;
for(i=0;i<len_y;i++) //按位减,分两步做
{
temp=data[i]+10-y.data[i+displace]-borrow;
if(temp>=10)
{
temp=temp-10;
borrow=0;
}
else
{
borrow=1;
}
result[i]=temp;
}
for(int j=len_y;j<len_max;j++)
{
temp=data[j]+10-result[j]-borrow;
if(temp>=10)
{
temp=temp-10;
borrow=0;
}
else
{
borrow=1;
}
result[j]=temp;
}
n=len_max;
i=1;
while(result[n-i]==0&&i<n) //由于减法会在高位产生0,i的回溯相当于去掉无用的高位0
{
i++;
}
n=n-i+1; //i回溯后,重新计算n
int *temp_sub=result; //交换指针,保证结果实在*this对象中
result=data;
data=temp_sub;
delete [] result;
return *this;
}///:p
cata &cata::operator *(const cata &y)
{
int len_x=length(),len_y=y.length();
int len_z=len_x+len_y;
int *result=new int [len_z]; //result存放高精度*的结果
int *temp=new int [len_z];
if(NULL==result||NULL==temp)
{
cout<<"the error take place in *"<<endl;
exit(1);
}
for(int j=0;j<len_z;j++)
{
result[j]=0;
}
int carry,temp1,temp2; //carry为进位
for(j=0;j<len_y;j++) //模拟手工方法,实现乘法
{
for(int i=0;i<len_z;i++)
{
temp[i]=0;
}
carry=0;
for(i=0;i<len_x;i++)
{
temp2=temp1=data[i]*y.data[j]+carry;
carry=temp1/10;
if(carry)
{
temp[i+j]=temp2%10;
}
else
{
temp[i+j]=temp2;
}
}
if(carry)
{
temp[len_x+j]=carry;
}
int carry_add=0,temp1_add,temp2_add; //乘法中的加法
for(i=0;i<len_z;i++)
{
temp2_add=temp1_add=temp[i]+result[i]+carry_add;
carry_add=temp1_add/10;
if(carry_add)
{
result[i]=temp2_add%10;
}
else
{
result[i]=temp2_add;
}
}
}
this->n=len_z;
int i=1;
while(result[n-i]==0&&i<n)
{
i++;
}
n=n-i+1;
int *temp_change=result; //交换指针
result=data;
data=temp_change;
delete [] result;
return *this;
}///:p