大数的乘法【数组】

大数的乘法【数组】

时间: 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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注