題目描述

高精除以高精，求它們的商和余數(shù)。

輸入

輸入兩個(gè)低于300位的正整數(shù)。

輸出

輸出商和余數(shù)。

算法基本原理

算法基本原理：就是被除數(shù)能減去除數(shù)多少次，減的次數(shù)就是商，減完剩下的部分就是余數(shù)。

忘了大整數(shù)減法？點(diǎn)我

代碼

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

// 計(jì)算數(shù)a是否比數(shù)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;
    }
}

//大整數(shù)減法，相當(dāng)于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();
        
    //倒序轉(zhuǎn)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';
    }

    //去除前導(dǎo)0 
    while(a[aLen-1] == 0 && aLen > 1){
        aLen--;
    }
    
    while(b[bLen-1] == 0 && bLen > 1){
        bLen--;
    }
    
    //執(zhí)行多次減法運(yùn)算，每次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;
}

不過，它存在兩個(gè)問題：

問題1：慢

問題2：當(dāng)商大于21.5億時(shí)，結(jié)果會(huì)溢出

優(yōu)化

優(yōu)化思想例圖

這種方法是可以將商10個(gè)10個(gè)，100個(gè)100個(gè)甚至100000000個(gè)100000000個(gè)運(yùn)算，大大提高了效率。

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

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

//逆序輸出數(shù)組值 
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的新長(zhǎng)度
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;
        
    //當(dāng)前被除數(shù)x的高位與除數(shù)y做一次減法運(yùn)算 
    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];
    }
    
    //商的相應(yīng)位置加一 
    z[zLoc]++;
    
    //計(jì)算當(dāng)前被除數(shù)x的真實(shí)長(zhǎng)度 
    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);

    //被除數(shù)和除數(shù)分別逆序存放 
    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';
    }
    
    //去除前導(dǎo)0
    aLen = delPreZero(a, aLen);
    bLen = delPreZero(b, bLen);
    
    //通過從高位開始連續(xù)減去除數(shù)，計(jì)算商和余數(shù) 
    cLen = aLen - bLen + 1;
    while(compare(a, b, aLen, bLen)){
        aLen = sub(a, b, c, aLen, bLen);
    }
    
    //解決商的位數(shù)是0或負(fù)數(shù)的情況 
    if(cLen < 1){
        cLen = 1;
    }
    
    //去除商的前導(dǎo)0 
    cLen = delPreZero(c, cLen);
    
    //輸出商c 
    printArr(c, cLen);
    
    //輸出余數(shù)a 
    printArr(a, aLen);
    
    return 0;
}

速度測(cè)試

輸入數(shù)據(jù)：
123456789
123

優(yōu)化前

優(yōu)化后

優(yōu)化后的速度是優(yōu)化前的17.5倍！
如果被除數(shù)更大，除數(shù)更小，優(yōu)化后的提速效果更顯著！

商溢出測(cè)試

輸入數(shù)據(jù)：
123456789123456789123456789
123

優(yōu)化后的算法沒有溢出

商雖然遠(yuǎn)大于21.5億，但它并沒有發(fā)生溢出。優(yōu)化前的算法根本跑不出結(jié)果來。

關(guān)鍵點(diǎn)

測(cè)試數(shù)據(jù)

特別鳴謝

測(cè)試數(shù)據(jù)提供： 挖坑大師——媽媽
推廣平臺(tái)提供： 簡(jiǎn)書
測(cè)試平臺(tái)提供： 信息學(xué)奧賽一本通網(wǎng)站