题目描述
高精除以高精，求它们的商和余数。
输入
输入两个低于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亿，但它并没有发生溢出。优化前的算法根本跑不出结果来。
关键点
| 优化前 | 优化后 |
|---|---|
| 利用循环，多次使用减法，容易超时。 | 从被除数的高位，以最少的次数使用减法，时间通常不超过0.3秒。 |
| 将结果放入整形变量，容易溢出。 | 将结果放入数组，不可能溢出。 |
测试数据
| 被除数 | 除数 | 商 | 余数 |
|---|---|---|---|
| 63 | 3 | 21 | 0 |
| 3 | 63 | 0 | 3 |
| 063 | 0003 | 21 | 0 |
| 123456789123456789123456789 | 123 | 1003713732711030805881762 | 63 |
| 123 | 123456789 | 0 | 123 |
| 1 | 1 | 1 | 0 |
| 0 | 123 | 0 | 0 |
| 00000 | 123 | 0 | 0 |
特别鸣谢
测试数据提供： 挖坑大师——妈妈
推广平台提供： 简书
测试平台提供： 信息学奥赛一本通网站
网友评论