算法分析和设计大整数乘法代码.doc

《算法分析和设计大整数乘法代码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#includeintmain(){chara[100],b[100],s[202];intn,i,j,g,t=0,k=1,temp;scanf("%d",&n);n--;scanf("%s%s",&a,&b);while(k<=2*n){s[k]=0;temp=0;for(i=0;i<=n;i++){for(j=0;j<=n;j++){if((i+j)==k-1)temp+=(a[n-i]-48)*(b[n-j]-48);}}g=(temp+t)%10;t=(temp+t)/10;s[k]=g;k++;}temp=0;for(i=0;i<=n;

2、i++){for(j=0;j<=n;j++)if((i+j)==k-1)temp+=(a[n-i]-48)*(b[n-j]-48);}temp+=t;printf("%d",temp);for(i=2*n;i>0;i--)printf("%d",s[i]);printf("");return0;}//两个100位以内的如果小了自己将数组改一下设X和Y是两个n位的整数，假定n是2的整数次幂。把每个整数分为两部分，每部分为n/2位，则X和Y可重写为X=x1*10n/2+x0和Y=y1*10n/2+y0，X和Y的乘积可以计算为X*Y=(x1*10n/2+x0)*(y

3、1*10n/2+y0)=X1*Y1*10n+((x1+x0)*(y1+y0)-x1*y1-x0*y0)*10n/2+x0*y0由此体现了分治递归的思想，将大整数化小，规模也变小。源代码如下:#include#includeintn,x,y,rt;//全局变量voidinput(){cout<<"两个乘数的位数是n,请输入n的值(n是2的整数次幂):";cin>>n;cout<>x;cout<<"y=";cin>>y;}intcalculate(in

4、ta,intb)//计算数值函数--循环体{inttemp1,temp2;longs;intx1,x0,y1,y0;if(n>1)//可以分治算法的条件{temp1=(int)pow(10,n/2);temp2=(int)pow(10,n);x1=a/temp1;//x值的前半部分x0=a-x1*temp1;//x值的后半部分y1=b/temp1;//y值的前半部分y0=b-y1*temp1;//y值的后半部分n=n/2;//经过一次分治后,数的位数减半s=calculate(x1,y1)*temp2+(calculate(x1+x0,y1+y0)-calcula

5、te(x1,y1)-calculate(x0,y0))*temp1+calculate(x0,y0);}elsereturna*b;returns;}voidprint()//输出函数{cout<<"乘数x="<>c;}while(c=='y'

6、

7、'c'=

8、='Y');}