用分治法怎么写大整数乘法的算法(用c语言写)
3个回答
展开全部
//大数的乘法,以前写的
#include<iostream>
#include<string>
using namespace std;
void toInt(char *s,int *in)
{
int i;
strrev(s);
for(i=0;i<strlen(s);i++)
{
in[i]=s[i]-'0';
}
}
void revint(int *in,int n)
{
int i,temp;
for(i=0;i<n/2;i++)
{
temp=in[i];
in[i]=in[n-i-1];
in[n-i-1]=temp;
}
}
int main()
{
char c1[200],c2[200];
int a1[200]={0}; //大数1
int a2[200]={0}; //大数2
int r2[300]={0}; //保存大结果
int f=0; //保存进位
int i,j;
cin>>c1>>c2;
if(strcmp(c1,"0")!=0&&strcmp(c2,"0")!=0)
{
int len1=strlen(c1);
int len2=strlen(c2);
int maxlen=len1+len2; //结果的最大位数
toInt(c1,a1);
toInt(c2,a2);
for(j=0;j<len2;j++)
{
int r1[200]={0}; //保存小结果
for(i=0;i<=len1;i++)
{
r1[i]=a2[j]*a1[i]+f;
if(r1[i]>9)
{
f=r1[i]/10;
r1[i]%=10;
}
else
{
f=0;
}
}
for(i=0;i<=len1;i++)
{
r2[j+i]+=r1[i];
if(r2[i+j]>9)
{
r2[i+j+1]+=r2[i+j]/10;
r2[i+j]%=10;
}
}
f=0;
}
revint(r2,maxlen);
if(r2[0]!=0)
cout<<r2[0];
for(i=1;i<maxlen;i++)
cout<<r2[i];
}
else
cout<<"0";
cout<<endl;
return 0;
}
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询