|
算法导论课作业：分治法求解大整数乘法 – 学号：20204227058
求解思想
实现大整数乘法的方法有许多种，其中我们最简单的方法就是小学里面教的竖式算法，这种方法在计算过程中数
A
A
A需要和数
B
B
B中的每一位数相乘，并且最终对每一位进行相加，就整体而言，复杂度为
O
(
n
2
)
O(n^2)
O(n2)，对每一位需要进行相乘和进位即为O(n)，又要对n位进行操作，最终结果就是
O
(
n
2
)
O(n^2)
O(n2)。 为此，我们采用分治法来处理大数乘法，进而进行算法复杂度降低的尝试，我们首先将两个数字
A
A
A和
B
B
B各自分成前后两段，当然这种时候可能存在两边数字长度不一样，而且比较长的一边不是偶数导致无法整除的方法，所以我们采用前方填充0的办法把两个数字填充成长度大于最长部分的前方填充0的偶长字符串。 接下来，我们将
A
A
A分成
A
1
,
A
2
A_1, A_2
A1,A2, 同时将
B
B
B分成
B
1
B_1
B1和
B
2
B_2
B2， 然后原本的计算公式就变成了
A
1
∗
B
1
∗
1
0
N
+
(
A
1
∗
B
2
+
A
2
∗
B
1
)
∗
1
0
N
/
2
+
A
2
∗
B
2
A_1 * B_1 * 10^N + (A_1 * B_2 + A_2 * B_1) * 10^{N/2} +A_2 * B_2
A1∗B1∗10N+(A1∗B2+A2∗B1)∗10N/2+A2∗B2，这样一来，递归每一步的时间复杂度就变成了
O
(
n
)
O(n)
O(n)，主要是加法，分治则包括四个子问题，每个子问题的规模是原本的
1
/
2
1/2
1/2, 也就是
T
(
n
)
=
4
T
(
n
/
2
)
+
O
(
n
)
T(n)=4T(n/2)+O(n)
T(n)=4T(n/2)+O(n), 一层层递归就是
n
+
4
∗
n
/
2
+
.
.
.
+
4
l
o
g
2
n
∗
1
n+4*n/2+...+4^{log_2^{n}}*1
n+4∗n/2+...+4log2n∗1, 然后后面我们用一个换底公式把最后一项改一下，结果就是
n
l
o
g
2
4
n^{log_2^4}
nlog24,也就是
n
2
n^2
n2, 我们这里可以直接用最大项，当然其实就不那么看，我们也可以大致得出，这个复杂度如果算上一些小的项目可能已经比原本的竖式算法还要大了，为此，我们必须要想办法去把复杂度降下来。 降低复杂度的方法就是我们再去改一下我们的公式，我们把计算公式中间那一部分给替换成如下公式，也就是
(
A
1
∗
B
2
+
A
2
∗
B
1
)
=
(
A
1
−
A
2
)
∗
(
B
2
−
B
1
)
+
A
1
∗
B
1
+
A
2
∗
B
2
(A_1*B_2 + A_2*B_1) = (A_1 - A_2) * (B_2 - B_1) + A_1 * B_1 + A_2 * B_2
(A1∗B2+A2∗B1)=(A1−A2)∗(B2−B1)+A1∗B1+A2∗B2 这时候，我们发现之前已经计算过的
A
1
∗
B
1
A_1 * B_1
A1∗B1 和
A
2
∗
B
2
A_2 * B_2
A2∗B2都被复用了，也就是说，我们乘法只需要计算三次了。这时候，我们来分析下这时候的复杂度，同样也是上面的方法，我们最后可以看成
T
(
n
)
=
3
T
(
n
/
2
)
+
O
(
n
)
T(n)=3T(n/2)+O(n)
T(n)=3T(n/2)+O(n), 最后计算的时候就是
n
+
3
∗
n
/
2
+
.
.
.
+
3
l
o
g
2
n
∗
1
n+3*n/2+...+3^{log_2^n}*1
n+3∗n/2+...+3log2n∗1，最后一项也就变成了
n
l
o
g
2
3
n^{log_2^3}
nlog23, 最后一项的大小开始比
n
2
n^2
n2要小了，这时候我们需要对这个等比数列来进行求和，结果如下
n
∗
(
3
/
2
)
l
o
g
2
n
−
1
3
/
2
−
1
=
n
∗
2
∗
(
n
l
o
g
2
3
n
l
o
g
2
2
−
1
)
=
2
∗
n
∗
(
n
l
o
g
2
3
−
l
o
g
2
2
−
1
)
=
2
n
(
n
l
o
g
2
3
/
2
−
1
)
=
2
n
l
o
g
2
3.5
−
2
n
<
n
2
n*\frac{(3/2)^{log_2^{n}}-1}{3/2-1}=n*2*(\frac{n^{log_2^3}}{n^{log_2^2}}-1)= 2 * n*(n^{log_2^3-log_2^2}-1)=2n(n^{log_2^{3/2}}-1)=2n^{log_2^{3.5}}-2n < n^2
n∗3/2−1(3/2)log2n−1=n∗2∗(nlog22nlog23−1)=2∗n∗(nlog23−log22−1)=2n(nlog23/2−1)=2nlog23.5−2n
string result = multi(num1, num2);
result = cut_zero(result);
return result;
}
string multi(string num1, string num2){
//cout
flag_2 = -1;
num2 = num2.substr(1);
}
// 如果异号，我们采用
if(flag_1 + flag_2 == 0){
final_flag = -1;
}
int maxsize = num1.size() > num2.size() ? num1.size() : num2.size();
if(maxsize % 2 == 1){
maxsize += 1;
}
num1 = to_odd_string(num1, maxsize);
num2 = to_odd_string(num2, maxsize);
//cout
string res = convert_multi(num1, num2);
if(final_flag == -1){
string ret = "-";
res = ret + res;
}
//cout
int n_1 = str2num(num1);
int n_2 = str2num(num2);
return num2str(n_1 * n_2);
}
string add(string num1, string num2){
int flag_1 = 1, flag_2 = 1;
if(num1[0] == '-'){
flag_1 = -1;
}
if(num2[0] == '-'){
flag_2 = -1;
}
if(flag_1 + flag_2 == 0){
// 两个数字一正一负
if(flag_1 == -1){
num1 = num1.substr(1);
if(compare(num1, num2)){
// 负数绝对值比正数大 num1绝对值-num2绝对值，返回值符号为负
string fret = "-";
return fret + single_minus(num1, num2);
}else{
// 负数绝对值比正数小 num2绝对值-num1绝对值
return single_minus(num2, num1);
}
}else if(flag_2 == -1){
//cout
//cout
return single_add(num1, num2);
}
}
// 比较两个字符串数字的大小
bool compare(string num1, string num2){
//cout
pos_1 = i;
break;
}
}
for(int i=0; i
pos_2 = i;
break;
}
}
if(num1.size() - pos_1 > num2.size() - pos_2){
return true;
}else if(num1.size() - pos_1
if(num1[i] == num2[j]){
continue;
}else if(num1[i] > num2[j]){
return true;
}else{
return false;
}
}
return true;
}
// 纯正数或者负数相加
string single_add(string num1, string num2){
int i = num1.length() - 1, j = num2.length() - 1, add = 0;
string ans = "";
while (i >= 0 || j >= 0 || add != 0) {
int x = i >= 0 ? num1[i] - '0' : 0;
int y = j >= 0 ? num2[j] - '0' : 0;
int result = x + y + add;
ans.push_back('0' + result % 10);
add = result / 10;
i -= 1;
j -= 1;
}
// 计算完以后的答案需要翻转过来
reverse(ans.begin(), ans.end());
//cout
ret += "0";
}
return ret;
}
// 前面的数字减去后面的数字，然后填充到原本的长度
string single_minus(string num1, string num2){
int i = num1.size() - 1, j = num2.size() - 1, minus = 0;
string ans = "";
while(i >=0 || j >=0){
int x = i >= 0 ? num1[i] - '0' : 0;
int y = j >= 0 ? num2[j] - '0' : 0;
int result = minus + x - y;
if(result
minus = 0;
}
ans.push_back('0' + result);
i -= 1;
j -= 1;
}
reverse(ans.begin(), ans.end());
//cout
num = "0" + num;
}
return num;
}
// 删除当前数字前的所有零
string cut_zero(string num){
int flag = 1, pos = 0, beginer = 0;
if(num[0] == '-'){
flag = -1;
beginer = 1;
}
if(num == "0"){
return "0";
}
for(int i=beginer; i
pos = i;
break;
}
}
num = num.substr(pos);
if(flag == -1){
string f = "-";
num = f + num;
}
return num;
}
string num2str(int i)
{
stringstream ss;
ss
for(int i=0; i
return false;
}
}
return true;
}
};
int main(){
Solution sl;
string a, b;
while(true){
cin >> a >> b;
cout |