浅谈高精度算法(加减乘除)

2019-08-16 07:57:27来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

浅谈高精度算法(加减乘除)

  在C/C++中,不时会遇到限定数据范围的情况,我们先来看看常用的int和long long两种数据类型的范围吧。

  C++标准规定,int占一个机器字长。在32位系统中int占32位,也就是4个字节,所以在32位系统中,int的范围是[-2^31,2^31-1],为10^9数量级;而long long的范围则是[-2^63,2^63-1],为10^18数量级,但当一些ACM/OI题目中测试数据范围超过此范围,甚至超过double(1.7*10^308数量级)时,该怎么办?Java有大数类,而python的整数也是不限制长度的,虽然C++的整数长度受到限制,但我们也有高精度算法,下面,我将介绍几种常见的高精度整算法。

  一、高精度加法。

  对于10^308以上的大数,确实不能用C++内置的数据类型直接处理,但回想我们曾经做过的小学算术问题,两个整数相加,先从个位算起,过十进位,依照这个思路,我们可以将大数存放在数组中,再利用数组去模拟加法运算的过程,代码如下:

#include<iostream>
#include<cstring>
using namespace std;
char s1[505],s2[505];
int a[505],b[505],c[505];
int main(){
    int m,n,v,t;
    std::ios::sync_with_stdio(false);
    cin>>s1>>s2;
    m=strlen(s1);
    n=strlen(s2);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
    for(int i=0;i<m;i++){
        a[m-1-i]=s1[i]-'0';
    }
    for(int i=0;i<n;i++){
        b[n-1-i]=s2[i]-'0';
    }
    m=max(m,n);
    m++;
    memset(c,0,sizeof(c));
    for(int i=0;i<m;i++){         
        v=a[i]+b[i];
        if((c[i]+v)<10)
            c[i]+=v;
        else{
            c[i+1]+=(c[i]+v)/10;
            c[i]=(c[i]+v)%10;        
        }    
    }        

//下面是一种更简单的做法,结果直接储存在a中 /*for(int i=0;i<m;i++){ a[i]+=b[i]; a[i+1]+=a[i]/10; a[i]%=10; }*/ if(c[m-1]==0) m--; for(int i=m-1;i>=0;i--) cout<<c[i]; return 0; }

  二、高精度减法。

  和高精度加法的基本思路相同,不过在减法中,需要确定输入数字的相对大小来判断是否输出负号,还需要注意是否要"借位"。上代码:

#include<iostream>
#include<cstring>
using namespace std;
bool compare(char s1[],char s2[]){
    int u=strlen(s1),v=strlen(s2);
    if(u!=v)
        return u>v;
    for(int i=0;i<u;i++)
        if(s1[i]!=s2[i])    return s1[i]>s2[i];
    return true;
}                                                  //比较两个数相对大小 
int main(){
    std::ios::sync_with_stdio(false);
    int flag=1,i,j;
    char s1[100005],s2[100005],s3[100005];              //这里为节省空间考虑,直接用char数组运算 
    cin>>s1>>s2;
    if(compare(s1,s2));
    else{
        flag=-1;
        strcpy(s3,s1);
        strcpy(s1,s2);
        strcpy(s2,s3);
    }
    int u=strlen(s1),v=strlen(s2);
    for(i=u-1,j=v-1;j>=0;i--,j--){
        if(s1[i]<s2[j]){
            s1[i-1]-=1;
            s3[i]=s1[i]-s2[j]+10+'0';
        }
        else    s3[i]=s1[i]-s2[j]+'0';
    }                                                  //从最后一位向前减 
    for(;i>=0;i--)    {
        if(s1[i]<'0'){
            s1[i-1]-=1;
            s3[i]=s1[i]+10;
        }
        else    s3[i]=s1[i];
    }                                                  //s1数位大,所以还有s1减'0' 
    for(i=0;i<u-1&&s3[i]=='0';i++);                     //只到u-1的原因时 
    if(flag==-1)    cout<<'-';
    cout<<s3+i;
    return 0;
}

  三、高精度乘法。

  依旧是模拟算术做竖式乘法的过程,要注意进位,贴代码:

#include<iostream>
#include<cstring>
using namespace std;
char a[2005],b[2005];
int c[2005],d[2005],e[4005];
int u,v,w;
int main(){
    int i,j;
    cin>>a>>b;
    u=strlen(a);
    v=strlen(b);
    memset(c,0,4005);
    for(int i=0;i<u;i++)
        c[u-1-i]=a[i]-'0';
    for(int i=0;i<v;i++)
        d[v-1-i]=b[i]-'0';
    for(i=0;i<u;i++){
        for(j=0;j<v;j++){
            w=c[i]*d[j];
            if(e[i+j]+w<10)    e[i+j]+=w;
            else{
                e[i+j+1]+=(e[i+j]+w)/10;
                e[i+j]=(e[i+j]+w)%10;
            }
        }
    }
    for(i=u+v-1;i>0&&e[i]==0;i--);            //此处是为了不漏掉输出结果为0而将条件写为i>0 
    for(;i>=0;i--)    cout<<e[i];
    return 0;
}

  四、高精度除法。

  高精度除法分两种,都是仿照竖式除法实现,一种是高精度除以低精度,较为容易实现,主要是利用一个数,在线处理:

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
char s1[5005];
int a[5005],b,c[5005],x=0;
int main(){
    cin>>s1>>b;
    a[0]=strlen(s1);
    for(int i=1;i<=a[0];i++)    a[i]=s1[i-1]-48;
    memset(c,0,sizeof(c));
    for(int i=1;i<=a[0];i++){
        c[i]=(x*10+a[i])/b;
        x=(x*10+a[i])%b;  
    }                              //核心部分
    x=1;
    while(c[x]==0&&x<a[0])    x++;
    for(;x<=a[0];x++)    cout<<c[x]; 
    return 0;
}

  另一种,是运用逐次相减的方法确定出商和余数,代码如下:

#include<iostream>
#include<cstring>
using namespace std;
int a[5005],b[5005],c[5005],d[5005];
bool compare(int a[],int b[]){
    if(a[0]!=b[0])    return a[0]>b[0];
    for(int i=a[0];i>0;i--){
        if(a[i]!=b[i])    return a[i]>b[i];
    }
    return true;
}
int main(){
    std::ios::sync_with_stdio(false);
    string s1,s2;
    cin>>s1>>s2;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    a[0]=s1.length();
    b[0]=s2.length();
    for(int i=1;i<=a[0];i++)    a[i]=s1[a[0]-i]-'0';
    for(int i=1;i<=b[0];i++)    b[i]=s2[b[0]-i]-'0';
    c[0]=a[0]-b[0]+1;
    for(int i=c[0];i>0;i--){            //c[0]代表最初a,b的数位差 
        memset(d,0,sizeof(d));
        for(int j=1;j<=b[0];j++)
            d[j+i-1]=b[j];
        d[0]=b[0]+i-1;                           //先让b中存下的数与a在一个数量级 
        while(compare(a,d)){                    //比较,如果a比较大,用a直接减去d,如果a比较小,下一次大循环中,d的位数会减一 
            c[i]++;
            for(int i=1;i<=a[0];i++){
                a[i]-=d[i];
                if(a[i]<0){
                    a[i+1]--;
                    a[i]+=10;
                }
            }
            while(a[0]>0&&a[a[0]]==0)    a[0]--;
        }
    }
    while(c[0]>1&&c[c[0]]==0)    c[0]--;
    cout<<"商:";
    for(int i=c[0];i>0;i--)    cout<<c[i];
    cout<<endl<<"余数:";
    for(int i=a[0];i>0;i--)    cout<<a[i];           //a中最后剩下的就是余数  
    return 0;
}

  好的,高精度基础算法介绍完毕,大家不妨自行动手一试。


原文链接:https://www.cnblogs.com/thereal/p/11294746.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:dfs/bfs专项训练

下一篇:「中山纪中集训省选组D2T1」书堆 欧拉常数