关于高精度计算的研究(1)——高精度加、减运算(2023-07-21)

发布时间 2023-07-21 22:42:47作者: Brownking

1、引入

在C++中,我们常会需要做加减乘除等等运算

首先我们来熟悉一下c++的计算符号:

+ (加号)                        - (减号、负号)                                   * (乘号)                                      / (除号)

() (括号)                        % (取余符)//例如5%2=1                   =    (赋值)                                   ==    (等于)//用于判断

 

特别注意:a/b如果a,b是整数,a/b系统会保留整数部分。

For example:

 

 #include <bits/stdc++.h>
 using namespace std;
 int main(){
     int a=3,b=2;
     cout<<"a="<<3<<"  "<<"b="<<2<<endl;
     cout<<"a-b="<<a-b<<endl;
     cout<<"a*b="<<a*b<<endl;
     cout<<"a/b="<<a
}

 

 

 

运行结果:

看起来很简单?

那如果a,b是几千亿的数呢?

这就行不通了!(不信自己试)

2、数据类型的极大值、极小值

首先,在讲高精度以前,我们先来认识一下比较常见的几种类型的最大值、最小值。

 

 正是因此,我们需要高精度计算。

加法

现在,我们来看看如何加。

 

我们想啊,题中给了一个条件:
image
那它肯定、肯定是不能使用常规的手法储存的,它的最大长度(501位)为远远超过 long long 类型的最大值。
我们要使用一些奇怪的东西,来储存它,比如说——字符串

前面我们有说过,string类型没有长度限制,那我们可以怎么操作呢?

思路

通用的思路,我们来模拟一下如何进行加法运算。

我们可以知道,加法可能会有进位
那进位能不能判断还不好说,所以我们考虑在数组中逆序存储,这样如果有进位会在结果的后面存储,最后输出时再逆序输出 ,就实现了存储。
为了方便,我建议大家把数组的每一位设置为0,可能会方便些。

 

如图示:

image

接下来,处理进位,逢十进一,当前的位取个位,后面的一位增加 1 。
imageimage

 

加法的代码实现

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int a[506], b[506];
int lena, lenb;
int m;
string a1, b1;

int main(){
    cin>>a1>>b1;//定义的字符串读入只可以用gets和cin,不能用scanf
    lena = a1.length();
    lenb = b1.length();
    for (int i = 0; i <= lena - 1; i++){
        a[lena - i - 1] = a1[i] -'0';
    }
    for(int i = 0; i <= lenb - 1; i++){
        b[lenb - i - 1] = b1[i] - '0';
    }
    if(lena >= lenb){
        for(int i = 0; i <= lena - 1; i++){
            int ss = a[i];
            a[i] = (b[i] + a[i] + m)%10;
            m = (ss + b[i] + m)/10;
        }
        if(m) a[lena] = m;
        else lena--;
        for(int i = lena; i >= 0; i--) printf("%d",a[i]);
        return 0;
    }
    else{
        for(int i = 0; i <= lenb-1; i++){
            int ss = b[i];
            b[i] = (b[i] + a[i] + m)%10;
            m = (ss + a[i] + m) /10;
        }
        if(m) b[lenb] = m;
        else lenb--;
        for(int i = lenb; i >= 0; i--) printf("%d",b[i]);
        return 0;
    }
    return 0;
}

减法

 

 

 

减法和加法的算法差不太多

代码如下:

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int N=205;
int main(){
    int i;
    int a[N],b[N],lena,lenb,x;
    char t[N],t1[N];
    scanf("%s %s",t,t1);
    lena=strlen(t);
    lenb=strlen(t1);
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(i=0;i<lena;i++)a[lena-i]=t[i]-48;
    for(i=0;i<lenb;i++)b[lenb-i]=t1[i]-48;
    i=1;x=0;
    while((i<=lena) or (i<=lenb)){
        a[i]=a[i]-b[i]-x;
        if(a[i]<0){
            a[i]+=10;
            x=1;
        }
         else x=0;
        i++;
    }
    bool f=false;
    for(i=N-1;i>=1;--i){
        if(a[i]!=0){
            printf("%d",a[i]);
            if(!f)f=true;
        }
         else if(f)printf("%d",a[i]);
    }
    if(!f)printf("0");
    return 0;
}

 

 《关于高精度计算的研究(2)——高精度乘、除运算》将于不久后写出