C++实现高精度减法

2023-08-07 10:23 由 Tomhard 发表于 #其他

一、问题描述：

高精度算法是处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中，用一个数组去表示一个数字，这样这个数字就被称为是高精度数。

二、解决思路：

其实按照上面的描述，我们也知道了我们需要将数中的每一个位进行相减。然后我们想到了我们使用字符串的话，可以很方便的取出每一个字符。然后我们就将数字按照字符串的形式输入进去。然后我们每取出来一个值，就将它转换为整数型，然后这个时候，我们就可以接着进行计算了。

我们这里需要实现的是减法运算，这也就意味着，我们可能存在被减数小于减数的情况，这个时候，我们有一个办法，就是先进行判断，如果被减数<减数，那么我们需要将他们颠倒计算，再添上一个‘-’号。至于如何判断，这个分为两种情况，一种情况是说A的位数和B的位数不相等（如A是三位数，B是六位数），还有一种情况是说A和B的位数相等，但是其中一位的数字不相等（如123和153这两个数字）

然后我们就可以进行计算了，计算的时候，我们还需要考虑一个问题，就是123-153只中，2<5这种情况，这意味着我们需要对更高位进行借位的情况，这个时候我们需要将借位情况计入一个变量t中，t的值只能是1或者0.然后如果借了位，那么被减数这一位的数字+10，更高位的数字-1.

三、代码实现：

#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;
    for(int i=0,t=0;i<A.size();i++){
        t=A[i]-t;//如果借位了，就需要借位的那个1减掉去
        if(i<B.size()) t-=B[i];//如果B的位数小于A的位数，那么就不用计算了，直接把值传下去
        C.push_back((t+10)%10);//这个分为两种情况，一种是A-B的值够用，一种是A-B的值不够用（这个时候我们就向A的上一位借1进行计算）
        if(t<0) t=1;//借了位进行标记，上一位需要剪掉1
        else t=0;
    }

    while(C.size()>1&&C.back()==0) C.pop_back();//将类似于3000这样值的末尾0减掉去，但是会保留单独的0这样的值
    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');//注意，这里我们使用的是i=a.size()-1，这是因为我们需要从个位开始计算

    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];
    cout<<endl;

    return 0;
}