《分治法 大整数乘法 c++实现》由会员分享，可在线阅读，更多相关《分治法 大整数乘法 c++实现（8页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析基础实验报告实验名称 分治法求大整数乘法 学 院 计算机学院 专业班级 计算机科学与技术 09(2)班 学 号 3109005933 姓 名 黄进杰 指导教师 顾 国 生 2012 年 12 月 03 日1一、一、 实验目的实验目的通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设计和算法复 杂性分析等。二、实验环境二、实验环境C-Free三、实验内容三、实验内容（1 1）问题的描述）问题的描述 通过分治法求两个大整数的乘法 （2 2）算法设计思想）算法设计思想将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题互相独立且与原问 题相同。递归地解这些子
2、问题，然后将各个子问题解合并得到原问题的解。 （3 3）程序设计）程序设计#include #include #include #include using namespace std; /string 类型转换成 int 类型int string_to_num(string k)/string 字符串变整数型例如 str=“1234“，转换为整数的 1234. int back; stringstream instr(k); instrback; return back; /整形数转换为 string 类型string num_to_string(int intValue)string re
3、sult;stringstream stream; stream result;/从 stream 中抽取前面放入的 int 值return result; /在字符串 str 前添加 s 个零string stringBeforeZero(string str,int s)for(int i=0;i str2.size() str2 = stringBeforeZero(str2,str1.size() - str2.size();else if (str1.size() =0;i-) int c = (str1i - 0) + (str2i - 0) + flag;/利用 ASCII 码对
4、字符进行运算,这里加上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); return result; /*两个大整数字符串相减，超出计算机表示范围的数也能实现相减(在这里比较特殊，第一个参数一
5、定大于第二个参数,因为：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) 所以本函数里不用考虑最终得到结果为负数的情况，至于计算有关大整数负数相乘的问题可以通过其他途径判断*/string stringSubtractstring(string str1,string str2) /对传进来的两个数进行修剪，如果前面几位有 0 则先去掉，便于统一处理while (0 = st
6、r103while (0 = str20 /使两个字符串长度相等if (str1.size() str2.size() str2 = stringBeforeZero(str2,str1.size() - str2.size();string result;for(int i=str1.size()-1;i=0;i-) int c = (str1i - 0) - (str2i - 0);/利用 ASCII 码进行各位减法运算if (c 1)x=x.substr(1,x.size()-1); /对传进来的第二个数进行修剪，如果前面几位有 0 则先去掉，便于统一处理while (0 = y0 /*
7、这里的 f 变量代表在两个数据字符串长度不想等或者不是 2 的指数倍的情况下，所要统一的长度，这样做是为了让数据长度为 2 的 n 次方的情况下便于利用分治法处理*/int f=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
8、) 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();5if (1 = x.size() /数据长度为 1 时,在前面补一个 0(这里之所以会出现长度为 1 的数据是因为前面对数据修剪过)x=stringBeforeZero(x,1
9、); 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); b1 = y.substr(0,s/2); b0 = y.substr(s/2,s-1); string result;
10、if( s = 2) /长度为 2 时代表着递归的结束条件 int na = string_to_num(a1); int nb = string_to_num(a0); int nc = string_to_num(b1); int nd = string_to_num(b0);result = num_to_string(na*10+nb) * (nc*10+nd); else /长度不为 2 时利用分治法进行递归运算/* 小提示:c = a*b = c2*(10n) + c1*(10(n/2) + c0;a = a1a0 = a1*(10(n/2) + a0;b = b1b0 = b1*
11、(10(n/2) + b0;c2 = a1*b1; c0 = a0*b0;c1 = (a1 + a0)*(b1 + b0)-(c2 + c0);6*/string c2 = IntMult(a1,b1);/ (a1 * b1)string c0 = IntMult(a0,b0);/ (a0 * b0)string c1_1 = stringAddstring(a1,a0);/ (a1 + a0)string c1_2 = stringAddstring(b1,b0);/ (b1 + b0)string c1_3 = IntMult(c1_1,c1_2);/ (a1 + a0)*(b1 + b0
12、)string c1_4 = stringAddstring(c2,c0);/ (c2 + c0)string c1=stringSubtractstring(c1_3,c1_4);/ (a1 + a0)*(b1 + b0)-(c2 + c0)string s1=stringFollowZero(c1,s/2);/ c1*(10(n/2)string s2=stringFollowZero(c2,s);/ c2*(10n)result = stringAddstring(stringAddstring(s2,s1),c0);/ c2*(10n) + c1*(10(n/2) + c0 retur
13、n result; int main() int f=1;while (1 = f)string A,B,C,D; string num1,num2; string r; system(“title 3109005933 09 计科 02 班 黄进杰 分治法大整数乘法“);system(“color 0a“); coutnum1;int i=0; /判断第一个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入for(i=0 ;i 9) coutnum1;i=-1;coutnum2; /判断第二个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入for(i=0 ;i 9) coutnum2;i=-1;r=IntMult(num1,num2); /对求得的结果进行修剪，去掉最前面的几个 0while (0 = r0 cout“两数相乘结果为:“endl;coutnum1“ “*“ “num2“ “=“ “rendlendl; （4 4）数据输入和结果输出）数据输入和结果输出四、实验心得与小结四、实验心得与小结通过本次试验我对分治法有了更深的了解。利用分治法可以将问题简化，这有助于我 们在实际中解决一些复杂性较大的问题，提高程序的运行效率。五、指导教师成绩评定：五、指导教师成绩评定：
