AcWing 792. 高精度减法
原题链接
简单
作者:
BanLi
,
2021-01-24 10:16:20
,
所有人可见
,
阅读 209
新手记录
C++ 代码
#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> &sa, vector<int> &sb){
vector<int> sc;
int t = 0; //表示借位,初始为0
for(int i = 0; i < sa.size(); i++){
t = sa[i] - t; //首先用较大数sa的i位减去进位, 借助10进制减法理解,这里的t要么为0,要么为1
if(i < sb.size()) //若还未超过较小数的长度,则减去sb的i位
t -= sb[i];
sc.push_back((t + 10) % 10); //t加10再取余表示,如果是负数,那么需要借位,即向高位借1相当于该位加10
//如果是正数,那么加的10对10取余之后为0,等于没加,取余结果仍是本身
if(t < 0) //针对t为负数时,向高位借了一位,则借位置为1,下次高位相减时,减数则要先减去1再与被减数相减
t = 1;
else
t = 0; //为正数则表示没有借位
}
while (sc.size() > 1 && sc.back() == 0) //当高位相同或借位导致高位相减得到结果中高位有很多0时,需要清除高位的0
sc.pop_back(); //以大于sc的长度大于1为判断条件是因为结果为0时需要保留一位0
return sc;
}
int main(){
string a, b;
vector<int> sa, sb;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i -- )
sa.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i -- )
sb.push_back(b[i] - '0');
vector<int> sc;
if(cmp(sa, sb)) //首先进行比较,从而判断是否需要输出负号,在进行减法时,保证是较大数减较小数
sc = sub(sa, sb);
else{
sc = sub(sb, sa);
cout << "-";
}
for(int i = sc.size() - 1; i >= 0; i--)
cout << sc[i];
return 0;
}