题解 /【学习笔记】-- 高精度减法

# 题解 /【学习笔记】-- 高精度减法 ## 修改日志： - 1、19/3/31 修改：优化了批注，写的更易懂一些。 - **2、19/8/8 修改：增加了图片，细节更多，调整码风，解决了一些小BUG，科普了一些~~无关紧要~~的知识。（重大修改）** ------------ - ## 1、$int$的悲伤与高精度的需求。 我们往常在作运算的时候，往往直接用运算符完成运算（譬如a - b）。这当然非常地简便。 但是当**数据范围特别大**的时候，你去用运算符做减法往往得不到正确的结果，**为什么？？** 首先，在$c++$里，每一种实数变量型都是有一个数据储存范围的。**譬如$int$型，它的数据范围就为 $-2147483648 < int < 2147483647$，也就是 $-2^{31} < int < 2^{31} -1$。一旦你给一个int型变量存一个大于这个范围的数，它就会产生溢出，然后你存的数字会变成另外一个非常神奇的数字** 。可以自己在线下试一试哦。 ~~不要和我提Py和java！~~ 这个时候，你存的数字本身就已经发生错误，就不用指望他来运算了。 当然也有解决办法，譬如开$long long$。但是当数据范围高到恐怖的地步的时候（甚至大于$10^{1000}$），别说$long long$了，开挂神器__$int128$都救不了你。 这个时候，就需要高精度算法来解决问题。 ------------ - ## 2、数组搞定高精度数字 上面我们有提到过，在数据范围很大的时候，任何变量型已经无法满足我们的需求。这个时候怎么办？ 接下来介绍一种最传统的做法：开数组。 我们开一个数组。这个数组开到多大？就要看你要存的数的位数有多少。若想存一个$2000$位的数，就把数组开到$2000$以上。 你位数可以多啊，你多一位 位数，我就把数组多开一个空间。~~看谁斗得过谁~~ 而本题甚至开到了$10086$位，所以我选择把数组开到$10500$位。（开多点没坏处） **想必这样说大概都清楚了。我们用数组的每一个空间来存每一位数的那个数字。** 这句话是什么意思呢？我们打个比方。 比如说我们现在要存$123$这个数，把它存进$na$数组里。 我们可以取出最后一位（个位）$3$，放到$na[1]$中。于是$na[1] = 3$ 同理，我们取出$2,1$放进数组，于是就有： ```cpp na[1] = 3; na[2] = 2; na[3] = 1; //也就是: na[MAXN] = {3, 2, 1}; ``` **此时，$na[i]$就代表了此数的最后$i$位** ### 但是 **我们并不选择直接一个一个输入每位数字，把数字存进数组。** 我们选择使用**字符串** ，像这样： ```cpp string a, b; cin >> a >> b; for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0'; for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0'; //这个代码底下有解释 ``` **为什么这样做？** 首先，**字符串输入两个数字，我们可以直接地知道每个数字的长度，也就是位数**（字符串$a$的长度为$a.size()$，依次类推）。**知道长度就可以直接给$for$循环服务。** 其次，字符串它输入方便啊，一个$cin$就完成了，也不必去检验什么输入到空格之类的了。 当然，最方便的是可以将字符串扔进子函数里（这个在最后有拓展） **当然：将字符串转化进数组需要一定技巧：** 1、首先，字符串里同样可以用下表形式表示某位的数（譬如$a[i]$），**但是和我们之前的存法相反，$a[0]$ 表示的数字的最高位，次高位是$a[1]$。他是从$0$且是从高位算起的，和我们之前说的从低位开始存恰好相反。** 2、其次，字符串里每个数其实都是$char$型的。虽然看起来和$int$型没什么不同，**但是想把$char$型转化成$int$型需要通过一个介质：$ASCII$码。** 每个$char$字符都有对应的$ASCII$码，而$0-9$的$ASCII$码是$48 - 57$。**如果你尝试把一个$char$型的$0$存进$int$，那么存进去的则是$0$的$ASCII$码，也就是$48$。** 这两个情况怎么解决？ - **1、第一个问题，我们只需要把数组的第$i$位和字符串的第（位数 $- i$）位对应起来就可以了。这是很好证明的。** 假设我们要存一个$3$位数，它的每一位： 用数组表示：$na[1], na[2], na[3]$ 用字符串表示:$a[3 - 1], a[3 - 2], a[3 - 3]$**（这里千万要注意字符串下标是从$0$开始存的，也就是$a[0]$表示最高位）** 代码中手打出来就可以了。 - 2、第二个问题，$0-9$的$ASCII$码不是$48 - 57$么，那么把字符引入$int$型的时候，**我们只需要引入时把每个数减去$48$就行了。** $48-57$减去$48 = 0-9$ 道理都懂，对吧。 **当然你可以把$48$写成$'0'$。$'0'$就代表着$0$的$ASCII$码** **于是这就有了我上面给出的代码：** ```cpp string a, b; cin >> a >> b; for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0';//其实这里正这倒着循环真的无所谓 for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0'; ``` - **于是乎，我们就有了两个数组，存了两个高精度数字。** - ## 3、小学计算教你做减法 **数字存进数组去了，那么问题来了，如何让两个数组作减法？？** 答案很简单：**小学竖式运算！** ~~什么？你居然教我减法用竖式？？？~~ 好吧，可能各位做减法熟能生巧，不需要列竖式就可以口糊出来。但是你要知道，计算机并不会做数组相减的运算。于是我们就需要“教他”算。 小学老师怎么教你算减法？当然是竖式运算。 具体做法就是：**把两个数字的每一位对齐，从低位到高位，同一位逐次相减，如果减不够就向后一位借位。**（小学竖式借位甚至还要向借的位打标记防止你忘了） 计算机的竖式运算同样是这个道理。我们假设有两个存了数字的数组$na,nb$。 我们把两个数的每位对齐，刚刚我们提到：$na[i]$代表$a$这个数的第$i$位。同理：$nb[i]$代表$b$这个数的第$i$位。 **那么，我们只需要做的就是$na[i] - nb[i]$就行了。这就代表了$a$的第$i$位减去了$b$的第$i$位** 我们用表格演示一下$456789$减去$135353$，其中，$ans$数组用来存储答案  可以看到，每一位依次相减，最后传进答案数组，这个相减的过程就完成了。 用代码表示，可以表示成： ``` ans[i] = na[i] - nb[i]; ``` ### 可是！以上问题没有考虑过借位的情况！ 如果要借位，我们怎么处理？？ 根据小学竖式~~的博大精深~~来看，我们可以向高位借位，然后再相减。 这个**借位**如果要说明白点，就是高位减去一个$1$，给低位一个$10$加上然后再相减。 具体的，如果运算$34 - 19$，$4 - 9$明显减不够，于是： ``` 34 - 19 = (30 + 4) - (10 + 9) = (20 + 14) - (10 + 9) = (20 - 10) + (14 - 9) = 10 + 5 = 15 ``` 上面的例子中，$30$很明显借了$10$给$4$，然后$14$ - $9$进行运算 这个东西放到我们数组相减也适用。**简单来说，当一位减不够另一位时，就从高位借$10$过来再减，当然，高位会比原来少$1$**。 我们再用表格举个例子：$456789 - 147791$  这样就成功处理了减位的问题。 用代码就这样表示： ``` int maxl = max(a.size(), b.size()); /* 找到两个数中的最大位，为for循环服务 如果两个数位数不相等，相减也无妨，因为位数少的数那部分被0补齐，减下去不影响 */ for(int i = 1; i <= maxl; i ++) { if(na[i] < nb[i])//减不够 { na[i + 1] --;//借位 na[i] += 10;//到低位去 } ans[i] = na[i] - nb[i];//相减 } ``` **于是，相减代码就是这样了** - ## 4、看似已完成，输出却全是坑 你以为这样就做完了？评测姬告诉你：**Too Young Too Simple** **输出里还有一些坑，把你坑的头皮发麻。** 平常的输出方式是什么？我们现在知道了两个数的最大位，上面也有提到过。我们用$maxl$表示。 **因为我们是从个位，逐渐递增存每位上的信息，但是我们要从最高位开始输出，也就是我们要先输出最高位。** 这倒是和字符串有点相似。 于是我们采用倒着输出方法，代码大概是这个样子。 ``` for(int i = maxl; i > 0; i --)cout << ans[i]; ``` 但是！坑来了。 - ### **坑点1、** **如果你用$10001 - 10000$，会发生什么？** 当然你会知道它应该输出$1$。可你的计算机不这么认为。 依照上面的输出方法，此时$maxl$为$5$。**那么，它输出的就不是$1$，而是$00001$！**，因为他会输出$maxl$次，也就是$5$次，并且是从$ans[5]$ 输到 $ans[1]$。**但此时：$ans[2]-ans[5]$都已经为$0$** 所以我们不得不考虑，在相减后位数下降的情况下，不特殊处理就会多输出若干个$0$。 解决方法很简单，输出前加上这么一句话即可： ```cpp while(ans[maxl] == 0)maxl --; //如果最高位为0，就一直减小最高位，直到不为0为止。 ``` 由于$maxl$直接为输出的$for$循环服务，减小$maxl$相当于减少了循环输出次数。最后，$ans[maxl]$会停留在第一个不为$0$的位置。 - ### **坑点2、** 上面的坑点提到要去除多余的前导零，**但是，是不是所有的前导零都是多余的？** **要是答案输出本身就为$0$，前导零就是他本身。这个时候我们仍然要输出一个$0$。** ，如果我们不处理这个地方，**上面处理前导零的代码就会把需要输出的$0$也给处理掉。** **也就是说，当两减数相等，答案为$0$，不处理这个地方，代码什么都不会输出。** 所以我们要在最后输出时这么写： ```cpp if(maxl < 1)cout << "0"; //最大位小于1，也就是最高位为0时输出。 //最高位为0，显而易见答案就为0了 //这种情况下前面什么都不会输出，这里额外输出一个0倒也无伤大雅 ``` - ### **坑点3、** 这里还有一个坑，**那就是：相减可能小于$0$** 显然，**我们用上面的相减代码是处理不掉这种情况下的。** 那怎么办？ 这个时候就需要手动加特判了。 稍微想一下，只有在数字 $b > a$的情况下，$a - b$才可能为负。于是我们可以用非常玄学的运算式： $(a - b)= - (b - a)$ 如何实现这个操作？我们在判断 $b > a$ 成立后，可以调用函数$swap$交换$a，b$，然后再用一个判断$bool$型变量打上标记。 交换过后，很明显，运算变为 $b - a$ ，而 $b > a$，显然运算不会出错。最后输出的时候，只需要在前面加一个负号即可。 ``` bool pd; if((a < b && a.size() == b.size()) || a.size() < b.size()) { swap(a, b);//swap函数作用：交换两数 pd = true;//打上标记 } //----中间省略一堆计算代码----- if(pd == true)cout << "-"; //b > a时，a - b < 0，打头输出负号 //----后面省略一堆输出代码----- ``` 这里需要一提的是判断 $b > a$的方法。很显然，这里$a，b$都是字符串$string$型。为什么要这么写？ 这里涉及**字典序**的比较大小方式。$string$类型不是不能比大小，而是规则上有所不同 粗略地概括一下： **从最高位比起，$ASCII$码更大的字符串更大。如果相等，比次高位，以此向下类推。** **所以在$string$中，串 $9 > 89$ 。因为最高位$9 >8$** 当然，像前面几个数如果都相等，位数更大的显然更大。 例如$1234500 > 12345$ **所以说：在位数相等的时候，我们可以直接利用字符串比大小的性质，来比较两数大小，但又要防止出现 $9 > 89$ 这种情况，所以还要保证位数大的数值才更大** 综上所述，得出这么一句判断。 到此为止：我们得出来了高精度的$AC$代码 - ## 上代码！ ```cpp #include<bits/stdc++.h> #define mian main #define QWQ puts("QWQ"); #define MAXN 10500 //define是宏定义，define a b的作用是把a代替为b执行。 //这里的意思是把MAXN替换成10500执行 //请无视上方两个的宏定义（QWQ） using namespace std; string a, b; //选择字符串。因为字符串储存了每个串的长度，可以直接调用。 int na[MAXN], nb[MAXN], ans[MAXN]; bool pd; int main() { cin >> a >> b; if((a < b && a.size() == b.size()) || a.size() < b.size()) { swap(a, b); pd = true; } for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0'; for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0'; //将字符串中的信息转化到数组中，数组模拟数字。 int maxl = max(a.size(), b.size()); //找到两个数中的最大位，为for循环服务 for(int i = 1; i <= maxl; i ++) { if(na[i] < nb[i]) { na[i + 1] --; na[i] += 10; } ans[i] = na[i] - nb[i]; } while(ans[maxl] == 0)maxl --;//防止减后降位，多输出若干0 if(pd == true)cout << "-";//b>a时，a - b < 0 所以打上负号 for(int i = maxl; i > 0; i --)cout << ans[i]; if(maxl < 1)cout << "0"; return 0; } ``` - ## I Need More！！！ 这个代码的确可以$AC$整道题，但是并不是完美的高精度减法。 - **当我们需要多次调用高精度运算时，这种写法就显得鸡肋了。** - **并且，它并不能处理 $a$ 或 $b$ 为负数的情况。** - ~~最重要的是，换种写法逼格更高~~ 但是这里就不写了，我挂在底下，有需求的可以自行了解哦（主要怕占版面太多 QWQ ） ## [“就这么点东西根本无法满足我”](https://www.luogu.org/blog/stonejuice/gao-jing-du-jian-fa-di-op-xie-fa) - ## 特别鸣谢： - 洛谷提供的平台 - 管理员的辛勤审核 - 大家的支持（没有大家的支持，我可能没有动力去更新Updata） 希望大家能在评论区留言讨论，我会尽量看的！