分治法 大整数乘法 C++实现

算法设计与分析基础实验报告实验名称分治法求大整数乘法学院计算机学院专业班级计算机科学与技术09(2)班学号3109005933姓名黄进杰指导教师顾国生2012年12月03日1一、实验目的通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。二、实验环境C-Free三、实验内容（1）问题的描述通过分治法求两个大整数的乘法（2）算法设计思想将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题解合并得到原问题的解。（3）程序设计#includeiostream#includesstream#includestring#includestdlib.husingnamespacestd;//string类型转换成int类型intstring_to_num(stringk)//string字符串变整数型例如str=1234，转换为整数的1234.{intback;stringstreaminstr(k);instrback;returnback;}//整形数转换为string类型stringnum_to_string(intintValue){stringresult;stringstreamstream;streamintValue;//将int输入流streamresult;//从stream中抽取前面放入的int值returnresult;}//在字符串str前添加s个零stringstringBeforeZero(stringstr,ints){for(inti=0;is;i++){str.insert(0,0);}2returnstr;}//两个大整数字符串相加，超出计算机表示范围的数也能实现相加(本函数可以实现大整数加法运算)stringstringAddstring(stringstr1,stringstr2){//假定str1和str2是相等的长度，不相等时在前面自动补零，使两个字符串长度相等if(str1.size()str2.size()){str2=stringBeforeZero(str2,str1.size()-str2.size());}elseif(str1.size()str2.size()){str1=stringBeforeZero(str1,str2.size()-str1.size());}stringresult;intflag=0;//前一进位是否有标志,0代表无进位，1代表有进位for(inti=str1.size()-1;i=0;i--){intc=(str1[i]-'0')+(str2[i]-'0')+flag;//利用ASCII码对字符进行运算,这里加上flag代表的是:当前一位有进位时加1，无进位时加0flag=c/10;//c大于10时，flag置为1，否则为0c%=10;//c大于10时取模，否则为其本身result.insert(0,num_to_string(c));//在result字符串最前端插入新生成的单个字符}if(0!=flag)//最后一为(最高位)判断，如果有进位则再添一位{result.insert(0,num_to_string(flag));}returnresult;}/*两个大整数字符串相减，超出计算机表示范围的数也能实现相减(在这里比较特殊，第一个参数一定大于第二个参数,因为：a1*b0+a0*b1=(a1+a0)*(b1+b0)-(a1*b1+a0*b0)0,所以(a1+a0)*(b1+b0)(a1*b1+a0*b0)这个函数的两个参数，第一个代表的其实就是(a1+a0)*(b1+b0)，第二个代表的其实就是(a1*b1+a0*b0)所以本函数里不用考虑最终得到结果为负数的情况，至于计算有关大整数负数相乘的问题可以通过其他途径判断*/stringstringSubtractstring(stringstr1,stringstr2){//对传进来的两个数进行修剪，如果前面几位有0则先去掉，便于统一处理while('0'==str1[0]&&str1.size()1){str1=str1.substr(1,str1.size()-1);}while('0'==str2[0]&&str2.size()1)3{str2=str2.substr(1,str2.size()-1);}//使两个字符串长度相等if(str1.size()str2.size()){str2=stringBeforeZero(str2,str1.size()-str2.size());}stringresult;for(inti=str1.size()-1;i=0;i--){intc=(str1[i]-'0')-(str2[i]-'0');//利用ASCII码进行各位减法运算if(c0)//当不够减时向前一位借位，前一位也不够位时再向前一位借位，依次如下{c+=10;intprePos=i-1;charpreChar=str1[prePos];while('0'==preChar){str1[prePos]='9';prePos-=1;preChar=str1[prePos];}str1[prePos]-=1;}result.insert(0,num_to_string(c));//在result字符串最前端插入新生成的单个字符}returnresult;}//在字符串str后跟随s个零stringstringFollowZero(stringstr,ints){for(inti=0;is;i++){str.insert(str.size(),0);}returnstr;}//分治法大整数乘法实现函数stringIntMult(stringx,stringy)//递归函数{//对传进来的第一个数进行修剪，如果前面几位有0则先去掉，便于统一处理while('0'==x[0]&&x.size()1){4x=x.substr(1,x.size()-1);}//对传进来的第二个数进行修剪，如果前面几位有0则先去掉，便于统一处理while('0'==y[0]&&y.size()1){y=y.substr(1,y.size()-1);}/*这里的f变量代表在两个数据字符串长度不想等或者不是2的指数倍的情况下，所要统一的长度，这样做是为了让数据长度为2的n次方的情况下便于利用分治法处理*/intf=4;/*当两字符串中有任意一个字符串长度大于2时都要通过与上面定义的f值进行比较，使其达到数据长度为2的n次方，实现方式是在前面补0，这样可以保证数据值大小不变*/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.size());}}}if(1==x.size())//数据长度为1时,在前面补一个0(这里之所以会出现长度为1的数据是因为前面对数据修剪过)5{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()y.size())//最后一次对数据校正，确保两个数据长度统一{x=stringBeforeZero(x,y.size()-x.size());}ints=x.size();stringa1,a0,b1,b0;if(s1){a1=x.substr(0,s/2);a0=x.substr(s/2,s-1);b1=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*(10^n)+c1*(10^(n/2))+c0;a=a1a0=a1*(10^(n/2))+a0;b=b1b0=b1*(10^(n/2))+b0;c2=a1*b1;c0=a0*b0;c1=(a1+a0)*(b1+b0)-(c2+c0);****************************************************/stringc2=IntMult(a1,b1);//(a1*b1)6stringc0=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)stringc1=stringSubtractstring(c1_3,c1_4);//(a1+a0)*(b1+b0)-(c2+c0)strings1=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))+c0}returnresult;}intmain(){intf=1;while(1==f){stringA,B,C,D;stringnum1,num2;stringr;system(title310900593309计科02班黄进杰分治法大整数乘法);system(color0a);cout大整数乘法运算(分治法实现)endl;cout请输入第一个大整数(任意长度):;cinnum1;inti=0;//判断第一个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入for(i=0;inum1.size();i++){if(num1[i]'0'||num1[i]'9'){cout您输入的数据不合法,请输入有效的整数!endl;cinnum1;i=-1;}}cout请输入第二个大整数(任意长度):;cinnum2;//判断第二个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入for(i=0;inum2.size();i++){if(num2[i]'0'||num2[i]