大数算法

2022/05/09

一般的程序设计语言都只能保存有限大小的数字类型,如果遇到超过所能表示的最大值就会发生溢出导致计算错误,对于过大的数字一般使用字符串表示,对于字符串表示的数字进行四则运算则称为大数算法。大数算法不算很难但是综合性较高,在刷题的时候经常遇到,听说在面试的时候也经常被问到。大数算法的核心就是模拟,从最低位开始一位一位的操作并且将进位与借位保存下来,加入下一轮操作。

1. 大数相加

假设ab为两个字符串表示两个正数,要求以字符串的形式返回它们的和

string addStrings(string a, string b){
    string ans = ""; 
    int carry = 0;
    int p1 = a.size()-1, p2 = b.size()-1;   
    while(p1 >= 0 || p2 >= 0 || carry != 0){
        int ta = p1 < a.size() ? a[p1]-48 : 0;p1--;
        int tb = p2 < b.size() ? b[p2]-48 : 0;p2--;
        int t = ta + tb + carry;
        ans += (t % 10) + '0';
        carry = t / 10;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

Leetcode上面的 Add Strings就是大数相加,可以验证自己写的对不对

2. 大数相减

假设ab为两个字符串表示两个正数,要求以字符串的形式返回它们的差

大数相减和大数相加过程及其差不多,但是有几点需要注意的

  1. 相减可能是产生负数,处理起来比较麻烦,可以先对输入的两个数进行比较用一个flag表示结果是正数还是负数,然后将较大的那个数作为被减数,较小的最为减数,最后根据flag来加或者不加符号。
  2. 先相减后可能回保留先导0, 比如000001,这些先导零应该要去除
// 两个大数相比较,如果位数不同则位数多的较大
bool compareStrings(const string& a, const string& b){
    if(a.size() != b.size()){
        return a.size() > b.size();
    }
    for(int i=0; i < a.size(); i++){
        if(a[i] != b[i])
            return a[i] > b[i];
    }
    return false;       // 如果相等就返回false
}

// 两个正数相减
string minStrings(string a, string b){
    // 用于标记结果是正好还是符号
    bool flag = true;
    // 保证a大于b
    if(!compare(a,b)){
        flag = false;
        string temp = a;
        a = b;
        b = temp;
    }
    int carry = 0;  // 保留借位
    int p1 = a.size()-1, p2 = b.size()-1;
    string ans = "";
    while(p1 >= 0 || p2 >= 0 || carry != 0){
        int ta = p1 < a.size() ? a[p1--]-48 : 0;
        int tb = p2 < b.size() ? b[p2--]-48 : 0;
        int t = ta - tb -carry;     // 因为是a-b,所以借位是在a上面借的
        ans += ((10+t) % 10) + '0';
        carry = t < 0 ? 1: 0;
    }
    reverse(ans.begin(), ans.end());
    // 去除先导0
    for(int i = 0; i < ans.size(); i++){
        if(ans[i] != '0'){
            ans = ans.substr(i);
            break;
        }
    }
    if(!flag){      // 如果是负数则添加负号
        ans = "-" + ans;
    }
    return ans;
}

拼题A上面有一道包含大数相减的题目1065 A+B and C可以验证自己写的对不对。

3. 大数相乘

大数相乘有多种解决方法,其中最简单的就是乘数是多少就把被乘数相加多少遍,比如5 × 3就可以写作5 + 5 + 5,然后按照大数相加的方法把他们加起来就可以了,但当乘数太大了算法的时间复杂度就非常高了。我们还可以按位相乘然后再相加,比如1233 × 42可以写成1233 × 2 + 1233 × 40

class Solution {
public:
    // 输入的两个数都是反向的
    string add(string num1, string num2){
        int n1 = 0, n2 = 0, carry = 0;
        string res = "";
        while(n1 < num1.size() || n2 < num2.size() || carry != 0){
            int x = n1 >= num1.size() ? 0: num1[n1++] - '0';
            int y = n2 >= num2.size() ? 0: num2[n2++] - '0';
            int z = x + y + carry;
            res.push_back('0' + z % 10 );
            carry = z / 10;                   
        }
        return res;
    }
    // 和之前的加法一样,后端对齐模拟相乘
    string multiply(string num1, string num2) {
        int n1 = num1.size() -1 ;
        string res = "0";
        for(int i = n1; i >=0; i--){
            int n2 = num2.size() - 1;
            int x = num1[i] - '0';
            int carry = 0;           
            string t = "";
            for(int j = i; j < n1; j++){        // 补零
                t.push_back('0');
            }            
            while(n2 >= 0 || carry != 0){
                int y = n2 < 0? 0: num2[n2] - '0';
                int z = x * y + carry;
                t.push_back('0' + z % 10);
                carry = z / 10;
                n2 --;
            }
            res = add(res, t);
        }
        reverse(res.begin(), res.end());
        for(const auto i:res){
            if(i != '0'){
                return res;
            }
            return "0";
        }
        return res;
    }
};

还有一种方法就是直接将每一位相乘,然后将结果保存在数组当中,假设num1m位、num2n位则结果ans最多有m+n位,所以可以初始化一个m+n位的数组用于保存每一位的数字,如果该位的数字大于10则向前进位,最后将结果以字符串的形式输出

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1[0] == '0' || num2[0] == '0'){
            return "0";
        }
        int m = num1.size(), n = num2.size();
        vector<int>ansArr(m+n, 0);     // 用于保存结果的各个位
        for(int i = m -1; i >= 0; i--){
            int x = num1[i] - '0';
            for(int j = n - 1; j >=0; j--){
                int y = num2[j] - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for(int i = m + n -1; i > 0; i--){
            ansArr[i-1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        string ans = "";
        while(index < m + n){
            ans.push_back('0' + ansArr[index++]);
        }
        return ans;
    }
};

Leetcode上面的43. Multiply Strings就是大数相乘,可以验证自己写的对不对

4. 大数相除

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        long numeratorLong = numerator;
        long denominatorLong = denominator;
        if (numeratorLong % denominatorLong == 0) {
            return to_string(numeratorLong / denominatorLong);
        }

        string ans;
        if (numeratorLong < 0 ^ denominatorLong < 0) {
            ans.push_back('-');
        }

        // 整数部分
        numeratorLong = abs(numeratorLong);
        denominatorLong = abs(denominatorLong);
        long integerPart = numeratorLong / denominatorLong;
        ans += to_string(integerPart);
        ans.push_back('.');

        // 小数部分
        string fractionPart;
        unordered_map<long, int> remainderIndexMap;
        long remainder = numeratorLong % denominatorLong;
        int index = 0;
        while (remainder != 0 && !remainderIndexMap.count(remainder)) {
            remainderIndexMap[remainder] = index;
            remainder *= 10;
            fractionPart += to_string(remainder / denominatorLong);
            remainder %= denominatorLong;
            index++;
        }
        if (remainder != 0) { // 有循环节
            int insertIndex = remainderIndexMap[remainder];
            fractionPart = fractionPart.substr(0,insertIndex) + '(' + fractionPart.substr(insertIndex);
            fractionPart.push_back(')');
        }
        ans += fractionPart;

        return ans;
    }
};

Leetcode上面的166. Fraction to Recurring Decimal就是大数相除,可以验证自己写的对不对