C++
（C++）数组模拟高精度加法、减法、乘法、除法
admin SU @ 2025-5-1 15:29:39

以下是使用 C++ 数组模拟高精度加法、减法、乘法和除法的代码：

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

// 高精度加法
std::vector<int> add(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}

// 高精度减法
std::vector<int> sub(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> c;
    for (int i = 0, t = 0; i < a.size(); i++) {
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

// 高精度乘法（一个大数乘一个小数）
std::vector<int> mul(const std::vector<int>& a, int b) {
    std::vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || t; i++) {
        if (i < a.size()) t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

// 高精度除法（一个大数除以一个小数）
std::pair<std::vector<int>, int> div(const std::vector<int>& a, int b) {
    std::vector<int> c;
    int r = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        r = r * 10 + a[i];
        c.push_back(r / b);
        r %= b;
    }
    std::reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return {c, r};
}

// 打印结果
void print(const std::vector<int>& num) {
    for (int i = num.size() - 1; i >= 0; i--) {
        std::cout << num[i];
    }
    std::cout << std::endl;
}

int main() {
    std::string num1, num2;
    int small_num;
    std::cout << "请输入第一个大数: ";
    std::cin >> num1;
    std::cout << "请输入第二个大数: ";
    std::cin >> num2;
    std::cout << "请输入一个小数用于乘除运算: ";
    std::cin >> small_num;

    std::vector<int> a, b;
    for (int i = num1.size() - 1; i >= 0; i--) a.push_back(num1[i] - '0');
    for (int i = num2.size() - 1; i >= 0; i--) b.push_back(num2[i] - '0');

    std::cout << "加法结果: ";
    print(add(a, b));

    std::cout << "减法结果: ";
    print(sub(a, b));

    std::cout << "乘法结果: ";
    print(mul(a, small_num));

    auto [quotient, remainder] = div(a, small_num);
    std::cout << "除法商: ";
    print(quotient);
    std::cout << "除法余数: " << remainder << std::endl;

    return 0;
}

上述代码定义了四个函数，分别用于模拟高精度加法、减法、乘法和除法。在main函数中，用户输入两个大数和一个小数，程序会调用这些函数进行运算并输出结果。

代码说明：

高精度加法：逐位相加，处理进位。
高精度减法：逐位相减，处理借位，同时去除前导零。
高精度乘法：一个大数乘一个小数，逐位相乘并处理进位，去除前导零。
高精度除法：一个大数除以一个小数，得到商和余数，去除商的前导零。

复杂度分析：

时间复杂度：加法、减法、乘法的时间复杂度为 $O(n)$ ，其中 $n$ 是较大数的位数；除法的时间复杂度也为 $O(n)$ 。
空间复杂度：主要是存储结果的数组，为 $O(n)$ 。

admin SU @ 2025-5-1 15:44:05

C++ 数组模拟高精度加法、减法、乘法、除法教程（0基础详细讲解）

📘 前言：什么是高精度运算？

在C++中，int 和 long long 类型的整数是有范围限制的：

int：通常是 -2³¹ ~ 2³¹-1（约 ±2e9）
long long：通常是 -2⁶³ ~ 2⁶³-1（约 ±9e18）

当我们要处理比这些范围还大的数字时，普通的类型就无法胜任了。

这时候就要使用 高精度算法 —— 使用数组或字符串来手动模拟大整数的四则运算。

🧠 第一章：高精度的基本思想

我们用 逆序存储的数组或vector 来表示一个大整数。

例如，数字 123456789，我们可以这样存储：

vector<int> num = {9, 8, 7, 6, 5, 4, 3, 2, 1};
// 表示个位是9，十位是8，百位是7...

为什么选择逆序？

这样做可以方便从低位到高位进行计算，就像列竖式一样

📦 第二章：输入输出格式说明

我们会使用如下方式读取和输出高精度数：

输入：两个字符串形式的数字（如 "12345678901234567890"）
输出：字符串形式的结果（如 "24691357802469135780"）

➕ 第三章：高精度加法（Addition）

3.1 思路

与小学列竖式加法一致：

    1 9 8      (低位在前)
+   1 2 7
=   3 2 5

逐位相加，注意进位！

3.2 实现步骤

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

vector<int> add(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int carry = 0; // 进位

    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) carry += A[i];
        if (i < B.size()) carry += B[i];
        C.push_back(carry % 10);
        carry /= 10;
    }

    if (carry) C.push_back(1); // 最后还有进位
    return C;
}

3.3 辅助函数：将字符串转为逆序数组

