【算法分析】
(1)C++不支持大数运算,故而引入高精度算法。
(2)高精度算法将大数以字符串形式输入,然后拆分转换为一位一位的整数,之后按照小学的竖式运算方法进行计算。(注意:字符串中 0 下标从左开始,竖式运算中 0 下标从右开始,故代码中需要有一个逆序(reverse)操作。)
(3)对最高位做判断,然后输出便得结果。
代码 while(c.size()>1 && c.back()==‘0’) c.pop_back(); 用于去除前导 0。因为两数相减后,左边若干位(即高位)有可能变为 0,故必须去除。
(4)在输入为 “321 159” 时,本高精度减法模拟执行过程如下所示:
input:
321 159
procedure:
t=-8 c=2
t=-4 c=26
t=1 c=261
output:
162
(5)据本题代码编写思路,此高精度减法函数 hiSub() 在进行计算时,永远是“大数 - 小数”。请按此理解代码。
(6)代码 t<0?t=1:t=0; 反映了两数相应位相减后的“借位”情况。若两数第 i 位相减后的值 t 为负数,说明要借位,则在根据 t 计算出对应的 c+=((t+10)%10+‘0’); 后,将 t 置为 1,为第 i-1 位的计算做准备。否则,将 t 置为 0。
【算法代码】
#include <bits/stdc++.h>
using namespace std;
bool cmp(string a, string b) {
if(a.size()!=b.size()) return a.size()>b.size();
for(int i=0; i<a.size(); i++) {
if(a[i]!=b[i]) return a[i]>b[i];
}
return true; //a=b
}
string hiSub(string a,string b) {
string c;
int t=0;
int i=a.size()-1, j=b.size()-1;
while(i>=0 || j>=0) {
if(i>=0) t=(a[i]-'0')-t;
if(j>=0) t-=(b[j]-'0');
c+=((t+10)%10+'0');
t<0?t=1:t=0;
i--, j--;
}
while(c.size()>1 && c.back()=='0') c.pop_back();
reverse(c.begin(),c.end());
return c;
}
int main() {
string a,b;
cin>>a>>b;
if(cmp(a,b)) cout<<hiSub(a,b)<<endl;
else cout<<"-"<<hiSub(b,a)<<endl;
return 0;
}
/*
in:
23 123
out:
-100
*/