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

《分治法 大整数乘法 c++实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、>#include#includeusingnamespacestd;//string类型转换成int类型intstring_to_num(stringk)//string字符串变整数型例如str="1234"，转换为整数的1234.{intback;stringstreaminstr(k);instr>>back;returnback;}//整形数转换为string类型stringnum_to_string(intintValue){stringresult;stringstreamstream;stream<

3、stream>>result;//从stream中抽取前面放入的int值returnresult;}//在字符串str前添加s个零stringstringBeforeZero(stringstr,ints){for(inti=0;i

4、size()>str2.size()){str2=stringBeforeZero(str2,str1.size()-str2.size());}elseif(str1.size()=0;i--){intc=(str1[i]-'0')+(str2[i]-'0')+flag;//利用ASCII码对字符进行运算,这

5、里加上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

6、*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){

7、str1=str1.substr(1,str1.size()-1);}while('0'==str2[0]&&str2.size()>1)7{str2=str2.substr(1,str2.size()-1);}//使两个字符串长度相等if(str1.size()>str2.size()){str2=stringBeforeZero(str2,str1.size()-str2.size());}stringresult;for(inti=str