C++题解 高精度减法

C++题解 高精度减法

题目描述

给定两个正整数（不含前导 00），计算它们的差，计算结果可能为负数。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的差。

数据范围

$$1\le 整数长度\le 10^5$$

输入样例：

32
11
1
2

输出样例：

21
1

思路

对于该题目的实现，我们使用两个数组进行加法的模拟，为了方便此处使用vector。

数据的输入

可以看到数字的长度远远超过了long long的需要，我们需要使用字符串进行数据的读入。

注意，为了运算方便，应该从字符串的末尾将原数字倒序的进行读入，想一想为什么。

模拟减法

负数情况的处理

首先我们需要回想一下，对于一个减法 3 - 5 = -2 ，我们人类一般会转换为 - (5 - 3) = -2 进行计算，那么对于程序也应该使用这种思想。定义一个cmp函数，获取两个数字的长度，当长度相同时，我们从最高位向最低位逐位比较，从而判断出两个数的大小。

借位思想

在这里，我们使用一个整型变量 r 进行运算的存储。将数字 a b 的相应位相减后，我们通过存储 (r + 10) %% 10 作为该位的最终结果，随后若 r < 0 ，令 r = 1 作为下一位运算中现在位的借位。

关于 (r + 10) %% 10

F ( r ) = { r , r ≥ 0 , r + 10 , r < 0 } F (r) =

$$egin{Bmatrix} r &, rge0,\ r + 10 &, r < 0 end{Bmatrix}$$ F(r)={rr+10​,r≥0,,r<0​}

对于借位 r ，应该有这两种情况，但是我们使用 (r + 10) %% 10 可以合二为一，想想为什么。

数据的输出

按照人类的习惯，我们将数组从最高位开始输出即可。

前导0处理

这里有一个比较特殊的情况，例如 222 - 221 我们得到的其实是 002 ，那么我们输出的时候就会导致我们出错。这里我们做了处理，循环检测高位数字，有0则去除，直到高位数字不为0。

以下是代码实现

//
// Created by Owwkmidream on 2021/10/30.
//
#include "iostream"
#include "vector"
using namespace std;

bool cmp(vector<int>& A, 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(vector<int>& A, vector<int>& B)
{
    vector<int> C;

    int r = 0;
    for(int i = 0; i < A.size(); i ++) {
        r = A[i] - r;
        if(i < B.size())    r -= B[i];
        C.push_back((r + 10) %% 10);
        if(r < 0)   r = 1;
        else r = 0;
    }

    while (C.size() > 1 and C.back() == 0)  C.pop_back();

    return C;
}

int main() {
    string a, b;
    cin >> a >> b;

    vector<int> 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');

    vector<int> C;
    if(cmp(A, B))
        C = sub(A, B);
    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