超长正整数的乘法

发表于 | 分类于 |

这是一道十分经典的题目了，早在考研的期间就想要写一次，但是一直苦于自己的拖延症，所以也就一直都没有能够将这个题目写出来。

题目

计算两个超长正整数的积

分析

这道题目其实是非常简单的，我们都用算式形式做过乘法，那么解这道题目也就是将这个过程模拟一下就可以了，这个过程中要注意处理进位。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <string.h>
#define ARRAY_LENGTH 200
#define RESULT_LENGTH 500
int input(int*, int*);
void mutiple(int* result, int* first, int* second, int length1, int length2);
void output(int* result);
int main() 
{
	int first[ARRAY_LENGTH] = {0}, second[ARRAY_LENGTH] = {0};
	int length1, length2, length;
	int result[RESULT_LENGTH] = {0};
	int i;
	input(first, &length1);
	input(second, &length2);
	mutiple(result, first, second, length1, length2);
	output(result);
	return 0;
}
int input(int* array, int* length)
{
	char temp[ARRAY_LENGTH] = {'0'};
	int i, j;
	gets(temp);
	*length = strlen(temp);
	for(i = 0; i < *length; i ++) 
	{
		array[i] = temp[i] - '0';
	}
	return 0;
}
void mutiple(int* result, int* first, int* second, int length1, int length2)
{
	int i, j, k;
	int temp, skip = 1;
	int m = 0, n = 0;  // m表示进位，n表示低位
	for(j = length2 - 1; j >= 0; j --) {
		k = RESULT_LENGTH - skip;
		for(i = length1 - 1; i >= 0; i --, k --) {
			temp = first[i] * second[j];
			n = m + temp % 10 + result[k];
			m = temp / 10 + n / 10;
			result[k] = n % 10;
		}
		result[k] = m;
		skip ++;
		m = 0;
	}
}
void output(int* result) 
{
	int i = 0;
	while(i < RESULT_LENGTH) {
		if(result[i] != 0)
			break;
		i ++;
	}
	for(; i < RESULT_LENGTH; i ++) {
		printf("%d", result[i]);
	}
	printf("\n");
}