• C++
  • 高精度除以高精度(竖式模拟法)教程

  • @ 2025-9-21 14:03:22

高精度除以高精度(竖式模拟法)教程

在 C++ 中,处理超过内置数据类型范围的大整数运算时,需要使用高精度算法。本文将介绍如何通过模拟竖式除法的方式实现高精度除以高精度的运算,不进行任何优化,完整还原手工计算过程。

算法思路

  1. 存储方式:使用字符串或数组存储大整数,每个元素表示一位数字
  2. 比较大小:先比较被除数和除数的大小,确定商的位数
  3. 竖式除法模拟
    • 从被除数的高位开始,逐位与除数比较
    • 确定当前位的商值(0-9)
    • 计算当前位的乘积并从被除数中减去
    • 处理余数,带入下一位计算
  4. 处理商的前导零:去除计算结果中多余的前导零

实现代码

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 比较两个高精度数的大小,a >= b 返回true
bool greaterOrEqual(const string &a, const string &b) {
    if (a.length() != b.length()) {
        return a.length() > b.length();
    }
    // 长度相等时逐位比较
    for (int i = 0; i < a.length(); i++) {
        if (a[i] != b[i]) {
            return a[i] > b[i];
        }
    }
    return true; // 两数相等
}

// 高精度减法,a - b,确保a >= b
string subtract(const string &a, const string &b) {
    string result;
    int i = a.length() - 1;
    int j = b.length() - 1;
    int borrow = 0;
    
    while (i >= 0 || j >= 0) {
        int digitA = (i >= 0) ? (a[i] - '0') : 0;
        int digitB = (j >= 0) ? (b[j] - '0') : 0;
        
        // 处理借位
        digitA -= borrow;
        if (digitA < digitB) {
            digitA += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        
        result.push_back((digitA - digitB) + '0');
        i--;
        j--;
    }
    
    // 去除结果中的前导零
    reverse(result.begin(), result.end());
    size_t startPos = result.find_first_not_of('0');
    if (startPos != string::npos) {
        result = result.substr(startPos);
    } else {
        result = "0";
    }
    
    return result;
}

// 高精度乘法(乘以单个数字)
string multiplySingleDigit(const string &num, int digit) {
    if (digit == 0) return "0";
    
    string result;
    int carry = 0;
    for (int i = num.length() - 1; i >= 0; i--) {
        int product = (num[i] - '0') * digit + carry;
        carry = product / 10;
        result.push_back((product % 10) + '0');
    }
    
    if (carry > 0) {
        result.push_back(carry + '0');
    }
    
    reverse(result.begin(), result.end());
    return result;
}

// 高精度除以高精度,返回商和余数
pair<string, string> divide(const string &dividend, const string &divisor) {
    // 处理除数为0的情况
    if (divisor == "0") {
        cerr << "错误:除数不能为0" << endl;
        exit(1);
    }
    
    // 处理被除数小于除数的情况
    if (!greaterOrEqual(dividend, divisor)) {
        return make_pair("0", dividend);
    }
    
    string quotient;
    string remainder = "";
    int dividendLen = dividend.length();
    int divisorLen = divisor.length();
    
    // 从被除数的高位开始处理
    for (int i = 0; i < dividendLen; i++) {
        // 将当前位加入余数
        remainder += dividend[i];
        
        // 去除余数的前导零
        if (remainder[0] == '0' && remainder.length() > 1) {
            size_t startPos = remainder.find_first_not_of('0');
            if (startPos != string::npos) {
                remainder = remainder.substr(startPos);
            } else {
                remainder = "0";
            }
        }
        
        // 确定当前位的商
        int currentDigit = 0;
        while (greaterOrEqual(remainder, divisor)) {
            // 减去一次除数,商加1
            remainder = subtract(remainder, divisor);
            currentDigit++;
        }
        
        quotient.push_back(currentDigit + '0');
    }
    
    // 去除商的前导零
    size_t startPos = quotient.find_first_not_of('0');
    if (startPos != string::npos) {
        quotient = quotient.substr(startPos);
    } else {
        quotient = "0";
    }
    
    return make_pair(quotient, remainder);
}

int main() {
    string dividend, divisor;
    
    cout << "请输入被除数: ";
    cin >> dividend;
    cout << "请输入除数: ";
    cin >> divisor;
    
    // 验证输入是否为合法数字
    auto isNumber = [](const string &s) {
        if (s.empty()) return false;
        for (char c : s) {
            if (!isdigit(c)) return false;
        }
        return true;
    };
    
    if (!isNumber(dividend) || !isNumber(divisor)) {
        cerr << "错误:输入必须是正整数" << endl;
        return 1;
    }
    
    pair<string, string> result = divide(dividend, divisor);
    
    cout << "商: " << result.first << endl;
    cout << "余数: " << result.second << endl;
    
    return 0;
}

代码解析

  1. greaterOrEqual 函数:比较两个高精度数的大小,用于判断是否可以进行减法操作

  2. subtract 函数:实现高精度减法,前提是被减数大于等于减数,处理了借位逻辑并去除结果中的前导零

  3. multiplySingleDigit 函数:实现高精度数乘以单个数字(0-9)的运算,处理进位逻辑

  4. divide 函数:核心除法函数,模拟竖式除法过程:

    • 从被除数的最高位开始,逐位处理
    • 每次将当前位加入余数
    • 通过多次减法确定当前位的商值
    • 更新余数并继续处理下一位
  5. 主函数:处理输入输出,验证输入合法性,并调用除法函数获取结果

使用方法

  1. 输入两个非负整数(可以是非常大的数,超出内置类型范围)
  2. 程序会计算并输出商和余数

这种实现方式完全模拟了手工竖式除法的过程,虽然效率不高(时间复杂度为O(n²)),但逻辑清晰,易于理解,适合作为学习高精度算法的入门示例。

1 条评论

  • @ 2025-9-21 14:04:59

    以下是为每行代码添加详细注释后的版本,帮助理解高精度除法的实现细节:

    // 引入必要的头文件
    #include <iostream>   // 用于输入输出操作
    #include <string>     // 用于处理字符串(存储大整数)
    #include <algorithm>  // 用于字符串反转等算法操作
    
    // 使用标准命名空间,避免重复书写std::
    using namespace std;
    
    // 比较两个高精度数的大小,a >= b 时返回true
    bool greaterOrEqual(const string &a, const string &b) {
        // 先比较长度,长度长的数更大
        if (a.length() != b.length()) {
            return a.length() > b.length();
        }
        // 长度相等时,从高位到低位逐位比较
        for (int i = 0; i < a.length(); i++) {
            if (a[i] != b[i]) {
                return a[i] > b[i];  // 找到第一位不相等的数字进行比较
            }
        }
        return true;  // 所有位都相等,两数相等
    }
    
    // 高精度减法,计算 a - b,要求 a >= b
    string subtract(const string &a, const string &b) {
        string result;  // 存储减法结果
        int i = a.length() - 1;  // 指向a的最后一位(最低位)
        int j = b.length() - 1;  // 指向b的最后一位(最低位)
        int borrow = 0;  // 借位标志,0表示无借位,1表示有借位
        
        // 从最低位开始处理每一位
        while (i >= 0 || j >= 0) {
            // 获取当前位的数字,若已超出字符串范围则视为0
            int digitA = (i >= 0) ? (a[i] - '0') : 0;
            int digitB = (j >= 0) ? (b[j] - '0') : 0;
            
            // 减去上一次的借位
            digitA -= borrow;
            // 若当前位a的数字小于b的数字,需要向高位借位
            if (digitA < digitB) {
                digitA += 10;  // 借1当10
                borrow = 1;    // 标记借位
            } else {
                borrow = 0;    // 无需借位
            }
            
            // 计算当前位的结果并加入结果字符串
            result.push_back((digitA - digitB) + '0');
            // 移动到下一位(高位)
            i--;
            j--;
        }
        
        // 反转结果字符串(因为我们是从低位开始计算的)
        reverse(result.begin(), result.end());
        // 去除结果中的前导零
        size_t startPos = result.find_first_not_of('0');
        if (startPos != string::npos) {
            result = result.substr(startPos);  // 从第一个非零位开始截取
        } else {
            result = "0";  // 若全为零,则结果为"0"
        }
        
        return result;
    }
    
    // 高精度乘法(乘以单个数字0-9)
    string multiplySingleDigit(const string &num, int digit) {
        if (digit == 0) return "0";  // 任何数乘以0都为0
        
        string result;  // 存储乘法结果
        int carry = 0;  // 进位值
        // 从最低位开始处理每一位
        for (int i = num.length() - 1; i >= 0; i--) {
            // 计算当前位与digit的乘积,加上进位
            int product = (num[i] - '0') * digit + carry;
            carry = product / 10;  // 计算新的进位
            // 将当前位的结果(乘积的个位数)加入结果字符串
            result.push_back((product % 10) + '0');
        }
        
        // 若还有进位,加入结果
        if (carry > 0) {
            result.push_back(carry + '0');
        }
        
        // 反转结果字符串得到正确的顺序
        reverse(result.begin(), result.end());
        return result;
    }
    
    // 高精度除以高精度,返回商和余数(pair的第一个元素是商,第二个是余数)
    pair<string, string> divide(const string &dividend, const string &divisor) {
        // 处理除数为0的情况
        if (divisor == "0") {
            cerr << "错误:除数不能为0" << endl;
            exit(1);  // 异常退出程序
        }
        
        // 若被除数小于除数,商为0,余数为被除数
        if (!greaterOrEqual(dividend, divisor)) {
            return make_pair("0", dividend);
        }
        
        string quotient;    // 存储商
        string remainder = "";  // 存储余数
        int dividendLen = dividend.length();  // 被除数的长度
        int divisorLen = divisor.length();    // 除数的长度
        
        // 从被除数的最高位开始逐位处理
        for (int i = 0; i < dividendLen; i++) {
            // 将当前位加入余数中
            remainder += dividend[i];
            
            // 去除余数中的前导零(保持余数的正确格式)
            if (remainder[0] == '0' && remainder.length() > 1) {
                size_t startPos = remainder.find_first_not_of('0');
                if (startPos != string::npos) {
                    remainder = remainder.substr(startPos);
                } else {
                    remainder = "0";
                }
            }
            
            // 确定当前位的商值(0-9)
            int currentDigit = 0;
            // 通过多次减去除数来找到最大的商值
            while (greaterOrEqual(remainder, divisor)) {
                remainder = subtract(remainder, divisor);  // 余数减去除数
                currentDigit++;  // 商值加1
            }
            
            // 将当前位的商加入结果
            quotient.push_back(currentDigit + '0');
        }
        
        // 去除商中的前导零
        size_t startPos = quotient.find_first_not_of('0');
        if (startPos != string::npos) {
            quotient = quotient.substr(startPos);
        } else {
            quotient = "0";  // 若全为零,则商为"0"
        }
        
        return make_pair(quotient, remainder);  // 返回商和余数
    }
    
    int main() {
        string dividend, divisor;  // 存储被除数和除数
        
        // 获取用户输入
        cout << "请输入被除数: ";
        cin >> dividend;
        cout << "请输入除数: ";
        cin >> divisor;
        
        // 定义 lambda 表达式验证输入是否为合法的非负整数
        auto isNumber = [](const string &s) {
            if (s.empty()) return false;  // 空字符串不合法
            // 检查每个字符是否为数字
            for (char c : s) {
                if (!isdigit(c)) return false;
            }
            return true;
        };
        
        // 验证输入合法性
        if (!isNumber(dividend) || !isNumber(divisor)) {
            cerr << "错误:输入必须是正整数" << endl;
            return 1;  // 输入不合法,退出程序
        }
        
        // 调用除法函数计算结果
        pair<string, string> result = divide(dividend, divisor);
        
        // 输出结果
        cout << "商: " << result.first << endl;
        cout << "余数: " << result.second << endl;
        
        return 0;  // 程序正常结束
    }
    

    以上注释详细解释了每一行代码的作用和实现思路,特别关注了高精度运算中字符串处理的细节,如:

    • 如何通过字符串存储大整数
    • 如何处理进位和借位
    • 如何去除前导零以保证结果正确性
    • 如何模拟手工除法的竖式计算过程

    通过这些注释,可以更清晰地理解高精度除法的实现原理和代码逻辑。

    • 1