编写程序实现两个长整数(大于等于0,每个最长80位数字)的乘法运算。从键盘分行读入两个超长整数,要考虑输入高位可能为0的情况(如00083),每行的最后都有回车换行。输出只有一行,是两个长整数的乘法运算结果,从高到低依次输出各位数字,各位数字紧密输出。除非结果为0,否则最高位不能为0。
方法:模拟法
思路
想一下我们人是怎么计算乘法的: 但是我们在做乘法的时候不考虑进位该怎么计算? 因此思路为:用数字b的每一位,分别乘上数字a的每一位,因此代码的大体框架应该是这样: 1
2
3
4
5
6
7for(int i=0; i<b的长度; i++)
{
for(int j=0; j<a的长度; j++)
{
什么东西 = b[i]*a[j];
}
}
所以我们先把每行的数字当成一个字符串输入,然后用一个数组存放数字的每一位。 1
2
3
4
5
6
7
8// 存放字符串
char tmp[1000000];
// A用来存放数字a的每一位元素,B用来存放b的每一位元素,C用来存放结果
int C[1000000], A[1000000], B[1000000];
// 数组开多大空间随意,但一定要保证够用
// 先读取数字a的字符串
scanf("%s", tmp);1
2
3
4
5
6
7
8
9// 首先获取字符串tmp的长度,也就是a的位数
int n = strlen(tmp);
int a = 0, b = 0;
for(int i = n-1; i>=0; i--)
{
// 对于字符串来说,每一个数字其存放方式是字符,例如'1'这样,而 '1'!=1 ,我们需要减去'0'才能转换为数字
A[a] = tmp[i] - '0';
a++;
}1
while (n--) A[a++] = tmp[n]-'0';
同样的操作,我们将第二个数字读入: 1
2
3
4
5
6
7
8scanf("%s", tmp);
n = strlen(tmp);
// while (n--) B[b++] = tmp[n] - '0';
for(int i = n-1; i>=0; i--)
{
B[b] = tmp[i] - '0';
b++;
}
我们先写出来一个大框: 1
2
3
4
5
6
7for (int i = 0; i < a; i++)
{
for (int j = 0; j < b; j++)
{
// A[i]*B[j];
}
}1
2
3
4
5
6
7for (int i = 0; i < a; i++)
{
for (int j = 0; j < b; j++)
{
C[i + j] += A[i] * B[j];
}
}1
2
3
4
5
6
7for (int i = 0; i < a+b; i++)
{
// 18/10 == 1, 27/10 == 2 ...
C[i + 1] += C[i] / 10;
// 18%10 == 8, 27%10 == 7 ...
C[i] %= 10;
}1
2
3
4
5
6int i;
for(i=a+b; i>=0; i--)
{
// 找到就跳出循环
if (C[i] != 0)break;
}1
2
3
4
5if (i==-1)printf("0");
else for(; i>=0; i--)
{
printf("%d", C[i]);
}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
char tmp[1000000];
int C[1000000], A[1000000], B[1000000];
int main(void)
{
scanf("%s", tmp);
int n = strlen(tmp);
int a = 0, b = 0;
for(int i = n-1; i>=0; i--)
{
A[a] = tmp[i] - '0';
a++;
}
scanf("%s", tmp);
n = strlen(tmp);
for(int i = n-1; i>=0; i--)
{
B[b] = tmp[i] - '0';
b++;
}
for (int i = 0; i < a; i++)
{
for (int j = 0; j < b; j++)
{
C[i + j] += A[i] * B[j];
}
}
for (int i = 0; i < a+b; i++)
{
C[i + 1] += C[i] / 10;
C[i] %= 10;
}
int i;
for(i=a+b; i>=0; i--)
{
if (C[i] != 0)break;
}
if (i==-1)printf("0");
else for(; i>=0; i--)
{
printf("%d", C[i]);
}
return 0;
}