【算法】高精度减法(大数减法)

高精度减法(大数减法)

• 基本原理：模拟小学时候的减法运算，模拟借位，进位操作
• 从低位开始用大数减小数
• 我们在存储数字的时候选择vector容器，尾插法，倒序存储方便计算

如图所示

解释

1. 我们在像图示一样减法计算的时候，通常是大数在上，小数在下，故在调用函数的时候我们也进行一个判断，大于正常A，B传入参数否则B，A传参
2. 只是在输出的时候我们心里面要知道这是一个负数故在最前面添上一个负号
3. 6-9-tt初始值为0，因为从低位往高位进行减法运算故第一位不可能出现前面有借位情况
4. 我们将(t+10)%10这个结果存进容器，如果两数相减结果小于0，通过+10也能模拟进位的情况，如果≥0存进的也会是该数本身，非常的巧妙
5. 如果想不到上面的巧妙办法也可以使用if对t进行判断再存进容器即可
6. 因为我们保证了A≥B故A必定每次都要去减借位，但B不一定，防止越界所以对长度进行判断后再进行减法运算
7. 怎么判断是否有借位可以通过t值来判断，因为进行借位的操作是在步骤4进行的，那个地方巧妙的进行了借位，我们在这儿就需要判断它是否小于0来判断
8. 如果小于0必定有借位让t=1，再下一次循环会减去，否则置为0表示前面没有借，不用减
9. 最后对容器前导0去除即可，因为存的时候高位在后，所以末尾为0，即前导0

#include 
#include 

using namespace std;

// A是否大于等于B
bool cmp(vector<int> &A, vector<int> &B) {
    if (A.size() != B.size()) {
        return A.size() >= B.size();
    }
    // 从高位开始判断
    for (int i = A.size(); i >= 0; --i) {
        if (A[i] != B[i]) {
            return A[i] >= B[i];
        }
    }
    return true;
}

vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0;
    for (int i = 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;
}

int main() {

    string a, b;
    cin >> a >> b;
    vector<int> A;
    // 将A字符串逆序读入容器
    for (int i = a.size() - 1; i >= 0; --i) {
        A.push_back(a[i] - '0');
    }
    vector<int> B;
    // 将B字符串逆序读入容器
    for (int i = b.size() - 1; i >= 0; --i) {
        B.push_back(b[i] - '0');
    }
    // 结果容器
    vector<int> C;
    // 调用减法函数之前判断是否两数大小
    if (cmp(A, B)) {
        C = sub(A, B);
        // 逆序输出正数结果
        for (int i = C.size() - 1; i >= 0; --i) {
            cout << C[i];
        }
    } else {
        C = sub(B, A);
        cout << "-";
        // 逆序输出负数结果
        for (int i = C.size() - 1; i >= 0; --i) {
            cout << C[i];
        }
    }


    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76