用分治法求大整数乘法的算法

用分治法求大整数乘法的算法

#include
#include
#include
int main()
{
int a[500]={0},b[500]={0},c[2000]={0},i,j,n,m,k;
char f[500]=" ",o[500]=" ";
printf("输入a:");
gets(f); //字符串得到数字后，转换给数组
printf("输入b:");
gets(o);
if(strlen(f)>strlen(o))
{
n=strlen(f);
int i,j=0;
for(i=n-1;i>=0;i--)
{
a[j++]=f[i]-'0';
}
j=0;
m=strlen(o);
for(i=m-1;i>=0;i--)
{
b[j++]=o[i]-'0';
}
}
else
{
n=strlen(o);
int i,j=0;
for(i=n-1;i>=0;i--)
{
a[j++]=o[i]-'0';
}
j=0;
m=strlen(f);
for(i=m-1;i>=0;i--)
{
b[j++]=f[i]-'0';
}
}
for(i=0;i for(j=0;j {
c[i+j]+=a[i]*b[j];
}
for(i=0;i<=n;i++)
{
c[i+1]+=c[i]/10;
c[i]=c[i]%10;
}
k=n*m;
for(i=k;i>=0;i--)
{
if(i==k && c[i]==0)
{
k--;
continue;
}
else break;
}
for(i=k;i>=0;i--)
{
printf("%d",c[i]);
}
printf("\n");
system("pause");
return 0;
}

十进制是逢十进一
二进制是逢二进一

(注:如"2②"表示2的2次方,"2⑤"表示2的5次方)
1.二进制计数法的概念
人们在日常生活中和生产实践中,我们接触到越来越多的数字,创造了分组计数的制度.而我们的生活中,一般采用了"满十进一"的十进制计数法,我们现在已经熟悉并经常运用这一种计数法了.但也有采用其他计数法.如二进制,六进制,十六进制等计数法.现在就来讲一讲"二进制"和"十进制"的关系
2.十进制和二进制数的互化
(1)化十进制数为二进制数
<1>比较小的十进制数为二进制数可以用观察法.
例:化45为二进制数
因为2的0次方,1次方,2次方~~~10次方分别等于1,2,4,8,16,32,64,128,256,512,1024.
所以 45=32+8+4+1=2⑤+2③+2②+1=1*2⑤+0*2④+1*2②+0*2①+1*1=101101(二进制)
<2>一般化法
利用短除法(通常叫做"二除取余法")
(2)化二进制数为十进制数
这是比较方便的,只需把二进制是写成展开式;计算即得.
例1 化101101(二进制)为十进制数.
101101(二进制)=1*2⑤+0*2④+1*2③+1*2②+0*2①+1*1=32+0+8+4+0+1=45
例 2 化1011010101(二进制)为十进制数.
1011010101(二进制)=1*2⑨+1*2⑦+1*2⑥+1*2④+1*2②+1*1=512+128+64+16+4+1=725

由于我的电脑水平有限,很多东西大不出来,不能很明确地表现出来,我已经把我认为比较重要和简单的东西表示出来了,如果您还有疑问,我建议您到书店去买一本书:
<<小学数学奥林匹克读本(最新修订本)5年级>>(江苏教育出版社)
这本书挺好，我相信您看了会有帮助的.

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息