大数的乘法【数组】

大数的乘法【数组】

时间： 1ms        内存：128M

描述：

大数是指计算的数值非常大或者对运算的精度要求非常高，用已知的数据类型无法精确表示的数值。例如：我们要计算如下两个数的乘积时，用我们已知的数据类型是无法精确表示其结果的：

a1 = 11111111111111111111111111111111111

b1 = 11111111111111111111111111111111111111

求：a1 * b1;

输入：

输入两行：每行一个数字，每行的数字不超过100位；

输出：

输出一行：为这两个大数的乘积

示例输入：

1111111111111111111
111111111111111

示例输出：

123456790123456666654320987654321

提示：

参考答案（内存最优[752]）：

#include<stdio.h>
#include<string.h>
#define LEN 300
int Input(char n[])
{
	char s[LEN];
	int i,l;
	for(i=0;i<LEN;i++)
		n[i]=0;
	if(scanf("%s",s)<1)
		return -1;
	l=strlen(s);
	for(i=0;i<l;i++)
		n[i]=s[l-i-1]-'0';
	return 0;
}
void Print(char n[])
{
	int i;
	for(i=LEN-1;i>0;i--)
		if(n[i]!=0) 
			break;
		for(;i>=0;i--)
			printf("%d",n[i]);
		printf("\n");
}
void Mul(char a[],char b[],char c[])
{
	int i,j;
	for(i=0;i<LEN*2;i++)
		c[i]=0;
	for(i=0;i<LEN;i++)
	{
		for(j=0;j<LEN;j++)
		{
			c[i+j]+=a[j]*b[i];
			if(c[i+j]>=10)
			{
				c[i+j+1]+=c[i+j]/10;
				c[i+j]=c[i+j]%10;
			}
		}
	}
}
int main()
{
	char a[LEN],b[LEN],c[LEN*2];
	Input(a);
	Input(b);
	Mul(a,b,c);
	Print(c);
	return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<string.h>
#define LEN 300
int Input(char n[])
{
	char s[LEN];
	int i,l;
	for(i=0;i<LEN;i++)
		n[i]=0;
	if(scanf("%s",s)<1)
		return -1;
	l=strlen(s);
	for(i=0;i<l;i++)
		n[i]=s[l-i-1]-'0';
	return 0;
}
void Print(char n[])
{
	int i;
	for(i=LEN-1;i>0;i--)
		if(n[i]!=0) 
			break;
		for(;i>=0;i--)
			printf("%d",n[i]);
		printf("\n");
}
void Mul(char a[],char b[],char c[])
{
	int i,j;
	for(i=0;i<LEN*2;i++)
		c[i]=0;
	for(i=0;i<LEN;i++)
	{
		for(j=0;j<LEN;j++)
		{
			c[i+j]+=a[j]*b[i];
			if(c[i+j]>=10)
			{
				c[i+j+1]+=c[i+j]/10;
				c[i+j]=c[i+j]%10;
			}
		}
	}
}
int main()
{
	char a[LEN],b[LEN],c[LEN*2];
	Input(a);
	Input(b);
	Mul(a,b,c);
	Print(c);
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。