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

偏执的太偏执、 2023-05-31 06:42 6阅读 0赞

### 【大数相加】   【代码一】 ###

/*********************************
    *   日期：2015-01-28
    *   作者：SJF0115
    *   题目: 大数加法(高精度加法)
    *   博客：
    **********************************/
    #include <iostream>
    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<<result<<endl;
        return 0;
    }

## ##

### 【代码二】 ###

/*********************************
    *   日期：2015-01-28
    *   作者：SJF0115
    *   题目: 大数加法(高精度加法)
    *   博客：
    **********************************/
    #include <iostream>
    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<<result<<endl;
        return 0;
    }

### 【代码三】 ###

#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;
    }

### 【代码二】 ###

/* 
    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 <iostream>
    #include <cstring>
    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<<result<<endl;
        return 0;
    }<span style="color:#ff0000;">
    </span>

### 【代码二】 ###

#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 <iostream>
    #include <string>
    #include <algorithm>
    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 length
    int 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 function
    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;
    }
    // big number add function
    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;
    }
    // 移位
    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<<result<<endl;
        return 0;
    }

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/43226505][https_blog.csdn.net_SunnyYoona_article_details_43226505]

[https_blog.csdn.net_SunnyYoona_article_details_43226505]: https://blog.csdn.net/SunnyYoona/article/details/43226505