算法学习——高精度减法

思路

防止两个数字在相减时超出long long的范围，所以使用该方法，主要原理是判断两个数字大小后进行相减，并模拟减法借位操作。

代码

#include<bits/stdc++.h>
using namespace std;
//判断大小
bool cmp(string s1,string s2){
    if(s1.size()!=s2.size())
        return s1.size()>s2.size();//长度大的数字大
    for(int i=s1.size()-1;i>=0;i--)
        if(s1[i]!=s2[i])
            return s1[i]>s2[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;//如果a<b则下一个最高位减1
        else    t = 0;//反之则为零
    }
    while((c.size()>1)&&(c[c.size()-1]==0)) c.pop_back();
    //去除最高位的零
    return c;
}
int main(){
    string s1,s2;
    cin>>s1>>s2;
    vector<int> a,b,c;
    //倒着将数字放入数组
    for(int i=s1.size()-1;i>=0;i--) a.push_back(s1[i]-'0');
    for(int i=s2.size()-1;i>=0;i--) b.push_back(s2[i]-'0');
    if(cmp(s1,s2)){
        c = sub(a,b);
    }
    else{
        //参数交换时需要输出负号
        printf("-");
        c = sub(b,a);
    }
    for(int i=c.size()-1;i>=0;i--)  printf("%d",c[i]);
    return 0;
}