WHCSRL 技术网

C++题解 高精度减法

C++题解 高精度减法

题目描述

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

输入格式

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

输出格式

共一行,包含所求的差。

数据范围

1 ≤ 整 数 长 度 ≤ 1 0 5 1≤整数长度≤10^5 1105

输入样例:

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) =

{r,r0,r+10,r<0}
F(r)={rr+10,r0,,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
推荐阅读