题目描述
给定两个正整数,计算它们的差,计算结果可能为负数。
-
输入格式
共两行,每行包含一个整数。 -
输出格式
共一行,包含所求的差。 -
数据范围
1≤整数长度≤105 - 输入样例:
32
11
- 输出样例:
21
算法分析
-
核心思路:逐位相减(A[i] - B[i] - t)的时候要判断减得的结果,如果小于0则需要往前面借位,即下一次运算的时候要提前先减1,如果没有产生借位就正常计算。此时当前计算位的值为$(t+10)%10$,因为t>=0时就是t本身,t<0时那么就是借10过来,也就是在原来的基础+10即可
-
逐位相减
- 比较数的大小确定是否添加符号
- 对于减法而言,如果相减不够减的时候就要向前面借一位出来
- 从这里对比加法可以看出,每一位的组成是分两种情况:
- 如果$A_i-B_i>=0$,则$(A_i-B_i)$
- 如果$A_i-B_i<0$,则在原来的基础上加上10,则$(A_i-B_i+10)$
- 对于减法而言,A和B不同的顺序会导致最后计算的值不一样,有两种情况:
- $A-B>0$,直接减即可
- $A-B<0$,先计算B-A,再添加负号
- 总的来说,计算减法主要是把先计算$|A-B|$的值,再根据原来A-B的大小判断是否添加负号
- 计算完所有位数后处理前导0。
C++ 代码
/* Title: bigInteger_minus_template
* Author: @PommesPeter
* Data:2021-02-07
* */
#include <iostream>
#include <vector>
using namespace std;
//判断两个数哪个大
bool cmp(vector<int> &A, vector<int> &B) {
//A,B位数不相等那么哪个长就哪个数大
if (A.size() != B.size()) return A.size() > B.size();
//如果相等那么如果从最高位开始,如果A的最高位比B的最高位大那么说明A大
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 t = 0;
for (int i = 0; i < A.size(); i++) {
//做相减
t = A[i] - t;
if (i < B.size()) t -= B[i];
//t>=0 为t本身,t<0 t=t+10;
C.push_back((t + 10) % 10);
//如果发生了需要借前一位来进行计算的时候此时A[i]-B[i]<0,所以t<0时,t=1
//因为t=1之后在下一次循环计算的时候就会自动减1,否则就是t=0;
if (t < 0) t = 1;
else t = 0;
}
//去除前导零C的最后一个元素是0(C.back())
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main() {
string a, b;
vector<int> A, B;
cin >> 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');
//A>B直接算,A<B加符号反过来再算
if (cmp(A, B)) {
auto C = sub(A, B);
for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
} else {
auto C = sub(B, A);
printf("-");
for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
}
return 0;
}