分治法求解十进制的两个整数相乘的解C语言
时间: 2024-05-09 12:19:35 浏览: 126
分治法求两个大整数相乘
以下是分治法求解十进制的两个整数相乘的解的C语言代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LEN 1000
void multiply(char x[], char y[], char res[]) {
int len1 = strlen(x);
int len2 = strlen(y);
if (len1 == 0 || len2 == 0) {
res[0] = '0';
res[1] = '\0';
return;
}
if (len1 == 1 && len2 == 1) {
int a = x[0] - '0';
int b = y[0] - '0';
int c = a * b;
if (c < 10) {
res[0] = c + '0';
res[1] = '\0';
} else {
res[0] = c / 10 + '0';
res[1] = c % 10 + '0';
res[2] = '\0';
}
return;
}
int max_len = len1 > len2 ? len1 : len2;
if (max_len % 2 != 0) {
max_len++;
}
char a[MAX_LEN], b[MAX_LEN], c[MAX_LEN], d[MAX_LEN];
char ac[MAX_LEN * 2 + 1], bd[MAX_LEN * 2 + 1], ad_bc[MAX_LEN * 2 + 1];
memset(a, '0', sizeof(a));
memset(b, '0', sizeof(b));
memset(c, '0', sizeof(c));
memset(d, '0', sizeof(d));
memset(ac, '0', sizeof(ac));
memset(bd, '0', sizeof(bd));
memset(ad_bc, '0', sizeof(ad_bc));
int i, j;
for (i = 0; i < len1 / 2; i++) {
a[i] = x[i];
}
for (j = 0; j < len2 / 2; j++) {
c[j] = y[j];
}
multiply(a, c, ac);
for (i = len1 / 2; i < len1; i++) {
b[i - len1 / 2] = x[i];
}
for (j = len2 / 2; j < len2; j++) {
d[j - len2 / 2] = y[j];
}
multiply(b, d, bd);
char tmp1[MAX_LEN], tmp2[MAX_LEN];
memset(tmp1, '0', sizeof(tmp1));
memset(tmp2, '0', sizeof(tmp2));
for (i = 0; i < len1 / 2; i++) {
tmp1[i] = x[i];
}
for (j = len2 / 2; j < len2; j++) {
tmp2[j - len2 / 2] = y[j];
}
multiply(tmp1, tmp2, ad_bc);
for (i = 0; i < max_len * 2; i++) {
res[i] = '0';
}
res[max_len * 2] = '\0';
for (i = 0; i < strlen(ac); i++) {
res[i] = ac[i];
}
for (i = strlen(ac); i < max_len * 2; i++) {
res[i] = '0';
}
for (i = 0; i < strlen(bd); i++) {
res[i + max_len * 2 - strlen(bd)] += bd[i] - '0';
}
for (i = 0; i < strlen(ad_bc); i++) {
res[i + max_len] += ad_bc[i] - '0';
}
for (i = max_len * 2 - 1; i > 0; i--) {
if (res[i] > '9') {
res[i - 1] += (res[i] - '0') / 10;
res[i] = (res[i] - '0') % 10 + '0';
}
}
while (res[0] == '0' && strlen(res) > 1) {
for (i = 0; i < strlen(res) - 1; i++) {
res[i] = res[i + 1];
}
res[strlen(res) - 1] = '\0';
}
}
int main() {
char x[MAX_LEN], y[MAX_LEN], res[MAX_LEN * 2 + 1];
printf("请输入两个整数:\n");
scanf("%s%s", x, y);
multiply(x, y, res);
printf("结果为:%s\n", res);
return 0;
}
```
其中,multiply函数是分治法求解十进制两个整数相乘的核心部分,采用递归的方式进行计算。主函数中输入两个整数,并调用multiply函数求解它们的乘积。
阅读全文