跳至正文
View Categories

2 min read

主要内容 #

  1. 高精度除以单精度例题精讲
  2. 高精度除以高精度例题精讲

1. 高精度除以单精度例题精讲 #

1.1 计算过程 #

1.输入大整数的数字串和整数b。用string存储大整数的数字串，用int存储整数b
2.将数字串从低位往高位存储到数组a中
3.利用竖式计算，c=a/b
（1）首先，另余数为x=0；
（2）让余数乘以10，和高位的第一个位置的数相加，然后除以b，得到此位置的商;
（3）求出此时的余数x；
（4）接着往高位的下一位走，重复（2）（3）步骤，直到最后一位；
4.输出商和余数

1.2 例题 #

一个大整数除以一个整数（低精度数）
输入:
一个大于0的大整数a,长度不超过100位，求出除以一个整数b。
输出:l
一行，商和余数，中间用空格隔开。
样例输入:
2132104848488485 13
样例输出:
164008065268345 0
参考程序

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

const int MAX = 101;

int main(int argc, const char * argv[]) {
    int b, i, la, lc, x;
    string str;
    int a[MAX], c[MAX];
    
    while(cin >> str >> b) { // 1.输入大整数和整数b
        memset(a, 0, sizeof(a)); // 清零
        memset(c, 0, sizeof(c));
        // 获取大整数的长度
        la = (int)str.size();
        for(i = 0; i < la; i++)
            a[la-i-1] = str[i] - '0'; // 2.将数字串从低位往高位存储到数组a中
        // 3.计算c=a/b
        x = 0; // 余数初始为0
        for(i = la-1; i >= 0; i--) {
            c[i] = (x * 10 + a[i]) / b; // 将高位得到的余数乘以10，再加上新位置的数，再除以b
            x = (x * 10 + a[i]) % b; // 得出余数
        }
        lc = la;
        while(lc > 1 && c[lc-1] == 0) // 4.删去多余的0
            lc--;
        // 5.从高位往低位输出商
        for(i = 0; i < lc; i++)
            cout << c[lc-i-1];
        // 空格输出余数
        cout << " " << x << endl;
    }
    return 0;
}

2. 高精度除以高精度例题精讲 #

2.1 计算过程 #

基本思想是反复做减法，看看从被除数里最多
能减去多少个除数，商就是多少。
• 一个一个减显然太慢，如何减得更快一些呢？
• 以7546除以23为例来看一下：开始商为0
– 先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300
– 然后用646减去230，发现够减2次，余下186。于是商的值增加20，变为320
– 最后用186减去23，够减8次，因此最终商就是328
• 本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。

2.2 例题 #

两个大整数相除
输入:
两行，分别是被除数和除数。
输出:l
两行，商和余数。
样例输入:
2132104848488485
13
样例输出:
164008065268345
0
参考程序

#include < iostream >
#include < string >
using namespace std;
int Substract(int nMaxLen, int *an1, int * an2)
//大整数an1减去an2。两者最多nMaxLen位，an1必须不小于an2, 差放在an1里
//返回差的最高非0位的位置
{
    int i, nStartPos = 0;
    for ( i = 0; i < nMaxLen ; i ++ ) {
        an1[i] -= an2[i]; //逐位相减
        if ( an1[i] < 0 ) { //看是否要借位
            an1[i] += 10;
            an1[i+1] --; //借位
        }
    if ( an1[i] )
        nStartPos = i; //记录最高位的位置
    }
return nStartPos; 
}

int Length(int nMaxLen, int *an)
// 求大整数的位数，0算0位 
{
    int i;
    for ( i = nMaxLen - 1; an[i] == 0 && i >= 0; i-- ); 
    if ( i >= 0 ) return i + 1;
    return 0;
}

void ShiftLeft(int nMaxLen, int *an1, int *an2, int n)
// 将大整数an1左移n位，即乘以10的n次方，结果放到an2里
 {
    int i;
    memcpy(an2, an1, nMaxLen * sizeof(int));
    if ( n <= 0 ) return;
    for ( i = nMaxLen -1; i >= 0; i -- ) { // 请写出循环体代码
        if(i - n >= 0)
            an2[i] = an1[i - n];
    }
    for(int j = 0; j < n; ++j){
        an2[j] = 0;
    } 

}

int * Max(int nMaxLen, int *an1, int *an2)
// 求大整数an1和an2里面大的那个;若an1==an2，返回an1 // 如果都是0，则返回NULL
{
    bool bBothZero = true;
    int i;
    for ( i = nMaxLen -1; i >= 0 ; i -- ) {
        if ( an1[i] > an2[i] ) return an1;
        else if ( an1[i] < an2[i] ) return an2;
        else if ( an1[i] ) bBothZero = false;
    }
    if ( bBothZero)
        return NULL; 
    else
    return an1; 
}

#define MAX_LEN 110
int an1[MAX_LEN]; // 存放被除数, an1[0]对应于个位 
int an2[MAX_LEN]; // 存放除数
int tmpAn2[MAX_LEN];
int anResult[MAX_LEN];//存放商
string szLine1;//存放被除数的字符串
string szLine2;//存放除数的字符串

int main() {
    int n = 1; 
    while(n--) { 
        cin >> szLine1;
        cin >> szLine2;
        int i, j; 
        //库函数memset将地址an1开始的sizeof(an1)字节内容置成0 
        memset(an1, 0, sizeof(an1));
        memset(an2, 0, sizeof(an2)); 
        //下面将szLine1中存储的字符串形式的整数转换到an1中去， 
        int nLen1 = szLine1.size();
        for (j = 0, i = nLen1 - 1; i >= 0; i--)
            an1[j++] = szLine1[i] - '0';
        int nLen2 = szLine2.size();
        for ( j = 0, i = nLen2 - 1; i >= 0; i--)
            an2[j++] = szLine2[i] - '0';
        int nHighestPos = 0;
        memset(anResult, 0, sizeof(anResult));
        int nShiftLen = Length(MAX_LEN, an1) - Length(MAX_LEN, an2); 
        // 只要an1大于an2，就不停相减
        while( Max(MAX_LEN, an1, an2) == an1 ) {
            // 算出an2的10的nShiftLen次方倍 
            ShiftLeft(MAX_LEN, an2, tmpAn2, nShiftLen);
            // 重复减去an2的10的nShiftLen次方倍，看能减几次 
            while( Max(MAX_LEN, an1, tmpAn2) == an1) {
                Substract(MAX_LEN, an1, tmpAn2);
                anResult[nShiftLen] ++; // 记录商对应位 
            }
            // 记录结果最高位的位置
            if( nHighestPos == 0 && anResult[nShiftLen])
                nHighestPos = nShiftLen; 
            nShiftLen--;
        }
    for ( i = nHighestPos; i >= 0; i-- ) 
        cout << anResult[i];
    cout << endl;
    int k = MAX_LEN - 1;
    //去除余数的前导0
    while(k >=0 && an1[k] == 0) --k;
    //整除，余数为0
    if(k == -1) 
        cout << 0;
    else 
        for(k; k >= 0; --k) cout << an1[k];
    cout << endl;
    }
    return 0;
}
What are your Feelings