关于大数问题的个人理解

缺乏、安全感 2022-03-07 03:46 230阅读 0赞

大数问题也不是第一次接触过，但是只是零零碎碎的做过几道题，并没有很系统的整理过，并且自己的处理上多多少少存在很多瑕疵，所以这里做一个整理；

一、大数的存储：  
相应的，大数存储应该将每一位存储在数组之中，但是需要注意的时，数组存储时从0开始，所以大数存储应该时数字的逆向存储；  
之前自己时正向存储，所以会在计算进位上造成麻烦，逆向存储可以很好的存储和管理进位问题；  
\`struct bign\{

int d[1000];
    int len;
    bign(){
        memset(d,0,sizeof(d));
        len=0;
    }

\};\`  
这里使用了构造函数，来保证结构体创立的时候能够第一时间初始化；

对于初始化读入数字的时候，我们也需要对数字进行逆序处理；

struct bign{
        int d[1000];
        int len;
        bign(){
            memset(d,0,sizeof(d));
            len=0;
        }
    };

所以对于不同的两个数字，我们比较的方式可以有如下定义：  
如果长度不一样，则长的大；  
如果长度相同，则从高位开始逐个比较（也就是反向枚举），从而找出数字大的；

int compare(bign a,bign b){
        if(a.len>b.len)
            return 1;
        else if(a.len<b.len){
            for(int i=a.len-1;i>=0;i--){
                if(a.d[i]>b.d[i])
                    return 1;
                else if(a.d[i]<b.d[i])
                    return -1;
            }
            return 0;
        }
    }

二、加法运算：  
对于加法，我们一定要注意进位问题，并且当一正一负的时候可以直接做减法运算，都为负数加和后加上符号即可；  
如下所示

bign add(bign a,bign b){
        bign c;
        int carry=0;//carry位进位位
        for(int i=0;i<a.len||i<b.len;i++){
            int temp=a.d[i]+b.d[i]+carry;//一定要加上上一位的进位;
            c.d[c.len++]=temp%10;
            carry=temp/10;//计算进位
        }
        if(carry!=0){
            c.d[len++]=carry;
        }
        return c;
    }

值得注意的使上面的循环操作，由于最短数字的后面都为0，所以相当于直接加上长的哪一位本位的元素，再加上进位（当短的遍历完之后carry恒为0）  
后面的if判断意为如果两个数字序列长度相等，则应该在新开辟更高一位存储进位；

三、减法运算：  
减法运算和加法运算大致相同，从序列低位开始，但是需要注意的使拥有借位思想；  
并且，当被减数小于减数的时候，应该交换位置进行相减，并且只需要输出一个负号即可；

bign sub(bign a,bign b){
        bign c;
        for(int i=0;i<a.len||i<b.len;i++){
            if(a.d[i]<b.d[i]){
                //需要借位；
                a.d[i+1]--;
                a.d[i]+=10;//当前位加十
            }
            c.d[c.len++]=a.d[i]-b.d[i];
        }
        while(c.len-1>=1&&c.d[c.len-1]==0){
            c.len--;
        }
    }

注意点有两处：  
1.这里的借位是相邻高位-1，本位+10相减的操作；  
2.由于可能有高位相减=0，但是len任然计数的可能性存在，所以要从高位开始，除去高位的前导0；

四、高精度和低精度乘法运算：  
这里所谓的高精度就是采用数组保存的大数，而低精度就是使用int保存的数字；  
假设，数组保存的数有三位，int保存的的数字有二位，和普通小学数学乘法不同的是，我们采用的是int保留的两位，逐个对数组保存的三位进行乘积，这样就会进行三次运算，而不是手写运算的两次；

bign multi(bign a,int b){
        bign c;
        int carry=0;
        for(int i=0;i<a.len;i++){
            int temp=a.d[i]*b+carry;//个位进行结果
            carry=temp/10;
        }
        while(carry!=0){
            c.d[c.len++]=carry%10;
            carry/=10
        }
        return c;
    }

其实和加法运算类似；  
需要注意的是当计算完毕，但是carry不为0的时候，最后操作相当于将carry逐位送入高位；

五、高精度和低精度除法：  
和手写除法类似，当该位不够除的时候，保留该位，置商为0，和下一位构成一个数，看是否够除，所以本质看来，代码里应该是对余数来进行除法操作；

bign divide(bign a,int b,int&r){
        //r为余数
        bign c;
        c.len=a.len;//和被除数一一对应
        for(int i=a.len-1;i>=0;i--){
            r=r*10+a.d[i];
            if(r<b)
                c.d[i]=0;
            else{
                c.d[i]=r/b;
                r=r%b;
            }
        }
        while(c.len-1>=1&&c.d[c.len-1]==0){
            c.len--;
        }
        return c;
    }

这里需要注意的是高位仍然需要除去0操作；  
在包括0的情况下，商的位数应该和被除数的位数一一对应，这也就是我们的边界判别条件之一；