算法基础课题解合集

高精度算法其实就是模拟！

模拟我们小学学的竖式加法

小学竖式

假设有两个数 $123$，和 $789$，这两个数相加就应该先把 $3$ 和 $9$ 相加，然后写 $2$ 进 $1$，接着 $2$ 加上 $8$ 和进位的 $1$，得 $11$，然后写 $1$ 进 $1$，最后 $1$ 加上 $7$ 和 进位 $1$，得 $9$，答案为 $912$。

高精度算法步骤

1. 用字符串将两个整数 $A$ 和 $B$，读进来。

2. 把字符串每个字符转成整数(就是 -'0')，然后倒序存入 $vector$ 里。

3. 让两个 $vector$ 做上面的竖式操作

4. 输出答案即可

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)//高精度加法
{
    vector<int> C;//答案
    int t = 0;//算进位的
    for (int i = 0; i < A.size() || i < B.size(); i ++)
    {
        /*
            把 A[i] 和 B[i] 两个数求和。
            注意要先判断有没有这个数，不然就会访问非法内存。
        */
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        /*
            t % 10 就是求这一位上的值。
            比如和是 12 那么 12 % 10 就是 2，所以这一位上填 2。
        */
        C.push_back(t % 10);
        /*
            统计进位。
            还是比如是 12，那么 12 / 10 就是 1，所以进 1。
        */
        t /= 10;
    }
    /*
        如果最后一位还有进位，就把最后一位的进位加入答案。
        比如 123 + 999，最后一位 1 + 9 + 1，还要进一位。
    */
    if (t) C.push_back(t);
    //去前导 0
    while (C.back() == 0 && C.size() > 1) C.pop_back();
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    //倒序存储
    for (int i = a.size() - 1; i >= 0; i --)
        A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i --)
        B.push_back(b[i] - '0');
    auto C = add(A, B);//也可以写成 vector<int> C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i --)
        cout << C[i];
    return 0; 
}

好了，这篇题解到这里就结束了，感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$