基础算法-高精度：高精度减法

P2142 高精度减法

题目链接：P2142 高精度减法 - 洛谷

高精度的题目解法和之前高精度加法的解法基本相同，所以就不再过多讲解原理了。

解法：模拟列竖式计算的过程。

①先用字符串读入，然后拆分每一位，逆序放在数组中。

但是我们需要提前判断a与b的大小，要让大的减小的，所以需要先进行判断。

我们在比较数字大小时，最简便的方法就是：先比较两者有多少位，如果相同，再从高到低依次比较。

由于我们要把a和b先读取为字符串，所以我们可以直接先比较a字符串与b字符串的长度（用size()函数），如果相同，直接用return a<b;因为在string中重定义了<，我们可以直接使用它来比较！

#include<iostream> #include<string> using namespace std; const int N = 1e6 + 10; int a[N], b[N], c[N]; int la, lb, lc; //比较两个数字的大小 bool cmp(const string& x, const string& y) { //比较长度 if (x.size() != y.size())return x.size() < y.size(); //按照字典序的方式比较 return x < y; } int main() { string x, y; cin >> x >> y; if (cmp(x, y)) { //如果x<y则需要交换x,y swap(x, y); //记得输出'-'，因为已经确定x<y，所以运算结果中必定有- cout << '-'; } //拆分每一位，逆序放到数组中 la = x.size(); lb = y.size(); lc = max(la, lb); for (int i = 0; i < la; i++) { a[la - i - 1] = x[i] - '0';//x[i]为字符! } for (int i = 0; i < lb; i++) { b[lb - i - 1] = y[i] - '0'; } //模拟减法过程 sub(c, a, b);//c=a-b; //输出结果 for (int i = lc - 1; i >= 0; i--) { cout << c[i]; } return 0; }

接下来就完善减法过程了。

②利用数组，模拟列竖式减法的过程

（1）先是对应位相减，如果结果小于0，则需要借位；（记得是+=a[i]+b[i]，因为如果该位置被前一位借位了，这个位置为-1！）

（2）处理借位，该位置后面一个位置-1，然后这个位置+10（c[i]+=10）

完善逻辑后的结果为：

#include<iostream> #include<string> using namespace std; const int N = 1e6 + 10; int a[N], b[N], c[N]; int la, lb, lc; //比较两个数字的大小 bool cmp(const string& x, const string& y) { //比较长度 if (x.size() != y.size())return x.size() < y.size(); //按照字典序的方式比较 return x < y; } //高精度减法的模板- c=a-b void sub(int c[], int a[], int b[]) { for (int i = 0; i < lc; i++) { c[i] += a[i] - b[i]; if (c[i] < 0) { --c[i + 1];//借位 c[i] += 10; } } } int main() { string x, y; cin >> x >> y; if (cmp(x, y)) { //如果x<y则需要交换x,y swap(x, y); //记得输出'-'，因为已经确定x<y，所以运算结果中必定有- cout << '-'; } //拆分每一位，逆序放到数组中 la = x.size(); lb = y.size(); lc = max(la, lb); for (int i = 0; i < la; i++) { a[la - i - 1] = x[i] - '0';//x[i]为字符! } for (int i = 0; i < lb; i++) { b[lb - i - 1] = y[i] - '0'; } //模拟减法过程 sub(c, a, b);//c=a-b; //输出结果 for (int i = lc - 1; i >= 0; i--) { cout << c[i]; } return 0; }

如果此时复制代码到题目上会有：

为什么？

我们可以发现：如果最高位相减如：9-9最终结果为0，而我们输出的时候这个0是需要省略的！也就是说如果999-997最终结果应该为2，而这样输出结果为002；其次，如果a==b，也就是说999-999最终得到的结果是0，而如果把所有0省略，那么最终没有输出，所以我们需要再加个条件lc>1，并使用while循环来去掉前置0，我们可以使用--lc的方式来去掉多余的前置0：

#include<iostream> #include<string> using namespace std; const int N = 1e6 + 10; int a[N], b[N], c[N]; int la, lb, lc; //比较两个数字的大小 bool cmp(const string& x, const string& y) { //比较长度 if (x.size() != y.size())return x.size() < y.size(); //按照字典序的方式比较 return x < y; } //高精度减法的模板- c=a-b void sub(int c[], int a[], int b[]) { for (int i = 0; i < lc; i++) { c[i] += a[i] - b[i];//对应位相减，然后借位 if (c[i] < 0) { --c[i + 1];//借位 c[i] += 10; } } //处理前导零 while (lc > 1 && c[lc - 1] == 0) { --lc; } } int main() { string x, y; cin >> x >> y; if (cmp(x, y)) { //如果x<y则需要交换x,y swap(x, y); //记得输出'-'，因为已经确定x<y，所以运算结果中必定有- cout << '-'; } //拆分每一位，逆序放到数组中 la = x.size(); lb = y.size(); lc = max(la, lb); for (int i = 0; i < la; i++) { a[la - i - 1] = x[i] - '0';//x[i]为字符! } for (int i = 0; i < lb; i++) { b[lb - i - 1] = y[i] - '0'; } //模拟减法过程 sub(c, a, b);//c=a-b; //输出结果 for (int i = lc - 1; i >= 0; i--) { cout << c[i]; } return 0; }

这样就可以运行成功了！

每次写这种题目的时候我们都要想到边界情况，不要盲目写即可。