欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-10-31 17:53:34
在C/C++中,不时会遇到限定数据范围的情况,我们先来看看常用的int和long long两种数据类型的范围吧。 C++标准规定,int占一个机器字长。在32位系统中int占32位,也就是4个字节,所以在32位系统中,int的范围是[-2^31,2^31-1],为10^9数量级;而long long ......

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

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