原理
遍历被除数
每次判断缓存rem是否大于除数s1
大于rem减去一次除数s1, 答案ans加一,再次判断
小于直接跳过,等于直接让rem为空,答案ans加一
退出循环后rem就是余数,处理一下ans前导0就可以得到商了
模拟了竖式除法,细节都在代码里都在代码里
代码演示1:粗糙版
#include <stdio.h>
#include <string.h>
char s1[1005], s2[1005]; // s1 / 22 = ans + rem;
int n1[1005], n2[1005], ans[1005], rem[1005]; //rem是余数(缓存) ,ans为商
//大数减法
void big_sub(int *a, const int *b) { //a >= b; a - b;
for (int i = 1; i <= a[0]; i++) {
a[i] -= b[i];
if (a[i] < 0) {
--a[i + 1]; //借一
a[i] += 10;
}
}
while (a[a[0]] == 0) --a[0];
return ;
}
//判断大数a与b大数谁大
int check(int *a, int *b) { //a大返回1,b大返回-1,相等返回0;
if (a[0] == b[0]) { //长度相等
for (int i = a[0]; i > 0; i--) {
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return -1;
}
return 0;
} else if (a[0] > b[0]) return 1;
return -1;
}
int main() {
// s1 / s2
scanf("%s", s2);
scanf("%s", s1);
n1[0] = strlen(s1), n2[0] = strlen(s2);
for (int i = 0, j = 1; j && s1[i]; i++, j++) { //正序存储
n1[j] = s1[i] - '0';
}
for (int i = 0, j = n2[0]; j && s2[i]; i++, j--) { //倒序存储
n2[j] = s2[i] - '0';
}
// n1 / n2
for (int i = 1; i <= n1[0]; i++) {
//缓存后移
for (int j = rem[0]; j > 0; j--) {
rem[j + 1] = rem[j];
}
++rem[0], rem[1] = n1[i]; //头插法,保证高位在后面,低位在前
//输出rem看看
// for (int k = 1; k <= rem[0]; k++) {
// printf("%d", rem[k]);
// }
// printf("\n");
if (check(rem, n2) == -1) continue;
while (check(rem, n2) > 0) { //rem > n2
ans[i]++; //ans全局初始化为0了
big_sub(rem, n2);
//for (int w = rem[0]; w; w--) printf("%d", rem[w]);
// printf("\n");
}
if (check(rem, n2) == 0) ++ans[i], rem[0] = 0;
}
//输出商
ans[0] = n1[0];
int t = 1;
while (ans[t] == 0 && t <= ans[0]) t++; //去除商的前导0
if (t > ans[0]) printf("0"); //特判,商为0时;
while (t <= ans[0]) printf("%d", ans[t++]);
printf("\n");
//输出余数
if (rem[0] == 0) printf("0");
for (int i = rem[0]; i; i--) printf("%d", rem[i]);
printf("\n");
return 0;
}
代码演示二:精简版
#include <stdio.h>
#include <string.h>
char s1[1005], s2[1005]; // s1 / 22 = ans + rem;
int n2[1005], ans[1005], rem[1005]; //rem是余数(缓存) ,ans为商
//大数减法
void big_sub(int *a, const int *b) { //a >= b; a - b;
for (int i = 1; i <= a[0]; i++) {
a[i] -= b[i];
if (a[i] < 0) {
--a[i + 1]; //借一
a[i] += 10;
}
}
while (a[a[0]] == 0) --a[0];
return ;
}
//判断大数a与b大数谁大
int check(int *a, int *b) { //a大返回1,b大返回-1,相等返回0;
if (a[0] == b[0]) { //长度相等
for (int i = a[0]; i > 0; i--) {
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return -1;
}
return 0;
} else if (a[0] > b[0]) return 1;
return -1;
}
int main() {
// s1 / s2
scanf("%s", s2);
scanf("%s", s1);
n2[0] = strlen(s2);
ans[0] = strlen(s1);
for (int i = 0, j = n2[0]; j && s2[i]; i++, j--) { //倒序存储
n2[j] = s2[i] - '0';
}
for (int i = 0; s1[i]; i++) { //遍历被除数
//缓存后移
for (int j = rem[0]; j > 0; j--) {
rem[j + 1] = rem[j];
}
++rem[0], rem[1] = s1[i] - '0'; //头插法,保证高位在后面,低位在前
//输出rem看看
// for (int k = 1; k <= rem[0]; k++) {
// printf("%d", rem[k]);
// }
// printf("\n");
if (check(rem, n2) == -1) continue;
while (check(rem, n2) > 0) { //rem > n2
ans[1 + i]++; //ans全局初始化为0了
big_sub(rem, n2);
//for (int w = rem[0]; w; w--) printf("%d", rem[w]);
// printf("\n");
}
if (check(rem, n2) == 0) ++ans[1 + i], rem[0] = 0; //直接让rem为空
}
//输出商
int t = 1;
while (ans[t] == 0 && t <= ans[0]) t++; //去除商的前导0
if (t > ans[0]) printf("0"); //特判,商为0时;
while (t <= ans[0]) printf("%d", ans[t++]);
printf("\n");
//输出余数
if (rem[0] == 0) printf("0");
for (int i = rem[0]; i; i--) printf("%d", rem[i]);
printf("\n");
return 0;
}