C++
高精度除法教程：用高精度减法高精度减法模拟除法（C++实现，无优化）
admin SU @ 2025-9-21 13:32:02

高精度除法教程：用高精度减法高精度减法模拟除法（C++实现，无优化）

在处理超出内置数据类型范围的大整数除法时，我们可以通过模拟手动计算的方式实现。本教程将介绍如何使用高精度减法来模拟除法运算，完全遵循手动计算逻辑，不做任何优化，帮助理解其核心原理。

一、基本原理

用减法模拟除法的核心思想很简单：求被除数a除以除数b的商和余数，本质上就是计算"a中包含多少个b"，商就是这个数量，而剩下的部分就是余数。

例如计算10÷3：

10 - 3 = 7（商+1）
7 - 3 = 4（商+1）
4 - 3 = 1（商+1）
1 < 3，停止
结果：商=3，余数=1

二、数据表示

我们使用字符串存储大整数，并用数组来处理每一位数字，约定如下：

数组下标0表示最低位（个位），方便进位和借位操作
例如"1234"存储为数组[4,3,2,1]

三、核心操作实现

3.1 高精度比较函数

判断两个大整数的大小，这是决定是否可以继续减法的关键：

// 比较两个大整数，a和b都是最低位在前的数组
// 返回值：1(a > b)，0(a == b)，-1(a < b)
int compare(const vector<int>& a, const vector<int>& b) {
    // 先比较长度，长的数更大
    if (a.size() > b.size()) return 1;
    if (a.size() < b.size()) return -1;
    
    // 长度相同则从最高位到最低位比较
    for (int i = a.size() - 1; i >= 0; i--) {
        if (a[i] > b[i]) return 1;
        if (a[i] < b[i]) return -1;
    }
    return 0; // 相等
}

3.2 高精度减法函数

实现两个大整数的减法（a - b），要求a > b：

