[算法系列之八]大数问题（高精度运算）-白红宇

【大数相加】

【代码一】

/**********************************   日期：2015-01-28*   作者：SJF0115*   题目: 大数加法(高精度加法)*   博客：**********************************/#include 
     
      using namespace std;string AddString(string num1,string num2){    int len1 = num1.length();    int len2 = num2.length();    // 容错处理    if(len1 <= 0){        return num2;    }//if    if(len2 <= 0){        return num1;    }    string result;    int i = len1-1,j = len2-1;    int a,b,sum,carry = 0;    // 倒序相加    while(i >= 0 || j >= 0 || carry > 0){        a = i >= 0 ? num1[i] - '0' : 0;        b = j >= 0 ? num2[j] - '0' : 0;        // 按位相加并加上进位        sum = a + b + carry;        // 进位        carry = sum / 10;        result.insert(result.begin(),sum % 10 + '0');        --i;        --j;    }//while    return result;}int main(){    string num1("72");    string num2("874");    string result = AddString(num1,num2);    // 输出    cout<
      
       <

【代码二】

/**********************************   日期：2015-01-28*   作者：SJF0115*   题目: 大数加法(高精度加法)*   博客：**********************************/#include 
     
      using namespace std;string AddString(string num1,string num2){    int len1 = num1.length();    int len2 = num2.length();    int max = len1 > len2 ? (len1 + 2) : (len2 + 2);    char* result = new char[max];    int index = 0;    int i = len1 - 1,j = len2 - 1;    int numA,numB,carry = 0,sum = 0;    //加法    while(i >= 0 || j >= 0 || carry > 0){        numA = i >= 0 ? (num1[i] - '0') : 0;        numB = j >= 0 ? (num2[j] - '0') : 0;        sum = numA + numB + carry;        carry = sum / 10;        result[index++] = sum % 10 + '0';        --i;        --j;    }//while    result[index] = '\0';    //反转    for(i = 0,j = index - 1;i < j;++i,--j){        char temp = result[i];        result[i] = result[j];        result[j] = temp;    }//for    return string(result);}int main(){    string num1("872");    string num2("874");    string result = AddString(num1,num2);    // 输出    cout<
      
       <

【代码三】

[cpp]
 #include<stdio.h>   
 #include<string.h>   
    
 char a[10001],b[10001],sum[10002];   
    
 int BigIntegerAdd(){   
     //两个数的长度   
     int lena = strlen(a);   
     int lenb = strlen(b);   
     //进位标记   
     int c = 0;   
     int i,j,k;   
     //初始化数组sum   
     memset(sum,0,10001);   
     //倒序相加   
     k = 0;   
     for(i = lena-1,j = lenb-1;i >= 0 && j >= 0;i--,j--){   
         sum[k] = a[i] + b[j] - '0' + c;   
         c = 0;   
         //如果相加大于等于10   
         if(sum[k] > '9'){   
             sum[k] -= 10;   
             c = 1;   
         }   
         k++;   
     }   
     //a > b   
     while(i >= 0){   
         sum[k] = a[i] + c;   
         c = 0;   
         //如果相加大于等于10   
         if(sum[k] > '9'){   
             sum[k] -= 10;   
             c = 1;   
         }   
         k++;   
         i--;   
     }   
     //b > a   
     while(j >= 0){   
         sum[k] = b[j] + c;   
         c = 0;   
         //如果相加大于等于10   
         if(sum[k] > '9'){   
             sum[k] -= 10;   
             c = 1;   
         }   
         k++;   
         j--;   
     }   
     //如果最后两个数相加有进位的情况   
     //例如：67 + 51：5+6有进位   
     if(c == 1){   
         sum[k++] = '1';   
     }   
     //翻转   
     char temp;   
     for(i = 0,j = k-1;i < j;i++,j--){   
         temp = sum[i];   
         sum[i] = sum[j];   
         sum[j] = temp;   
     }   
     return 0;   
 }   
    
 int main(){   
     while(scanf("%s %s",a,b) != EOF){   
         BigIntegerAdd();   
         puts(sum);   
     }   
 }   

【大数相减】

【代码一】

string MinusString(string num1, string num2) {    int len1 = num1.length();    int len2 = num2.length();    // 相等    if(num1 == num2){        return "0";    }//if    // 正负    bool positive = true;    if(len1 < len2 || (len1 == len2 && num1 < num2)){        positive = false;        // 交换使之num1 > num2        string tmp = num1;        num1 = num2;        num2 = tmp;        int temp = len1;        len1 = len2;        len2 = temp;    }//if    string result;    int i = len1 - 1,j = len2 - 1;    int a,b,sum,carray = 0;    // 从低位到高位对位做减法    while(i >= 0 || j >= 0){        a = i >= 0 ? num1[i] - '0' : 0;        b = j >= 0 ? num2[j] - '0' : 0;        sum = a - b + carray;        carray = 0;        // 不够减        if(sum < 0){            sum += 10;            carray = -1;        }//if        result.insert(result.begin(),sum + '0');        --i;        --j;    }//while    // 删除前导0    string::iterator it = result.begin();    while(it != result.end() && *it == '0'){        ++it;    }//while    result.erase(result.begin(),it);    return positive ? result : "-"+result;}

【代码二】

[cpp]
 /*  
 1.比较减数与被减数的长度,确定正负号  
 2.模拟减法运算  
     (1)a[i] == b[j]   
     (2)a[i] < b[j] //借位  
     (3)a[i] > b[j]   
  */   
 #include<stdio.h>   
 #include<string.h>   
    
 char a[10001],b[10001],sum[10001],temp[10001];   
    
 int BigIntegerMinus(){   
     //两个数的长度   
     int lena = strlen(a);   
     int lenb = strlen(b);   
     //借位标记   
     int c = 0;   
     int i,j,k,positive = 1;   
     //判断正负号   
     if(lena < lenb || (lena == lenb && strcmp(a,b) < 0) ){   
         strcpy(temp,a);   
         strcpy(a,b);   
         strcpy(b,temp);   
         positive = -1;//负号   
         lena = strlen(a);   
         lenb = strlen(b);   
     }   
     //倒序相减    
     k = 0;     
     for(i = lena-1,j = lenb-1;i >= 0 && j >= 0;i--,j--){     
         sum[k] = a[i] - b[j] + '0' + c;     
         c = 0;     
         //如果相减小于0     
         if(sum[k] < '0'){     
             sum[k] += 10;     
             c = -1;     
         }     
         k++;     
     }     
     //a > b     
     while(i >= 0){     
         sum[k] = a[i] + c;     
         c = 0;     
         //如果相减小于0     
         if(sum[k] < '0'){     
             sum[k] += 10;     
             c = -1;     
         }     
         k++;     
         i--;     
     }     
     //b > a     
     while(j >= 0){     
         sum[k] = b[j] + c;     
         c = 0;     
         //如果相减小于0     
         if(sum[k] < '0'){     
             sum[k] += 10;     
             c = -1;     
         }     
         k++;     
         j--;     
     }   
     int index = k - 1;   
     //检索高位，有可能相减为0   
     while(sum[index] == '0' && index > 0){   
         index--;   
     }   
     //正号   
     if(positive == 1){   
         sum[index+1] = '\0';   
     }   
     //负号   
     else{   
         sum[++index] = '-';   
         sum[index+1] = '\0';   
     }   
     //翻转   
     char t;   
     for(i = 0,j = index;i < j;i++,j--){   
         t = sum[i];   
         sum[i] = sum[j];   
         sum[j] = t;   
     }   
     return 0;   
 }   
    
 int main(){   
     while(scanf("%s %s",a,b) != EOF){   
         BigIntegerMinus();   
         puts(sum);   
     }   
 }   

【大数乘法】

【代码一】

/**********************************   日期：2015-01-28*   作者：SJF0115*   题目: 高精度乘法(大数乘法)*   博客：**********************************/#include 
     
      #include 
      
       using namespace std;string MultiplyString(string num1, string num2) {    int len1 = num1.length();    int len2 = num2.length();    // 容错处理    if(len1 <= 0 || len2 <= 0){        return "";    }//if    int sum = 0;    int len3 = len1 + len2;    char result[len3];    memset(result,'0',sizeof(result[0])*(len3+1));    for(int i = len1 - 1,m = 0;i >= 0;--i,++m){        for(int j = len2 - 1,n = 0;j >= 0;--j,++n){            sum = (num1[i] - '0') * (num2[j] - '0') + result[m+n] - '0';            result[m+n] = sum % 10 + '0';            // 进位            result[m+n+1] += sum / 10;        }//for    }//for    //去掉前导0 确定乘积的位数    while(result[len3] == '0' && len3 > 0){        --len3;    }//while    //注意：加'\0'    result[len3+1] = '\0';    //翻转    int temp;    for(int i = 0,j = len3;i < j;++i,--j){        temp = result[i];        result[i] = result[j];        result[j] = temp;    }//for    return string(result);}int main(){    string num1("2");    string num2("123");    string result = MultiplyString(num1,num2);    // 输出    cout<
       
        <

【代码二】

[cpp]
 #include<stdio.h>   
 #include<string.h>   
    
 char a[10001],b[10001],c[20002];   
    
 int BigIntegerMulti()   
 {   
     int i,j,lena,lenb,lenc;   
     //初始化   
     memset(c,'0',20002);   
     //两个数的长度   
     lena = strlen(a);   
     lenb = strlen(b);   
     //乘积最大位数   
     lenc = lena + lenb - 1;   
     //翻转     
     char temp;     
     for(i = 0,j = lena-1;i < j;i++,j--){     
         temp = a[i];     
         a[i] = a[j];     
         a[j] = temp;     
     }     
     for(i = 0,j = lenb-1;i < j;i++,j--){     
         temp = b[i];     
         b[i] = b[j];     
         b[j] = temp;     
     }    
     //倒序相乘   
     /*  
           123  
         *  54  
         ------  
           492  
          615  
         -----  
          6642   
     */   
     int t;   
     for(i = 0;i < lena;i++){   
         for(j = 0;j < lenb;j++){   
             /* c[i+j] = (a[i] - '0') * (b[j] - '0') + c[i+j];   
                9 * 9 + '0' 超出char范围越界所以设置一个int临时变量t    */   
             t = (a[i] - '0') * (b[j] - '0') + c[i+j] - '0';   
             //进位   
             c[i+j+1] = t / 10 + c[i+j+1];   
             c[i+j] = t % 10 + '0';   
         }   
     }   
     //确定乘积的位数   
     while(c[lenc] == '0' && lenc >0){   
         lenc--;   
     }   
     //注意：加'\0'   
     c[lenc+1] = '\0';   
     //翻转   
     for(i = 0,j = lenc;i < j;i++,j--){     
         temp = c[i];     
         c[i] = c[j];     
         c[j] = temp;     
     }    
     return 0;   
 }   
    
 int main(){   
     while(scanf("%s %s",a,b) != EOF){   
         BigIntegerMulti();   
         puts(c);   
     }   
     return 0;   
 }   

【代码三】

/**********************************   日期：2015-01-29*   作者：SJF0115*   题目: Karatsuba快速相乘算法*   博客：**********************************/#include 
    
     #include 
     
      #include 
      
       using namespace std;// given two unequal sized bit strings, converts them to// same length by adding leading 0s in the smaller string. Returns the// the new lengthint MakeSameLen(string& num1,string& num2){    int len1 = num1.length();    int len2 = num2.length();    if(len1 < len2){        for(int i = 0;i < len2 - len1;++i){            num1 = "0" + num1;        }//for        return len2;    }//if    else{        for(int i = 0;i < len1 - len2;++i){            num2 = "0" + num2;        }//for        return len1;    }//else}// big number minus functionstring MinusString(string num1, string num2) {    int len1 = num1.length();    int len2 = num2.length();    // 相等    if(num1 == num2){        return "0";    }//if    // 正负    bool positive = true;    if(len1 < len2 || (len1 == len2 && num1 < num2)){        positive = false;        // 交换使之num1 > num2        string tmp = num1;        num1 = num2;        num2 = tmp;        int temp = len1;        len1 = len2;        len2 = temp;    }//if    string result;    int i = len1 - 1,j = len2 - 1;    int a,b,sum,carray = 0;    // 从低位到高位对位做减法    while(i >= 0 || j >= 0){        a = i >= 0 ? num1[i] - '0' : 0;        b = j >= 0 ? num2[j] - '0' : 0;        sum = a - b + carray;        carray = 0;        // 不够减        if(sum < 0){            sum += 10;            carray = -1;        }//if        result.insert(result.begin(),sum + '0');        --i;        --j;    }//while    // 删除前导0    string::iterator it = result.begin();    while(it != result.end() && *it == '0'){        ++it;    }//while    result.erase(result.begin(),it);    return positive ? result : "-"+result;}// big number add functionstring AddString(string num1,string num2){    int len1 = num1.length();    int len2 = num2.length();    // 容错处理    if(len1 <= 0){        return num2;    }//if    if(len2 <= 0){        return num1;    }    string result;    int i = len1-1,j = len2-1;    int a,b,sum,carry = 0;    // 倒序相加    while(i >= 0 || j >= 0 || carry > 0){        a = i >= 0 ? num1[i] - '0' : 0;        b = j >= 0 ? num2[j] - '0' : 0;        // 按位相加并加上进位        sum = a + b + carry;        // 进位        carry = sum / 10;        result.insert(result.begin(),sum % 10 + '0');        --i;        --j;    }//while    return result;}// 移位string ShiftString(string num,int len){    if(num == "0"){        return num;    }//if    for(int i = 0;i < len;++i){        num += "0";    }//for    return num;}// Karatsuba快速相乘算法string KaratsubaMultiply(string num1, string num2) {    int len = MakeSameLen(num1,num2);    if(len == 0){        return 0;    }//if    // all digit are one    if(len == 1){        return to_string((num1[0] - '0')*(num2[0] - '0'));    }//if    int mid = len / 2;    // Find the first half and second half of first string.    string x1 = num1.substr(0,mid);    string x0 = num1.substr(mid,len - mid);    // Find the first half and second half of second string    string y1 = num2.substr(0,mid);    string y0 = num2.substr(mid,len - mid);    // Recursively computer    string z0 = KaratsubaMultiply(x0,y0);    string z1 = KaratsubaMultiply(AddString(x1,x0),AddString(y1,y0));    string z2 = KaratsubaMultiply(x1,y1);    // (z2*10^(2*m))+((z1-z2-z0)*10^(m))+(z0)    // z2*10^(2*m)    string r1 = ShiftString(z2,2*(len - mid));    // (z1-z2-z0)*10^(m)    string r2 = ShiftString(MinusString(MinusString(z1,z2),z0),len - mid);    return  AddString(AddString(r1,r2),z0);}int main(){    string num1("12345001");    string num2("1006789");    string result = KaratsubaMultiply(num1,num2);    // 输出    cout<
       
        <

自己写的如有问题，请告知一下。