提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【C++】高精度算法讲解

2023-02-19 12:20:35 时间

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

相关文章