智者乐山仁者乐水分治法求2个大整数相乘

2021年1月19日发(作者：阳翰笙)
分治法求
2
个大整数相乘

一、
问题描述

利用分治法实现两个大整数的乘法。

二、算法设计思想

将一个规 模为
n
的问题分解为
k
个规模较小的子问题，
这些子问题互相独立且 与原问题
相同。递归地解这些子问题，然后将各个子问题解合并得到原问题的解。

三、程序实现

#include

#include

#include

#include
using namespace std;

int string_to_num(string k)
{





int back;





stringstream instr(k);





instr>>back;





return back;

}

string num_to_string(int intValue)//
整形数转换为
string
类型

{

string result;

stringstream stream;

stream << intValue;

stream >> result;

return result;
}
string stringBeforeZero(string str,int s)
{

for(int i=0;i
{(0,

return str;
}
string stringAddstring(string str1,string str2) //
实现大整数加法

{

if (() > ())


{str2 = stringBeforeZero(str2,() - ());}

else if (() < ())



{
str1 = stringBeforeZero(str1,() - ());

string result;

int flag=0;

for(int i=()-1;i>=0;i--)

{
}


int c = (str1[i] - '0') + (str2[i] - '0') + flag;


flag = c/10;


c %= 10;



(0,num_to_string(c));

}

if (0 != flag)


{(0,num_to_string(flag));}


return result;
}
string stringSubtractstring(string str1,string str2)
{

while ('0' == str1[0]&&()>1)

{str1=(1,()-1);}

while ('0' == str2[0]&&()>1)

{str2=(1,()-1);}

if (() > ())


{str2 = stringBeforeZero(str2,() - ());}

string result;

for(int i=()-1;i>=0;i--)

{


int c = (str1[i] - '0') - (str2[i] - '0');


if (c < 0)

{


c +=10;


int prePos = i-1;



char preChar = str1[prePos];


while ('0' == preChar) {



str1[prePos]='9';



prePos -= 1;



preChar = str1[prePos];}


str1[prePos]-=1;

}

(0,num_to_string(c));

}

return result;
}
string stringFollowZero(string str,int s)
{

for(int i=0;i
{((),

return str;
}
string IntMult(string x,string y)//
递归函数

//
分治法大整数乘法实现函数

{


while ('0' == x[0]&&()>1)