大家好我是锁门黑我已经断更好久了最近发生了太多事情我就不再展开说了。因为最近事情挺多的再加上我已经主战小红书了所以以后我的更新频率和内容可能会断断续续在这里要跟大家道歉好了那我们就开始正文吧。今天我们来讲一个有意思的算法——高精度。由于高精度的内容比较多我会分成几期来讲。那我们今天先来讲高精度加法为什么说这个算法有意思呢众所周知大部分算法都难在思路比如稀疏表我现在都没学明白可是高精度却恰恰相反只要你学过数学你就基本明白这个算法的思路了。一.基本思路今天先讲高精度加法的思路。当你看到两个多位数相加时你会怎么做有朋友说用计算器那就算了吧。人家让你提交一段C代码你提交一个计算器网址那OJ不得姹紫嫣红啊玩笑OK言归正传我们正常的思路都是列一个竖式对吧。没错这就是高精度加法的基础思路了。但是真的这样就行么貌似不太行。你想想假如现在有一个加法问题12349045。你要是直接用这个顺序存数字数组如下a:1,2,3,4 b:9,0,4,5你要算这个的话首先你要倒着遍历很麻烦。其次你不确定会不会进位可能出现数组越界或者输出少一位。费力不讨好。那该怎么办我们不是怕数组越界么那我们把数字的存储给反过来是不是就不担心了所以我们只要把两个数字反过来储存就可以了。这就是高精度加法乃至整个高精度算法的关键一步——翻转。二.伪代码那这时候思路已经明朗我们就可以写一个伪代码了。输入两个数字字符串 翻转两个数字字符串 字符串转数组 把两个数字暴力加起来再处理进位数组 寻找和的最高位去除前导0 倒叙输出本人不太会写伪代码所以这个写得有一点儿奇怪(ToT)三.代码实现#includebits/stdc.h using namespace std; int N1001; int a[N],b[N],c[N1]; string x,y; int main(){ cinxy; reverse(x.begin(),x.end()); reverse(y.begin(),y.end()); for(int i0;ix.size();i)a[i]x[i]-‘0’; for(int i0;iy.size();i)b[i]y[i]-‘0’; int fsizemax(x.size(),y.size()); for(int i0;ifsize;i){ c[i]a[i]b[i]; if(c[i]10){ c[i]%10; c[i1]; } } int posN; while(!c[pos]pos0){ pos—; } for(int ipos;i0;i—){ coutc[i]; } return 0; }备注:本文为手机编辑所以可能会出一些小BUG可以反馈哈拜拜我们下期见下一期讲高精度减法