vector<int> strToVec(string s) {
    vector<int> res;
    for (int i = s.size() - 1; i >= 0; i--)
        res.push_back(s[i] - '0');
    return res;
}

3.4 输出函数

void printVec(vector<int>& v) {
    for (int i = v.size() - 1; i >= 0; i--)
        cout << v[i];
    cout << endl;
}

✅ 完整测试代码

int main() {
    string a_str, b_str;
    cout << "请输入第一个大整数: ";
    cin >> a_str;
    cout << "请输入第二个大整数: ";
    cin >> b_str;

    vector<int> A = strToVec(a_str);
    vector<int> B = strToVec(b_str);

    vector<int> C = add(A, B);

    cout << "高精度加法结果是: ";
    printVec(C);

    return 0;
}

➖ 第四章：高精度减法（Subtraction）

4.1 思路

与列竖式减法类似，注意借位。

⚠️ 本教程默认保证 A ≥ B

vector<int> subtract(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int borrow = 0;

    for (int i = 0; i < A.size(); i++) {
        int temp = A[i] - borrow;
        if (i < B.size()) temp -= B[i];

        if (temp < 0) {
            temp += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }

        C.push_back(temp);
    }

    // 去掉末尾多余的0
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();

    return C;
}

✅ 测试方法同上

只需调用 subtract 即可：

vector<int> D = subtract(A, B);
cout << "高精度减法结果是: ";
printVec(D);

✖️ 第五章：高精度乘法（Multiplication）

5.1 思路

模拟手算的方式：一位一位乘然后累加。

比如：

     1 2 3
×       4
---------
     4 9 2

最终数组索引是 i + j

5.2 实现代码

vector<int> multiply(vector<int>& A, int b) {
    vector<int> C;
    int carry = 0;

    for (int i = 0; i < A.size() || carry > 0; i++) {
        int val = carry;
        if (i < A.size()) val += A[i] * b;
        C.push_back(val % 10);
        carry = val / 10;
    }

    // 去掉前导0
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();

    return C;
}

✅ 调用示例

int b;
cout << "请输入乘数: ";
cin >> b;

vector<int> E = multiply(A, b);
cout << "高精度乘法结果是: ";
printVec(E);

➗ 第六章：高精度除法（Division）（按整数除）

6.1 思路

我们实现的是"大整数 ÷ 小整数"的除法（从高位到低位逐步计算）

vector<int> divide(vector<int>& A, int b, int& remainder) {
    vector<int> C;
    long long r = 0;

    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i]; // 当前位参与除法
        C.push_back(r / b);
        r %= b;
    }

    remainder = r;

    // 去掉前导0
    while (C.size() > 1 && C[0] == 0)
        C.erase(C.begin());

    return C;
}

✅ 使用示例

int divisor;
cout << "请输入除数: ";
cin >> divisor;

int remainder;
vector<int> F = divide(A, divisor, remainder);

cout << "商是: ";
printVec(F);
cout << "余数是: " << remainder << endl;

🧪 第七章：综合练习建议

编写程序，实现两个大整数的比较（返回 > 或 <）
扩展乘法：支持两个大整数相乘（需要用到二维数组）
扩展除法：支持两个大整数相除（需要迭代逼近）
写一个计算器程序，支持用户输入任意两个大整数并选择操作（+ - × ÷）
加入负数处理（通过符号位）

📋 第八章：总结对比表

操作	时间复杂度	是否支持负数	备注
高精度加法	O(n)	否	简单直观
高精度减法			需要判断大小
高精度乘法（小整数）			可以扩展为两数相乘
高精度除法（小整数）			支持求余

📚 第九章：推荐学习内容

✅ 高精度乘法扩展（两个大数相乘）
✅ 高精度除法扩展（两个大数相除）
✅ 高精度阶乘计算（如1000!）
✅ 高精度幂运算（快速幂 + 高精度）
✅ 高精度模运算（用于密码学）
✅ 高精度类封装（面向对象编程）

📌 结语

高精度运算是竞赛编程和实际开发中非常实用的技巧，尤其在处理超大数据、金融计算、密码学等领域。虽然看起来有点复杂，但只要理解“列竖式”的思路，就能轻松写出正确的代码。

如果你希望我为你定制以下内容，请留言告诉我：

高精度支持负数的版本
两个大整数相乘的完整实现
高精度类（封装成结构体或类）
高精度计算器完整项目源码

📌 下一步推荐学习：

高精度类的封装（面向对象）
高精度阶乘/幂运算
快速幂 + 模运算
高精度在实际问题中的应用（如LeetCode题解）

祝你学习愉快，早日掌握高精度算法！😊