算法分析与设计----大整数乘法代码(1).doc_第1页
算法分析与设计----大整数乘法代码(1).doc_第2页
算法分析与设计----大整数乘法代码(1).doc_第3页
算法分析与设计----大整数乘法代码(1).doc_第4页
免费预览已结束，剩余1页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

#include int main() char a100,b100,s202; int n,i,j,g,t=0,k=1,temp; scanf(%d,&n); n-; scanf(%s%s,&a,&b); while(k=2*n) sk=0; temp=0; for(i=0;i=n;i+) for(j=0;j=n;j+) if(i+j)=k-1) temp+=(an-i-48)*(bn-j-48); g=(temp+t)%10; t=(temp+t)/10; sk=g; k+; temp=0; for(i=0;i=n;i+) for(j=0;j0;i-) printf(%d,si); printf(n); return 0;/两个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)*( y1*10n/2+y0) = X1*Y1*10n+( x1+x0)*( y1+y0)-x1*y1-x0*y0)* 10n/2+ x0*y0 由此体现了分治递归的思想，将大整数化小，规模也变小。源代码如下: #include #include int n,x,y,rt;/全局变量 void input() coutn; coutendl请输入两个乘数的值:endl; coutx; couty; int calculate(int a,int b) /计算数值函数-循环体 int temp1,temp2; long s; int x1,x0,y1,y0; if(n1) /可以分治算法的条件 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)-calculate(x1,y1)-calculate(x0,y0)*temp1+calculate(x0,y0); else return a*b; return s; void print()/输出函数 cout乘数x=xty=yendl; cout结果rt=rtendl; void main()/主函数 char c; do system(cls);/清屏函数 input(); r
人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论