算法基础课题解合集

高精度减法其实是模拟竖式。

小学竖式

假设有一个算式为 123 - 99，那么我们就先算 $3 - 9$，不够减怎么办？借位！

我们从 $2$ 那里借来 $1$，这样就变成了 $13 - 9$，得 $4$。

然后算第二位，由于 $2$ 被借了 $1$，所以实际上是 $1 - 9$，不够减就找 $1$ 借去 $1$，这样就成了 $11 - 9$，得 $2$。

最高位被借了 $1$，所以变成了 $0$，不管，结束，答案是 $24$。

高精度减法

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

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

3. 判断 $A$ 是否 $\geq b$，如果小于，则输出一个符号，然后交换 $A$ 和 $B$。

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

5. 输出答案即可。

代码

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

using namespace std;

//比较 A 和 B 的大小
bool cmp(const vector<int> &A, const vector<int> &B)
{
    //如果长度不同那肯定一大一小
    if (A.size() != B.size()) return A.size() > B.size();
    //从最高位开始比
    //由于我们是倒序存储的，所以要从尾部开始
    for (int i = A.size() - 1; i >= 0; i --)
        if (A[i] != B[i])
            return A[i] > B[i];
    return true;
}

vector<int> sub(const vector<int> &A, const vector<int> &B)
{
    vector<int> C;//答案
    for (int i = 0, t = 0; i < A.size(); i ++)//t 为进位，而且经过比较，A 的长度一定大于 B 的长度
    {
        //t = A[i] - B[i] - t
        //但是由于 B 的长度问题，就拆成两部
        t = A[i] - t;
        if (i < B.size())
            t -= B[i];
        /*
            假设 t 是负数，比如 -8，那 +10，后为 2，%10 为 2。
            如果是正数就是 %10 的结果
        */
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    //去前导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');
    //A >= B
    if (cmp(A, B))
    {
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i --)
            printf("%d", C[i]);
    }
    //A < B
    else 
    {
        printf("-");
        auto C = sub(B, A);
        for (int i = C.size() - 1; i >= 0; i --)
            printf("%d", 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{天元之弈}$