// 高精度减法，a - b，结果存储在a中
// 要求：a > b，都是最低位在前的数组
void subtract(vector<int>& a, const vector<int>& b) {
    int borrow = 0;
    for (int i = 0; i < a.size(); i++) {
        // 当前位的值 = a的当前位 - 借位
        int val = a[i] - borrow;
        // 如果b还有这一位，则减去
        if (i < b.size()) {
            val -= b[i];
        }
        
        // 处理借位
        if (val < 0) {
            val += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        
        a[i] = val;
    }
    
    // 移除前导零（最高位的零）
    while (a.size() > 1 && a.back() == 0) {
        a.pop_back();
    }
}

3.3 字符串转数组函数

将输入的数字字符串转换为我们约定的数组格式：

// 将数字字符串转换为最低位在前的数组
vector<int> strToVector(const string& s) {
    vector<int> res;
    for (int i = s.size() - 1; i >= 0; i--) {
        res.push_back(s[i] - '0');
    }
    return res;
}

3.4 数组转字符串函数

将计算结果的数组转换回字符串格式：

// 将最低位在前的数组转换为数字字符串
string vectorToStr(const vector<int>& v) {
    string res;
    for (int i = v.size() - 1; i >= 0; i--) {
        res += (v[i] + '0');
    }
    return res.empty() ? "0" : res;
}

四、完整除法实现

结合以上函数，实现用减法模拟的高精度除法：

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

// 比较两个大整数，a和b都是最低位在前的数组
// 返回值：1(a > b)，0(a == b)，-1(a < b)
int compare(const vector<int>& a, const vector<int>& b) {
    if (a.size() > b.size()) return 1;
    if (a.size() < b.size()) return -1;
    
    for (int i = a.size() - 1; i >= 0; i--) {
        if (a[i] > b[i]) return 1;
        if (a[i] < b[i]) return -1;
    }
    return 0;
}

// 高精度减法，a - b，结果存储在a中
// 要求：a > b，都是最低位在前的数组
void subtract(vector<int>& a, const vector<int>& b) {
    int borrow = 0;
    for (int i = 0; i < a.size(); i++) {
        int val = a[i] - borrow;
        if (i < b.size()) {
            val -= b[i];
        }
        
        if (val < 0) {
            val += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        
        a[i] = val;
    }
    
    // 移除前导零
    while (a.size() > 1 && a.back() == 0) {
        a.pop_back();
    }
}

// 将数字字符串转换为最低位在前的数组
vector<int> strToVector(const string& s) {
    vector<int> res;
    for (int i = s.size() - 1; i >= 0; i--) {
        res.push_back(s[i] - '0');
    }
    return res;
}

// 将最低位在前的数组转换为数字字符串
string vectorToStr(const vector<int>& v) {
    string res;
    for (int i = v.size() - 1; i >= 0; i--) {
        res += (v[i] + '0');
    }
    return res.empty() ? "0" : res;
}

// 高精度除法：用减法模拟，返回(商, 余数)
pair<string, string> highPrecisionDivision(const string& dividend, const string& divisor) {
    // 处理除数为0的情况
    if (divisor == "0") {
        throw invalid_argument("除数不能为0");
    }
    
    // 处理被除数为0的情况
    if (dividend == "0") {
        return make_pair("0", "0");
    }
    
    vector<int> a = strToVector(dividend);
    vector<int> b = strToVector(divisor);
    
    // 如果被除数小于除数，商为0，余数为被除数
    if (compare(a, b) < 0) {
        return make_pair("0", dividend);
    }
    
    // 初始化商为0
    vector<int> quotient(1, 0);
    
    // 不断用a减b，直到a < b
    while (compare(a, b) >= 0) {
        subtract(a, b);
        
        // 商加1
        int carry = 1;
        for (int i = 0; i < quotient.size() && carry; i++) {
            int sum = quotient[i] + carry;
            quotient[i] = sum % 10;
            carry = sum / 10;
        }
        if (carry) {
            quotient.push_back(carry);
        }
    }
    
    // 转换结果为字符串
    string quotientStr = vectorToStr(quotient);
    string remainderStr = vectorToStr(a);
    
    return make_pair(quotientStr, remainderStr);
}

int main() {
    // 测试示例
    string dividend, divisor;
    
    cout << "请输入被除数: ";
    cin >> dividend;
    cout << "请输入除数: ";
    cin >> divisor;
    
    try {
        auto result = highPrecisionDivision(dividend, divisor);
        cout << dividend << " ÷ " << divisor << " = " << result.first 
             << ", 余数: " << result.second << endl;
    } catch (const invalid_argument& e) {
        cout << "错误: " << e.what() << endl;
    }
    
    // 以下是一些预设的测试用例
    cout << "\n测试用例:\n";
    auto test = [](const string& a, const string& b) {
        auto res = highPrecisionDivision(a, b);
        cout << a << " ÷ " << b << " = " << res.first << ", 余数: " << res.second << endl;
    };
    
    test("10", "3");        // 10 ÷ 3 = 3, 余数: 1
    test("100", "7");       // 100 ÷ 7 = 14, 余数: 2
    test("12345", "23");    // 12345 ÷ 23 = 536, 余数: 17
    test("99999", "123");   // 99999 ÷ 123 = 812, 余数: 33
    test("123", "456");     // 123 ÷ 456 = 0, 余数: 123
    test("0", "12345");     // 0 ÷ 12345 = 0, 余数: 0
    
    return 0;
}

五、代码解析

上述代码的核心逻辑在highPrecisionDivision函数中，其工作流程如下：

参数检查：处理除数为0和被除数为0的特殊情况
初始化：将输入的字符串转换为我们约定的数组格式
特殊情况处理：如果被除数小于除数，直接返回商0和余数为被除数
核心循环：
- 只要被除数大于等于除数，就用被除数减去除数
- 每次减法后，商加1（注意处理商的进位）
结果转换：将表示商和余数的数组转换回字符串格式并返回

六、算法特点与性能

这种用减法模拟除法的方法：

优点：逻辑简单直观，完全模拟手动计算过程，易于理解
缺点：效率极低，时间复杂度为O(a/b)，当商很大时（如1000000÷1）需要执行百万次减法
适用场景：仅用于理解除法的基本原理，不适合实际工程中处理大整数除法

七、总结

本教程介绍了如何使用高精度减法来模拟除法运算，通过这种方法，我们可以处理任意大小的整数除法。虽然这种方法效率不高，但它清晰地展示了除法运算的本质：商是被除数中包含除数的个数，余数是除法后剩下的部分。

在实际应用中，我们通常会使用更高效的算法（如模拟竖式除法），但理解这种最基本的实现方式，有助于深入理解高精度计算的核心思想。

目前还没有评论...