C/C++教程

C++题解 高精度减法

本文主要是介绍C++题解 高精度减法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

C++题解 高精度减法

题目描述

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

输入格式

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

输出格式

共一行,包含所求的差。

数据范围

$$
1≤整数长度≤10^5
$$

 

输入样例:

32
11

输出样例:

21

思路

对于该题目的实现,我们使用两个数组进行加法的模拟,为了方便此处使用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) = \begin{Bmatrix} r &, r\ge0,\\ r + 10 &, r < 0 \end{Bmatrix}
$$

 

对于借位 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;
}

 

这篇关于C++题解 高精度减法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!