<不用数组>的<高精度>加减法

先声明一下,本帖不是给大家抄答案AC用的,是用来拓展学习的,求管理员不要封QwQ

大家做高精度的时侯一般用的是:
字符串读入,逆序存到数组里,按位相加减……
这种用数组做的方法。

其实也可以不用数组做:

加法:

定义函数,传入两个string类型的参数。

string he(string a,string b){
	……
}

先记录a的长度和b的长度最大的值,
将a和b统一长度,
定义计算结果和进位值。

long long len=max(a.size(),b.size());
while(len-a.size())a='0'+a;
while(len-b.size())b='0'+b;
string t="";
bool jw=0;

for循环,i从0开始,i<len时执行,i++
计算a的len-1-i的值-‘0’+b的len-1-i的值-‘0’+进位值
这个值的%10计算结果上这个位置的值,所以将这个值%10+‘0’转char类型的值连接到计算结果的前面
这个值的/10进位,所以将这个值/10存到进位值里,进行下一次循环。

t=char((a[len-1-i]-'0'+b[len-1-i]-'0'+jw)%10+'0')+t;
jw=(a[len-1-i]-'0'+b[len-1-i]-'0'+jw)/10;

如果for循环结束了,而进位值还有值,那么将进位值+‘0’转char类型的值连接到计算结果的前面,最后返回就行了。

if(jw)t=char(jw+'0')+t;

减法:

跟高精度加法一样的,不过进位变成了退位,而且保证a>=b,那么 while(len-a.size())a='0'+a; 是可以省略的。

string cha(string a,string b){
	……
}

for循环,也是i从0开始,i<len时执行,i++
计算a的len-1-i的值-‘0’-退位值+(a的len-1-i的值-退位值<b的len-1-i的值)*10-(b的len-1-i的值-‘0’)
化简后应该是a的len-1-i的值-退位值+(a的len-1-i的值-退位值<b的len-1-i的值)*10-b的len-1-i的值
(a的len-1-i的值-退位值<b的len-1-i的值)*10表示如果这个位置上a的len-1-i的值-退位值不够减,则借一位加10再计算;
这个值就是计算结果上这个位置的值,所以直接将这个值+‘0’转char类型的值连接到计算结果的前面
如果这个位置上a的len-1-i的值-退位值不够减,则是借了一位加10才接着计算的,所以要记录一下,下一次计算就退一位。

t=char(a[len-1-i]-tw+(a[len-1-i]-tw<b[len-1-i])*10-b[len-1-i]+'0')+t;
tw=(a[len-1-i]-tw<b[len-1-i]);

因为减法计算出来的值可能前面会有0占位,所以要确定一下从哪开始返回,也有计算出来全是0的情况,所以要加一个i<计算结果的长度-1才执行的条件,i就是要开始返回的位置,将后面的字符串截取出来返回就行。

for(i=0;t[i]=='0'&&i<t.size()-1;i++);

注意:减法算出来的结果可能会是负数,所以要判断a<b(不是字典序,是数的大小)是否要交换变量并在前面加负号。
如:

if(a.size()<b.size()||a.size()==b.size()&&a<b){
	swap(a,b);
	jg="-";
}
jg+=cha(a,b);

相对于用数组写,这样应该更简便:
不用开范围、初始化,不用逆序,代码短,容易理解。
速度的话我觉得是这种快,感觉统一长度比逆序存贮快一丢丢。

4 个赞