求帮优化 我的高精度加减法以及乘法模块
本帖最后由 SureEdding 于 2013-09-04 21:24:22 编辑
//高精度加法
void plus(char *a, char *b, char *c)
{
int i, j, l;
int length1, length2;
int A[10005] = { 0 }, B[10005] = { 0 }, C[10005] = { 0 }, D[10005] = { 0 };
length1 = strlen(a);
length2 = strlen(b);
int counter = 0;
if (length1 >= length2)//取A和B较长的长度
l = length1;
else
l = length2;
for (i = 0; i < length1; i++)//将字符串转化为整形数组
{
A[i] = a[length1 - i - 1] - '0';
}
for (i = 0; i < length2; i++)
{
B[i] = b[length2 - 1 - i] - '0';
}
for (i = 0; i < l; i++)
{
C[i] += A[i] + B[i]; //c[i]表示结果的第i位
if (C[i] >= 10) //当前的位和大于等于10 需进位
{
C[i + 1]++; //下一位加1
C[i] -= 10; //当前位减去10
}
}
if (C[l] > 0) l++; //处理最高位是否进位
//如999+1=1000 此时长度为l+1
for (i = 0; i < l; i++)
D[i] = C[l - i - 1];
j = 0;
for (i = 0; i < l; i++)
{
if (D[i] == 0)
{
counter++;
continue;
}
else
{
c[j++] = D[i] + '0';
goto o;
}
}
o:
for (j; j < l - counter; j++)
{
c[j] = D[++i] + '0';
}
c[j] = '\0';
if (c[0] == '\0')
{
c[0] = '0';
c[1] = '\0';
}
return;
}
//高精度减法
void minus(char *a, char *b, char *c)
{
int i, l;
int length1, length2;
int A[10005] = { 0 }, B[10005] = { 0 }, C[10005] = { 0 }, D[10005] = { 0 };
length1 = strlen(a);
length2 = strlen(b);
if (length1 > length2)
{
p:
if (length1 >= length2)//取A和B较长的长度
l = length1;
else
l = length2;
for (i = 0; i < length1; i++)//将字符串转化为整形数组
{
A[i] = a[length1 - i - 1] - '0';
}
for (i = 0; i < length2; i++)
{
B[i] = b[length2 - 1 - i] - '0';
}
for (i = 0; i < l; i++)
{
C[i] += (A[i] - B[i]);
if (C[i] < 0) //借位操作
{
C[i + 1]--;
C[i] += 10;
}
}
while (C[l] == 0 && l > 0)
{
l--;
}
for (i = 0; i < l + 1; i++)
c[i] = C[l - i] + '0';
c[l + 1] = '\0';for (i = 0; i <= l; i++)
return;
}
else if (length1 < length2)
{
q:
if (length1 >= length2)//取A和B较长的长度
l = length1;
else
l = length2;
for (i = 0; i < length1; i++)//将字符串转化为整形数组
{
A[i] = a[length1 - i - 1] - '0';
}
for (i = 0; i < length2; i++)
{
B[i] = b[length2 - 1 - i] - '0';
}
for (i = 0; i < l; i++)
{
C[i] += (B[i] - A[i]);
if (C[i] < 0) //借位操作
{
C[i + 1]--;
C[i] += 10;
}
}
while (C[l] == 0 && l > 0)
{
l--;
}
c[0] = '-';
for (i = 1; i < l + 2; i++)
c[i] = C[l - i + 1] + '0';
c[l + 2] = '\0';
return;
}
else
{
int P = strcmp(a, b);
if (P > 0)
goto p;
else if (P < 0)
goto q;
else
{
for (i = 0; i < length1; i++)
if (i == length1 - 1)
{
c[0] = '0';
c[1] = '\0';
}
}
}
}
//高精度乘法
void multiply(char* a, char* b, char* c)
{
int i, j, ca, cb, *s;
ca = strlen(a);
cb = strlen(b);
s = (int*) malloc(sizeof(int) * (ca + cb));
for (i = 0; i < ca + cb; i++)
s[i] = 0;
for (i = 0; i < ca; i++)
for (j = 0; j < cb; j++)
s[i + j + 1] += (a[i] - '0') * (b[j] - '0');
for (i = ca + cb - 1; i >= 0; i--)
if (s[i] >= 10)
{
s[i - 1] += s[i] / 10;
s[i] %= 10;
}
i = 0;
while (s[i] == 0)
i++;
for (j = 0; i < ca + cb; i++, j++)
c[j] = s[i] + '0';
c[j] = '\0';
free(s);
}
#include <iostream>
#include <string>
using namespace std;
inline int compare(string str1,string str2) {//相等返回0，大于返回1，小于返回-1
if (str1.size()>str2.size()) return 1; //长度长的整数大于长度小的整数
else if (str1.size()<str2.size()) return -1;
else return str1.compare(str2); //若长度相等，则头到尾按位比较
}
string SUB_INT(string str1,string str2);
string ADD_INT(string str1,string str2) {//高精度加法
int sign=1; //sign 为符号位
string str;
if (str1[0]=='-') {
if (str2[0]=='-') {
sign=-1;
str=ADD_INT(str1.erase(0,1),str2.erase(0,1));
} else {
str=SUB_INT(str2,str1.erase(0,1));
}
} else {
if (str2[0]=='-') {
str=SUB_INT(str1,str2.erase(0,1));
} else { //把两个整数对齐，短整数前面加0补齐
string::size_type L1,L2;
int i;
L1=str1.size();
L2=str2.size();
if (L1<L2) {
for (i=1;i<=L2-L1;i++) str1="0"+str1;
} else {
for (i=1;i<=L1-L2;i++) str2="0"+str2;
}
int int1=0,int2=0; //int2 记录进位
for (i=str1.size()-1;i>=0;i--) {
int1=(int(str1[i])-'0'+int(str2[i])-'0'+int2)%10;
int2=(int(str1[i])-'0'+int(str2[i])-'0'+int2)/10;
str=char(int1+'0')+str;
}
if (int2!=0) str=char(int2+'0')+str;
}
}
//运算后处理符号位
if ((sign==-1)&&(str[0]!='0')) str="-"+str;
return str;
}
string SUB_INT(string str1,string str2) {//高精度减法
int sign=1; //sign 为符号位
string str;
int i,j;
if (str2[0]=='-') {
str=ADD_INT(str1,str2.erase(0,1));
} else {
int res=compare(str1,str2);
if (res==0) return "0";
if (res<0) {
sign=-1;
string temp =str1;
str1=str2;
str2=temp;
}
string::size_type tempint;
tempint=str1.size()-str2.size();
for (i=str2.size()-1;i>=0;i--) {
if (str1[i+tempint]<str2[i]) {
j=1;
while (1) {//zhao4zhong1添加
if (str1[i+tempint-j]=='0') {
str1[i+tempint-j]='9';
j++;
} else {
str1[i+tempint-j]=char(int(str1[i+tempint-j])-1);
break;
}
}
str=char(str1[i+tempint]-str2[i]+':')+str;
} else {
str=char(str1[i+tempint]-str2[i]+'0')+str;
}
}
for (i=tempint-1;i>=0;i--) str=str1[i]+str;
}
//去除结果中多余的前导0
str.erase(0,str.find_first_not_of('0'));
if (str.empty()) str="0";
if ((sign==-1) && (str[0]!='0')) str ="-"+str;
return str;
}
string MUL_INT(string str1,string str2) {//高精度乘法
int sign=1; //sign 为符号位
string str;
if (str1[0]=='-') {
sign*=-1;
str1 =str1.erase(0,1);
}
if (str2[0]=='-') {
sign*=-1;
str2 =str2.erase(0,1);
}
int i,j;
string::size_type L1,L2;
L1=str1.size();
L2=str2.size();
for (i=L2-1;i>=0;i--) { //模拟手工乘法竖式
string tempstr;
int int1=0,int2=0,int3=int(str2[i])-'0';
if (int3!=0) {
for (j=1;j<=(int)(L2-1-i);j++) tempstr="0"+tempstr;
for (j=L1-1;j>=0;j--) {
int1=(int3*(int(str1[j])-'0')+int2)%10;
int2=(int3*(int(str1[j])-'0')+int2)/10;
tempstr=char(int1+'0')+tempstr;
}
if (int2!=0) tempstr=char(int2+'0')+tempstr;
}
str=ADD_INT(str,tempstr);
}
//去除结果中的前导0
str.erase(0,str.find_first_not_of('0'));
if (str.empty()) str="0";
if ((sign==-1) && (str[0]!='0')) str="-"+str;
return str;
}
string DIVIDE_INT(string str1,string str2,int flag) {//高精度除法。flag==1时,返回商; flag==0时,返回余数
string quotient,residue; //定义商和余数
int sign1=1,sign2=1;
if (str2 == "0") { //判断除数是否为0
quotient= "ERROR!";
residue = "ERROR!";
if (flag==1) return quotient;
else return residue ;
}
if (str1=="0") { //判断被除数是否为0
quotient="0";
residue ="0";
}
if (str1[0]=='-') {
str1 = str1.erase(0,1);
sign1 *= -1;
sign2 = -1;
}
if (str2[0]=='-') {
str2 = str2.erase(0,1);
sign1 *= -1;
}
int res=compare(str1,str2);
if (res<0) {
quotient="0";
residue =str1;
} else if (res == 0) {
quotient="1";
residue ="0";
} else {
string::size_type L1,L2;
L1=str1.size();
L2=str2.size();
string tempstr;
tempstr.append(str1,0,L2-1);
for (int i=L2-1;i<L1;i++) { //模拟手工除法竖式
tempstr=tempstr+str1[i];
tempstr.erase(0,tempstr.find_first_not_of('0'));//zhao4zhong1添加
if (tempstr.empty()) tempstr="0";//zhao4zhong1添加
for (char ch='9';ch>='0';ch--) { //试商
string str;
str=str+ch;
if (compare(MUL_INT(str2,str),tempstr)<=0) {
quotient=quotient+ch;
tempstr =SUB_INT(tempstr,MUL_INT(str2,str));
break;
}
}
}
residue=tempstr;
}
//去除结果中的前导0
quotient.erase(0,quotient.find_first_not_of('0'));
if (quotient.empty()) quotient="0";
if ((sign1==-1)&&(quotient[0]!='0')) quotient="-"+quotient;
if ((sign2==-1)&&(residue [0]!='0')) residue ="-"+residue ;
if (flag==1) return quotient;
else return residue ;
}
string DIV_INT(string str1,string str2) {//高精度除法,返回商
return DIVIDE_INT(str1,str2,1);
}
string MOD_INT(string str1,string str2) {//高精度除法,返回余数
return DIVIDE_INT(str1,str2,0);
}
int main() {
char ch;
string s1,s2,res;
while (cin>>s1>>ch>>s2) {
switch (ch) {
case '+':res=ADD_INT(s1,s2);break;
case '-':res=SUB_INT(s1,s2);break;
case '*':res=MUL_INT(s1,s2);break;
case '/':res=DIV_INT(s1,s2);break;
case '%':res=MOD_INT(s1,s2);break;
default : break;
}
cout<<res<<endl;
}
return(0);
}
