十年老IT知识分享 – 【C++】高精度算法讲解

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];
}

正文完