大整数的乘法实验报告.doc

算法设计与分析实验报告姓名:XXX班级:XXX学号:XXX一、实验名称:大整数的乘法时间:2012年3月7日,星期三,第四节地点:12#311二、实验目的及要求实现大整数相乘,需要处理很大的整数,它无法在计算机硬件能直接表示的整数范围内进行处理。若用浮点数来表示它,则只能近似的表示它的大小,计算结果中的有效数字也受到限制。如要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字,就必须用软件的方法来实现大整数的算术运算。三、实验环境Vc++。四、实验内容从键盘上输入两个大整数,实现两个大整数相乘,并输出结果。例如:在键盘上输入两个数a,b。 a=9876543210; b=369852147;五、算法描述及实验步骤定义三个数组a[100],b[100],c[199]。用数组a来存放大整数a,a[0]=9,a[1]=8,a[2]=7,a[3]=6,a[4]=5,a[5]=4,a[6]=3,a[7]=2,a[8]=1,a[9]=0;用数组b来存放大整数b,b[0]=3,b[1]=6,b[2]=9,b[3]=8,b[4]=5,b[5]=2,b[6]=1b[7]=4,b[8]=7。用数组c来存放数组a和b每一位的乘积,c[0]=a[0]*b[0];c[1]=a[1]*b[0]+a[0]*b[1];c[2]=a[2]*b[0]+a[1]*b[1]+a[0]*b[2];…………c[17]=a[9]*b[8];六、调试过程及实验结果voidmake(inta[],intaa,intb[],intbb,intc[]){inti,j;for(i=0;i<aa;i++){if(a[i]==0)continue;for(j=0;j<bb;j++)c[i+j]+=a[i]*b[j];}for(i=0;i<aa+bb-1;i++){c[i-1]+=c[i]/10;c[i]=c[i]%10;}printf("\nc=");for(i=0;i<aa+bb-1;i++)printf("%d",c[i]);} 程序运行结果:更改程序后:voidmake(inta[],intaa,intb[],intbb,intc[]){ inti,j; for(i=0;i<aa;i++){ if(a[i]==0)continue; for(j=0;j<bb;j++) c[i+j]+=a[i]*b[j]; } for(i=aa+bb-2;i>0;i--){ c[i-1]+=c[i]/10; c[i]=c[i]%10; } printf("\nc="); for(i=0;i<aa+bb-1;i++) printf("%d",c[i]);}运行结果:七、总结本程序的的时间复杂度太大O(aa*bb),但是解决了大整数相乘硬件无法完成的问题。上机经验和体会:因注意循环体部分和循环条件,此处时容易出错的地方。八、附录(源程序清单)#include<>#defineA100#defineB100intgetnumber(chara[],intb[]){ inti=0; while(a[i]!='\0'){ b[i]=a[i]-48; i++; } returni;}voidmake(inta[],