题目描述

高精除以高精，求它们的商和余数。

输入

输入两个低于300位的正整数。

输出

输出商和余数。

算法基本原理

算法基本原理：就是被除数能减去除数多少次，减的次数就是商，减完剩下的部分就是余数。

忘了大整数减法？点我

代码

#include<iostream>
#include<string>
using namespace std;

// 计算数a是否比数b大（或相等）
bool bigger(int a[], int b[], int aLen, int bLen){ 
    if(aLen < bLen){
        return 0;
    }else if(aLen > bLen){
        return 1;
    }else{
        for(int i=aLen-1, j=bLen-1; i>=0 && j>=0; i--,j--){
            if(a[i]<b[j]){
                return 0;
            }else if(a[i]>b[j]){
                return 1;
            }
        }
        return 1;
    }
}

//大整数减法，相当于a-=b。 
int sub(int a[], int b[], int aLen, int bLen){
    int ans[100]={0},maxLen=max(aLen,bLen);
    
    for(int i=0; i<maxLen; i++){
        if(a[i]<b[i]){
            a[i] += 10;
            a[i+1]--;
        }
        ans[i] = a[i] - b[i];
    }
    
    while(ans[maxLen-1] == 0 && maxLen > 1){
        maxLen--;
    }
    
    for(int i=0; i<maxLen; i++){
        a[i] = ans[i];
    }
    return maxLen;
}

int main(){
    string as, bs;
    int a[100]={0}, b[100]={0}, aLen, bLen, sum=0;
    
    //输入 
    cin>> as >> bs;
    
    aLen = as.length();
    bLen = bs.length();
        
    //倒序转int 
    for(int i=0; i<aLen; i++){
        a[aLen-i-1] = as[i] - '0';
    }
    
    for(int i=0; i<bLen; i++){
        b[bLen-i-1] = bs[i] - '0';
    }

    //去除前导0 
    while(a[aLen-1] == 0 && aLen > 1){
        aLen--;
    }
    
    while(b[bLen-1] == 0 && bLen > 1){
        bLen--;
    }
    
    //执行多次减法运算，每次a=a-b,直至a<b 
    while(bigger(a, b, aLen, bLen)){ 
        aLen = sub(a, b, aLen, bLen);
        sum++;
    }
    
    //输出
    cout << sum << endl; 
    for(int i=aLen-1; i>=0; i--){
        cout << a[i];
    }
    cout << endl;
    
    return 0;
}

不过，它存在两个问题：

问题1：慢

问题2：当商大于21.5亿时，结果会溢出

优化

优化思想例图

这种方法是可以将商10个10个，100个100个甚至100000000个100000000个运算，大大提高了效率。

#include <iostream>
#include <cstring>
using namespace std;

//去除前导0
int delPreZero(int x[], int xLen){
    int i=xLen;
    
    while(x[i-1]==0 && i>1){
        i--;
    }
    
    return i;
} 

//逆序输出数组值 
void printArr(int x[], int xLen){
    for(int i=xLen-1; i>=0; i--){
        cout << x[i];
    }
    cout << endl;
}

//若x>=y返回true，否则返回false 
bool compare(int x[], int y[], int xLen, int yLen){
    if(xLen < yLen){
        return false;
    }
        

    if(xLen == yLen){
        for(int i=xLen-1; i>=0; i--){
            if(x[i] > y[i]){
                return true;
            }
            if(x[i] < y[i]){
                return false;
            }
        }
        return true;
    }
    return true;
}

//若x>=y,则x的高位减去y（只减一次）,返回值为x的新长度
int sub(int x[], int y[], int z[], int xLen, int yLen){
    int zLoc = xLen - yLen ;    //商的位置 
    
    //若不够减，则商的位置后移一位 
    for(int i=1; i<=yLen; i++){
        if(x[xLen-i] > y[yLen-i])
            break;
        
        if(x[xLen-i] < y[yLen-i]){
            zLoc--;
            break;
        }           
    }
    
    if(zLoc<0) 
        return xLen;
        
    //当前被除数x的高位与除数y做一次减法运算 
    for(int i=zLoc,j=0; i<xLen && j<yLen; i++,j++){
        while(x[i] < y[j]){
            x[i+1]--;
            x[i] += 10;
        }
        
        x[i] -= y[j];
    }
    
    //商的相应位置加一 
    z[zLoc]++;
    
    //计算当前被除数x的真实长度 
    while(x[xLen-1]==0)
        xLen--;
    
    if(xLen <= 0)
        xLen = 1;
        
    return xLen;
} 

int main(){
    char as[301], bs[301];
    
    int a[301]={0}, b[301]={0}, c[301]={0};
    int aLen = 0, bLen = 0, cLen = 1, maxLen = 0;
    int i;
    
    //输入 
    cin >> as >> bs;
    aLen = strlen(as);
    bLen = strlen(bs);

    //被除数和除数分别逆序存放 
    for(i=0; i<aLen; i++){
        a[i] = as[aLen-1-i] - '0';
    }

    for(i=0; i<bLen; i++){
        b[i] = bs[bLen-1-i] - '0';
    }
    
    //去除前导0
    aLen = delPreZero(a, aLen);
    bLen = delPreZero(b, bLen);
    
    //通过从高位开始连续减去除数，计算商和余数 
    cLen = aLen - bLen + 1;
    while(compare(a, b, aLen, bLen)){
        aLen = sub(a, b, c, aLen, bLen);
    }
    
    //解决商的位数是0或负数的情况 
    if(cLen < 1){
        cLen = 1;
    }
    
    //去除商的前导0 
    cLen = delPreZero(c, cLen);
    
    //输出商c 
    printArr(c, cLen);
    
    //输出余数a 
    printArr(a, aLen);
    
    return 0;
}

速度测试

输入数据：
123456789
123

优化前

优化后

优化后的速度是优化前的17.5倍！
如果被除数更大，除数更小，优化后的提速效果更显著！

商溢出测试

输入数据：
123456789123456789123456789
123

优化后的算法没有溢出

商虽然远大于21.5亿，但它并没有发生溢出。优化前的算法根本跑不出结果来。

关键点

测试数据

特别鸣谢

测试数据提供： 挖坑大师——妈妈
推广平台提供： 简书
测试平台提供： 信息学奥赛一本通网站