主要内容 #
- 高精度除以单精度例题精讲
- 高精度除以高精度例题精讲
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;
}
