算法设计与分析（作业一）

int s = x.size(); string a1,a0,b1,b0; if( s > 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;

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*(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);

****************************************************/ 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) 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*(10^n)

result = stringAddstring(stringAddstring(s2,s1),c0);// c2*(10^n) + c1*(10^(n/2)) + c0 }

return result; }

int main() {

int f=1;

string A,B,C,D;

string num1,num2; string r;

system(\软件3班 王建君 20122668 分治法实现大整数乘法\ cout<<\请输入第一个大整数(任意长度):\ cin>>num1; int i=0;

//判断第一个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入

for(i=0 ;i < num1.size();i++) {

if (num1[i]<'0' || num1[i]>'9') {

cout<<\您输入的数据不合法,请输入有效的整数!\ cin>>num1; i=-1; } }

cout<<\请输入第二个大整数(任意长度):\ cin>>num2;

//判断第二个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入

for(i=0 ;i < num2.size();i++) {

if (num2[i]<'0' || num2[i]>'9') {

cout<<\您输入的数据不合法,请输入有效的整数!\ cin>>num2; i=-1; } }

r=IntMult(num1,num2);

//对求得的结果进行修剪，去掉最前面的几个0 while ('0' == r[0]&&r.size()>1) {

r=r.substr(1,r.size()-1); }

cout<<\两数相乘结果为:\

cout<

五、结果分析

计算结果截图如下

即当00112233445566778899与11210748210374098777790374124081568900

99887766554433221100相乘

得