【NEUCSECG】长整数乘法

VLSMB2024-07-122024-07-12

编写程序实现两个长整数（大于等于0，每个最长80位数字）的乘法运算。从键盘分行读入两个超长整数，要考虑输入高位可能为0的情况（如00083），每行的最后都有回车换行。输出只有一行，是两个长整数的乘法运算结果，从高到低依次输出各位数字，各位数字紧密输出。除非结果为0，否则最高位不能为0。

方法：模拟法

思路

想一下我们人是怎么计算乘法的：
alt text
但是我们在做乘法的时候不考虑进位该怎么计算？

因此思路为：用数字b的每一位，分别乘上数字a的每一位，因此代码的大体框架应该是这样：

for(int i=0; i<b的长度; i++)
{
    for(int j=0; j<a的长度; j++)
    {
        什么东西 = b[i]*a[j];
    }
}

数字的输入

因为题目说数字最长有80位，而C语言中int的上限为2147483647，就算是开unsigned long long，最大才能存下18446744073709551615这个数字，因此显然不能用一个变量存放数字。

所以我们先把每行的数字当成一个字符串输入，然后用一个数组存放数字的每一位。

// 存放字符串
char tmp[1000000];
// A用来存放数字a的每一位元素，B用来存放b的每一位元素，C用来存放结果
int C[1000000], A[1000000], B[1000000];
// 数组开多大空间随意，但一定要保证够用

// 先读取数字a的字符串
scanf("%s", tmp);

然后我们要想，如何把字符串tmp中的数字a存放在int A里。对于字符串”123456”，我们发现数字a的个位是6，十位是5……是倒过来的。为了让A[0]=6，A[1]=5，A[2]=4，A[3]=3，A[4]=2，A[5]=1，我们需要这样操作：

// 首先获取字符串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';

循环结束后变量a就变成了第一个数字的长度。

同样的操作，我们将第二个数字读入：

scanf("%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++;
}

至此我们完成了数字的输入

为什么不需要特殊处理前导0？

例如，对于数字”0023”，我们的程序strlen(“0023”)返回4，即我们记录的数字长度为4。但是，经过我们的处理，数组中存放的元素为{3, 2, 0, 0}，即使我们把它当四位数去做乘法，高二位的0与另一个数字的每一位乘积都是0，并不会影响最终的答案。因此不需要特殊考虑字符串前导0的情况。

模拟乘法

假设我们的输入是”456”和”123”，那么现在的B == {3, 2, 1}，A == {6, 5, 4}
A的长度为a，B的长度为b。我们现在拿A的每一位去乘B的每一位，这个答案应该放在哪里呢？

我们先写出来一个大框：

for (int i = 0; i < a; i++)
{
	for (int j = 0; j < b; j++)
    {
        // A[i]*B[j];
    }
}

alt text
i取0时，A[0]和B的各位乘积分别为18，12，6（先不管进位），这三个数字应该落在C[0]，C[1]，C[2]上

i取1时，A[1]和B的各位乘积，这三个数字应该落在C[1]，C[2]，C[3]上；i取2时，A[2]和B的各位乘积，这三个数字应该落在C[2]，C[3]，C[4]上。因此，对于每一个A[i]和B[j]，他们的乘积A[i]*B[j]应该是C[i + j]的一部分
alt text

for (int i = 0; i < a; i++)
{
	for (int j = 0; j < b; j++)
	{
		C[i + j] += A[i] * B[j];
	}
}

经过这样的操作，C数组变成{18, 27, 28, 13, 4}。

处理最终结果

但是我们还没有处理完，我们需要得到的答案应该每一位不超过10，因此我们需要处理数组。
例如，对于个位数字18，我们应该保留8，并将十位+1，依次类推：

for (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;
}

因为C中的数字是由刚才的二重循环而来，而二重循环的i最大为a-1，j最大为b-1，因此C最大长度也就是(a-1)+(b-1)+1 == a+b-1，但是经过我们的处理，可能会产生进位，C的长度就变成了a+b

输出

在输入的时候我们不需要考虑前导0，但输出的时候就需要考虑了，我们从C的最大长度a+b开始，逆序找第一个数字不是0的位置：

int i;
for(i=a+b; i>=0; i--)
{
    // 找到就跳出循环
	if (C[i] != 0)break;
}

显然，如果没有找到的话，那么i==-1。这个时候我们要输出一个0，代表最终乘积结果为0。如果i不是-1的话，那么就从此处开始，倒序输出数组C的结果，就是最终的答案

if (i==-1)printf("0");
else for(; i>=0; i--)
{
	printf("%d", C[i]);
}

完整的代码

#include <stdio.h>
#include <string.h>
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;
}

【NEUCSECG】 长整数乘法