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

/*********************************
*   日期：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] = '';
    //反转
    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;
}

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,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. 1.比较减数与被减数的长度,确定正负号?
2. 2.模拟减法运算?
3. ????(1)a[i]?==?b[j]??
4. ????(2)a[i]?<?b[j]?//借位?
5. ????(3)a[i]?>?b[j]??
6. ?*/??
7. #include<stdio.h>??
8. #include<string.h>??
9. ??
10. int?BigIntegerMinus(){??
11. //两个数的长度??
12. int?lena?=?strlen(a);??
13. int?lenb?=?strlen(b);??
14. //借位标记??
15. int?c?=?0;??
16. //判断正负号??
17. if(lena?<?lenb?||?(lena?==?lenb?&&?strcmp(a,b)?<?0)?){??
18. ????????strcpy(temp,a);??
19. ????????strcpy(a,b);??
20. ????????strcpy(b,temp);??
21. ????????positive?=?-1;//负号??
22. ????????lena?=?strlen(a);??
23. ????????lenb?=?strlen(b);??
24. //倒序相减???
25. ????k?=?0;????
26. ????????sum[k]?=?a[i]?-?b[j]?+?'0'?+?c;????
27. ????????c?=?0;????
28. //如果相减小于0????
29. if(sum[k]?<?'0'){????
30. ????????????sum[k]?+=?10;????
31. ????????????c?=?-1;????
32. ????????}????
33. ????????k++;????
34. ????}????
35. //a?>?b????
36. while(i?>=?0){????
37. ????????sum[k]?=?a[i]?+?c;????
38. ????????c?=?0;????
39. //如果相减小于0????
40. if(sum[k]?<?'0'){????
41. ????????????sum[k]?+=?10;????
42. ????????????c?=?-1;????
43. ????????}????
44. ????????k++;????
45. ????????i--;????
46. //b?>?a????
47. while(j?>=?0){????
48. ????????sum[k]?=?b[j]?+?c;????
49. ????????j--;????
50. int?index?=?k?-?1;??
51. //检索高位，有可能相减为0??
52. while(sum[index]?==?'0'?&&?index?>?0){??
53. ????????index--;??
54. //正号??
55. if(positive?==?1){??
56. ????????sum[index+1]?=?'';??
57. //负号??
58. else{??
59. ????????sum[++index]?=?'-';??
60. ????????sum[index+1]?=?'';??
61. //翻转??
62. char?t;??
63. ????????t?=?sum[i];??
64. ????????sum[i]?=?sum[j];??
65. ????????sum[j]?=?t;??
66. return?0;??
67. }??
68. int?main(){??
69. ????????BigIntegerMinus();??
70. ????????puts(sum);??
71. }??

【大数乘法】

【代码一】

/*********************************
*   日期：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
    //注意：加''
    result[len3+1] = '';
    //翻转
    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>

【代码二】

int?BigIntegerMulti()??
1. {??
2. //初始化??
3. ????memset(c,'0',20002);??
4. ????lena?=?strlen(a);??
5. ????lenb?=?strlen(b);??
6. //乘积最大位数??
7. ????lenc?=?lena?+?lenb?-?1;??
8. //翻转????
9. char?temp;????
10. ????????temp?=?a[i];????
11. ????????a[i]?=?a[j];????
12. ????????a[j]?=?temp;????
13. ????????temp?=?b[i];????
14. ????????b[i]?=?b[j];????
15. ????????b[j]?=?temp;????
16. ????}???
17. //倒序相乘??
18. ??????????123?
19. ????????*??54?
20. ????????------?
21. ??????????492?
22. ?????????615?
23. ????????-----?
24. ?????????6642??
25. ????*/??
26. int?t;??
27. for(i?=?0;i?<?lena;i++){??
28. for(j?=?0;j?<?lenb;j++){??
29. ????????????/*?c[i+j]?=?(a[i]?-?'0')?*?(b[j]?-?'0')?+?c[i+j];??
30. ???????????????9?*?9?+?'0'?超出char范围越界所以设置一个int临时变量t????*/??
31. ????????????t?=?(a[i]?-?'0')?*?(b[j]?-?'0')?+?c[i+j]?-?'0';??
32. ????????????//进位??
33. ????????????c[i+j+1]?=?t?/?10?+?c[i+j+1];??
34. ????????????c[i+j]?=?t?%?10?+?'0';??
35. //确定乘积的位数??
36. while(c[lenc]?==?'0'?&&?lenc?>0){??
37. ????????lenc--;??
38. //注意：加''??
39. ????c[lenc+1]?=?'';??
40. ????????temp?=?c[i];????
41. ????????c[i]?=?c[j];????
42. ????????c[j]?=?temp;????
43. ????}???
44. ????????BigIntegerMulti();??
45. ????????puts(c);??
46. }??

【代码三】

/*********************************
*   日期：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,it);
    return positive ? result : "-"+result;
}
// big number add function
string AddString(string num1,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;
}

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!