题目描述
-
高精度减法给定两个正整数,计算它们的差,计算结果可能为负数。
输入格式
共两行,每行包含一个整数。
输出格式
共一行,包含所求的差。
数据范围
1≤整数长度≤1051≤整数长度≤105
样例
输入样例:
```
32
11
```
输出样例:
```
21
```
思路:
首先高精度的题不管是加减乘除存储数据的方式都是一样的,因为一道题中往往不会只含有一种运算方法,所以都采用逆序存储;
其次需要比较A和B的大小,因为模板适用于A大于B的情况,如果B大于A,则B - A,只不过在结果前面增加一个-号;
最后考虑如何写sub函数,最难的地方就是借位问题,即考虑t = A[i] - B[i] - t大于等于0 还是小于0,如果是大于等于0的话,就不用借位了,则令t = 0,否则令t = 1,写函数过程中还需注意i < B.size()这一边界问题,因为只有在这个条件下成立才能正确运行函数,最后还需注意是否结果含有前导0这一情况,如果有,则剔除。
代码:
#include<iostream>
#include<vector>
using namespace std;
// 比较是否有 A >= B
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;
if(i < B.size()) t -= B[i];
C.push_back((t + 10) % 10); // 包含t >= 0 && t < 0 两种情况
if(t < 0) t = 1; // 如果t < 0 则表示像高位借了一位
else t = 0;
}
// 去除前号0
// 注意这里C是逆序存储数据
while(C.size() > 1 && 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');
if(cmp(A, B)){
auto C = sub(A, B);
for(int i = C.size() - 1; i >= 0; --i) cout<<C[i];
}else{ // 如果B > A,那就算sub(B, A),在前面加个-号即可
cout<<"-";
auto C = sub(B, A);
for(int i = C.size() - 1; i >= 0; --i) cout<<C[i];
}
return 0;
}
```