高精度除以高精度
作者:
AELee
,
2021-01-29 11:57:16
,
所有人可见
,
阅读 538
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[10010], b[10010], c[10010], tmp[10010];
int compare() { //比较a和tmp的大小
if (a[0] > tmp[0]) return 1;
if (a[0] < tmp[0]) return -1;
for (int i = a[0]; i > 0; i--) {
if (a[i] > tmp[i]) return 1;
if (a[i] < tmp[i]) return -1;
}
return 0;
}
int main() {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
string s, t;
cin >> s >> t;
a[0] = s.size(), b[0] = t.size(); //位数
for (int i = 1; i <= a[0]; i++) a[i] = s[a[0] - i] - '0';//倒置存储
for (int i = 1; i <= b[0]; i++) b[i] = t[b[0] - i] - '0';
//除法
c[0] = a[0] - b[0] + 1; //位数
int i;
for (i = c[0]; i > 0; i--) {
memset(tmp, 0, sizeof(tmp));
for (int j = 1; j <= b[0]; j++) {
tmp[j + i - 1] = b[j]; //将除数复制到减数i开始的位置上
}
tmp[0] = b[0] + i - 1; //减数的位数
while (compare() >= 0) { //a>=tmp
c[i]++; //商+1
for (int i = 1; i <= a[0]; i++) { //被除数(a)减去减数(tmp)
if (a[i] < tmp[i]) { a[i + 1]--; a[i] += 10; }
a[i] -= tmp[i];
}
while (a[0] > 0 && a[a[0]] == 0) a[0]--; //更新a的位数
}
}
while (c[0] > 0 && c[c[0]] == 0) c[0]--; //更新c的位数
for (int i = c[0]; i > 0; i--) cout << c[i]; //商
cout << endl;
for (int i = a[0]; i > 0; i--) cout << a[i]; //余数
cout << endl;
}
%%%
zan
点赞