What’s the 高精度?
高精度运算也称之为大数运算。即:在变量运算对象的数值范围为任何数据类型所无法容纳的情况下,采用整数数组存储(用字符串表示数字)。
首先来思考一下,如果我们在进行数学运算时,是如何做的,因为在高精度算法中我们用到这一方法
How?怎么做?(存储+计算+输出)
既然我们要计算,那么我们就要储存所要计算的数据,那如何储存,前文也说到了,当范围过大时,可能会超过int甚至时long long的范围,而数组的范围更大,所以我们可以把每一位数存储到一个数组中,不同的数组索引值对应的是不同位上的数,而我们又该如何储存呢?
下面,我会着重讲一下如何存储数字。
存储
对于int型变量的最大值为2^31 -1 = 2147483647,也就是说,只要数字超过2146483647,数据类型便无法容纳(这里以int型为例,long || long long同理)。
就拿2147483647这个10位数为例,对于int型来说确实很大,但如果把它换成strings呢?没错,相比之下小了很多很多,所以,我们可以把这个数当作一个字符串,然后在将每一位进行减’0’运算倒序存入数组中(为了避免错位操作,我们通常选择倒序储存)。
话不多说,上操作
int getNumber(int Number[]){
strings s;
cin>>s;
Number[0]=s.length();
for(int i=1;i<=Number[0];i++)
/*s.length()你可以直接改为Number[0],'0'你也可以改为48*/
Number[i]=s[s.length()-i]-'0';
}
可能有些朋友对于倒序存储不为理解,下面我来说一下,为什么要倒序存储
以加法为例,如果我们要进行加法运算的运算,我们会怎么计算呢?
没错,是这样计算,如果我们把他用计算机语言来表示,设a[]={3,3,7,8,9},b[]={2,2,3},那我们计算的时候,对应位置相加,那么a[1]+b[1]=5,明显错位。
当然,有点小伙伴会说我携程b[]={0,0,2,3}不就行了嘛,那如果位数过多呢?岂不是就要输出很多个0,也有小伙伴说,我直接末尾相加再倒数第二个相加(a[4]+b[2])也可以,但这样操作是不是很麻烦(还有其他原因,我就不多说了,可以自己去探索),所以我们可以选择倒序存储、倒序输出
输出
int putNumber(int Number[]){
if(Number[0]==0) return 0;
for(int i=Number[0]-1;i>0;i--) cout<<Number[i];
return;
}
加法
方向存储,数组相加,若有进位,下一索引值+1
void add(string aa,string bb){
int la=aa.size();
int lb=bb.size();
int lc=max(aa.size(),bb.size());
int a[100],b[100],c[100];
memset(a,-9999,sizeof(a));
memset(b,-9999,sizeof(b));
memset(c,0,sizoef(b));
for(int i=0;i<la;i++){
a[la-i]=aa[i]-'0';
}
for(int i=0;i<lb;i++){
b[la-i]=bb[i]-'0';
}
for(int i=1;i<=lc;i++){
c[i]=(a[i]+b[i])%10;//如果该位的和是个位数,则直接加上,如果是两位数,则取出各位
c[i+1]+=(a[i]+b[i])/10;//如果该位的和是两位,则直接取出十位数,加到下一位上
}
if(c[lc+1]>0&&c[lc+1]<10)lc++;
for(int i=lc;i>=1;i--) cout<<c[i];
}