分治法大整数乘法C 实现

1、精彩文档算法设计与分析基础实验报告实验名称分治法求大整数乘法学院专业班级计算机科学与技术09(2)班学号3109005933姓名黄进杰指导教师顾国生2012年12月03日一、实验目的通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。二、实验环境C-Free三、实验内容问题的描述通过分治法求两个大整数的乘法算法设计思想将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题解合并得到原问题的解。程序设计#include#include#include#includeusingnamespacestd

2、;/string类型转换成nt类型intstring_to_num(stringk)/str字符串变整数型例如tr二1234转换为整数的234.intback;stringstreaminstr(k);instrback;returnback;/整形数转换为tring类型stringnum_to_string(intintValue)stringresult;stringstreamstream;streamresult;/从stream中抽取前面放入的nt值returnresult;/在字符串str前添加s个零stringstringBeforeZero(stringstr,ints)for

3、(inti=0;istr2.size()str2=stringBeforeZero(str2,str1.size()-str2.size();elseif(str1.size()=0;i-)intc二(str1i-0)+(str2i-0)+利用gSCII码对字符进行运算这里加上flag代表的是当前一位有进位时加无进位时力0flag二c/10;/大于10时，flag置为1,否则为0c%=10；/大于10时取模，否则为其本身result.insert(0,num_to_string(c)在/)sult字符串最前端插入新生成的单个字符if(0!二flag)/最/后一为(最高位)判断，如果有进位则再添

4、一位result.insert(0,num_to_string(flag);returnresult;/*两个大整数字符串相减超，出计算机表示范围的数也能实现相(在减这里比较特殊第，一个参数一定大于第二个参数,因为：a1*b0+a0*b1=(a1+a0)*(b1+b0)-(a1*b1+a0*b0)所以(a1+a0)*(b1+b0)(a1*b1+a0*b0)这个函数的两个参数，一个代表的其实就是1+a0)*(b1+bQ)第二个代表的其实就是1*b1+a0*b0)所以本函数里不用考虑最终得到结果为负数的情况，至于计算有关大整数负数相乘的问题可以通过其他途径判断*/stringstringSubtr

5、actstring(stringstr1,stringstr2)/对传进来的两个数进行修剪，如果前面几位0则有先去掉，便于统一处理while(0二二str10&str1.size()1)str1=str1.substr(1,str1.size()T);while(0=str20&str2.size()1)str2=str2.substr(1,str2.size()-1);/使两个字符串长度相等if(str1.size()str2.size()str2=stringBeforeZero(str2,str1.size()-str2.size();stringresult;for(inti=str1

6、.size()-1;i=0;i-)intc二(str1i-0)-(str2i-0利用ASCII码进行各位减法运算if(c0)/当/不够减时向前一位借位，前一位也不够位时再向前一位借位，依次如下c+二10;intprePos二i-1;charpreChar二str1prePos;while(0二二preChar)str1prePos二9;prePos-二1;preChar二str1prePos;str1prePos-=1;result.insert(0,num_to_string(c)在/esult字符串最前端插入新生成的单个字符returnresult;/在字符串str后跟随s个零string

7、stringFollowZero(stringstr,ints)for(inti=0;i1)x=x.substr(1,x.size()-1);/对传进来的第二个数进行修剪，如果前面几0位则有先去掉，便于统一处理while(0=y0&y.size()1)y=y.substr(1,y.size()-1);/*这里的f变量代表在两个数据字符串长度不想等或者不的指数倍的情况下，所要统一的长度,这样做是为了让数据长度2为勺n次方的情况下便于利用分治法处理*/intf=4;/*当两字符串中有任意一个字符串长度大于都要通过与上面定义的直进行比较，使其达到数据长度为2的n次方，实现方式是在前面补0，这样可以保

8、证数据直大小不变*/if(x.size()2|y.size()2)if(x.size()=y.size()|/一个数长度大于等于第二个数长度的情况while(x.size()f)判/断f值f*=2;if(x.size()!=f)x=stringBeforeZero(x,f-x.size();y=stringBeforeZero(y,f-y.size();else/第二个数长度大于第一个数长度的情况while(y.size()f)判/断f值f*=2;if(y.size()!=f)x=stringBeforeZero(x,f-x.size();y=stringBeforeZero(y,f-y.si

9、ze();if(1=x.size()数/据长度为1时,在前面补一个0(这里之所以会出现长度为1的数据是因为前面对数据修剪过)x=stringBeforeZero(x,1);if(1=y.size()数/据长度为1时,在前面补一个0(这里之所以会出现长度为1的数据是因为前面对数据修剪过)y=stringBeforeZero(y,1);if(x.size()y.size()最/后一次对数据校正，确保两个数据长度统一y=stringBeforeZero(y,x.size()-y.size();if(x.size()1)a1=x.substr(0,s/2);a0=x.substr(s/2,s-1);b

10、1=y.substr(0,s/2);b0=y.substr(s/2,s-1);stringresult;if(s=2)/长/度为2时代表着递归的结束条件intna=string_to_num(a1);intnb=string_to_num(a0);intnc=string_to_num(b1);intnd=string_to_num(b0);result=num_to_string(na*10+nb)*(nc*10+nd);else/长/度不为2时利用分治法进行递归运算小提示:c二a*b二c2*(10l)+c1*(10八(n/2)+cO;a二alaO二a1*(10八(n/2)+aO;b二blb

11、O二b1*(10八(n/2)+bO；c2二a1*b1;c0二a0*b0;c1二(a1+a0)*(b1+b0)-(c2+c0);stringc2=IntMult(a1,b1);/(a1*b1)stringc0=IntMult(a0,b0);/(a0*b0)stringc1_1=stringAddstring(a1,a0);/(a1+a0)stringc1_2=stringAddstring(b1,b0);/(b1+b0)stringc1_3=IntMult(c1_1,c1_2);/(a1+a0)*(b1+b0)stringc1_4=stringAddstring(c2,c0);/(c2+c0)s

12、tringc1=stringSubtractstring(c1_3,c1_4);/(a1+a0)*(b1+b0)-(c2+c0)strings仁stringFollowZero(c1,s/2)；/c1*(10入(n/2)strings2=stringFollowZero(c2,s);/c2*(10八n)result二stringAddstring(stringAddstring(s2,s1),c0);/c2*(10八n)+c1*(10入(n/2)+c0returnresult;intmain()intf=1;while(1=f)stringA,B,C,D;stringnum1,num2;str

13、ingr;system(title3109005933计09科02班黄进杰分治法大整数乘法);system(color0a);cout大整数乘法运算分治法实现endl;coutnum1;inti=0;/判断第一个输入的数据是否合,当法字符串中包含非数字字符时提示用户重新输入for(i=0;inum1.size();i+)if(num1i9)cout您输入的数据不合，请输入有效的整tnum1;i=-1;coutnum2;/判断第二个输入的数据是否合,当字符串中包含非数字字符时提示用户重新输入for(i=0;inum2.size();i+)if(num2i9)cout您输入的数据不合7请输入有效的整tnum2;i=-1;r=IntMult(num1,num2)