L5_03 C++ 高精度运算

一、数组模拟高精度加法

1.1 算法思路

将大数以字符串形式输入，转换为数组存储，逐位相加。

1.2 代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string add(string num1, string num2) {
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    
    string result;
    int carry = 0;
    int maxLen = max(num1.size(), num2.size());
    
    for (int i = 0; i < maxLen || carry; i++) {
        int digit1 = (i < num1.size()) ? num1[i] - '0' : 0;
        int digit2 = (i < num2.size()) ? num2[i] - '0' : 0;
        int sum = digit1 + digit2 + carry;
        carry = sum / 10;
        result.push_back(sum % 10 + '0');
    }
    
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    string a = "123456789";
    string b = "987654321";
    cout << add(a, b) << endl;  // 输出1111111110
    return 0;
}

---

二、数组模拟高精度减法

2.1 算法思路

确保被减数大于等于减数，逐位相减，处理借位。

2.2 代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isGreaterOrEqual(string a, string b) {
    if (a.size() != b.size()) {
        return a.size() > b.size();
    }
    return a >= b;
}

string subtract(string num1, string num2) {
    if (!isGreaterOrEqual(num1, num2)) {
        return "-" + subtract(num2, num1);
    }
    
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    
    string result;
    int borrow = 0;
    
    for (int i = 0; i < num1.size(); i++) {
        int digit1 = num1[i] - '0';
        int digit2 = (i < num2.size()) ? num2[i] - '0' : 0;
        int diff = digit1 - digit2 - borrow;
        borrow = 0;
        
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        }
        
        result.push_back(diff + '0');
    }
    
    while (result.size() > 1 && result.back() == '0') {
        result.pop_back();
    }
    
    reverse(result.begin(), result.end());
    return result;
}

---

三、数组模拟高精度乘法

3.1 算法思路

使用竖式乘法，逐位相乘，累加结果。

3.2 代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    
    int len1 = num1.size();
    int len2 = num2.size();
    string result(len1 + len2, '0');
    
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int product = (num1[i] - '0') * (num2[j] - '0');
            int sum = product + (result[i + j + 1] - '0');
            result[i + j + 1] = sum % 10 + '0';
            result[i + j] += sum / 10;
        }
    }
    
    size_t startPos = result.find_first_not_of('0');
    return (startPos != string::npos) ? result.substr(startPos) : "0";
}

---

四、数组模拟高精度除法

4.1 算法思路

从高位到低位逐位试商。

4.2 代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

pair<string, string> divide(string dividend, string divisor) {
    if (divisor == "0") {
        return {"", ""};
    }
    
    string quotient, remainder;
    int len = dividend.size();
    
    for (int i = 0; i < len; i++) {
        remainder += dividend[i];
        
        int q = 0;
        string temp;
        
        while (isGreaterOrEqual(remainder, divisor)) {
            remainder = subtract(remainder, divisor);
            q++;
        }
        
        quotient.push_back(q + '0');
    }
    
    size_t qStart = quotient.find_first_not_of('0');
    size_t rStart = remainder.find_first_not_of('0');
    
    quotient = (qStart != string::npos) ? quotient.substr(qStart) : "0";
    remainder = (rStart != string::npos) ? remainder.substr(rStart) : "0";
    
    return {quotient, remainder};
}

---

五、示例程序

#include <iostream>
#include <string>
using namespace std;

string add(string, string);
string multiply(string, string);

int main() {
    string a = "12345678901234567890";
    string b = "98765432109876543210";
    
    cout << "加法结果: " << add(a, b) << endl;
    cout << "乘法结果: " << multiply(a, b) << endl;
    
    return 0;
}