使用分治法解决大数乘法问题
问题分析
大数乘法问题,由于不限制数据的大小,使用基本数据类型无法直接计算超过其最大表示范围的数据。因此需要考虑对大数进行分解 。
首先观察一下,乘法最基础的计算方法——列竖式。以999*999
为例
十万
万
千
百
十
个
9
9
9
9
9
9
9*9
8
1
90*9
8
1
0
900*9
8
1
0
0
9*90
8
1
0
90*90
8
1
0
0
900*90
8
1
0
0
0
9*900
8
1
0
0
90*900
8
1
0
0
0
900*900
8
1
0
0
0
0
9
9
8
0
0
1
可以看到大数乘法被分解为了多步简单的计算 ,且每步计算是相互独立的 ,最后只需要将多步计算的结果累加即可。
方法引入
分治法
思想
将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
适用情况
分治法能够解决的问题具有以下特征
该问题的规模缩小到一定的程度就可以很容易地解决。
问题可以分解为多个规模较小的相同问题,即该问题具有最优子结构 。
将该问题所分解出的子问题的解合并就可以得到该问题的解。
该问题所分解出的各个子问题是相互独立的,即子问题之间不存在公共性的问题。
特征1是大多数问题都能满足的
特征2是使用分治法的前提 ,也是大部分问题能够满足的
特征3是最关键的 ,能否在该问题上使用分治法完全取决于特征3
特征4涉及到分治法的效率问题 ,如果子问题之间不是相互独立的,则分治法需要重复地解决公共的问题,降低效率。针对这个效率问题,就设计出了动态规划法 来应对具有重叠子问题的最优子结构问题。
使用步骤
将原问题分解为多个规模较小、相互独立且和原问题形式相同的子问题。
若子问题规模足够小则直接解决,否则使用递归 进一步分解子问题直到能够解决为止。
将多个子问题的解返回,通过递归合并为原问题的解。
方法实现
假设有大数a(长度为n)和b(长度为m)。这里使用二分法将大数进行拆分,则大数a、b可拆分为
a = a 1 ∗ 1 0 n / 2 + a 0 b = b 1 ∗ 1 0 m / 2 + b 0 a=a_1*10^{n/2}+a_0\\
b=b_1*10^{m/2}+b_0
a = a 1 ∗ 1 0 n / 2 + a 0 b = b 1 ∗ 1 0 m / 2 + b 0
则
a ∗ b = ( a 1 ∗ 1 0 n / 2 + a 0 ) ∗ ( b 1 ∗ 1 0 m / 2 + b 0 ) = a 1 ∗ b 1 ∗ 1 0 n / 2 + m / 2 + a 1 ∗ b 0 ∗ 1 0 n / 2 + a 0 ∗ b 1 ∗ 1 0 m / 2 + a 0 ∗ b 0 \begin{aligned}
a*b=(a_1*10^{n/2}+a_0)*(b_1*10^{m/2}+b_0)\\
=a_1*b_1*10^{n/2+m/2}+a_1*b_0*10^{n/2}\\+a_0*b_1*10^{m/2}+a_0*b_0
\end{aligned}
a ∗ b = ( a 1 ∗ 1 0 n / 2 + a 0 ) ∗ ( b 1 ∗ 1 0 m / 2 + b 0 ) = a 1 ∗ b 1 ∗ 1 0 n / 2 + m / 2 + a 1 ∗ b 0 ∗ 1 0 n / 2 + a 0 ∗ b 1 ∗ 1 0 m / 2 + a 0 ∗ b 0
可以发现大数乘法分解成了四个小数乘法,即a 1 ∗ b 1 a_1*b_1 a 1 ∗ b 1 、a 1 ∗ b 0 a_1*b_0 a 1 ∗ b 0 、a 0 ∗ b 1 a_0*b_1 a 0 ∗ b 1 、a 0 ∗ b 0 a_0*b_0 a 0 ∗ b 0 。如果分解出来的数字还是过大可以进一步分解。这里考虑将大数a、b分解到只有一位数字的规模进行求解。
方法函数设计
函数原型:以字符串类型传递两个大数
string cal (string, string) ;
先设计对较小规模的方法处理,判断两个字符串长度,将两个字符串转为int
进行计算之后再转回字符串返回
if (a.length () < 2 && b.length () < 2 ) { int ai = stoi (a); int bi = stoi (b); return to_string (ai * bi); }
再设计递归表达式,这里使用二分法分解大数。
二分法获取大数的前半部分和后半部分,主要通过substr
函数实现。
int ahalflen = a.length () / 2 ;int bhalflen = b.length () / 2 ;string ahead = "0" ; string atail = "0" ; if (a.length () > ahalflen && ahalflen > 0 ) { ahead = a.substr (0 , ahalflen); atail = a.substr (ahalflen, a.length () - ahalflen); } else { ahead = "0" ; atail = a; } string bhead = "0" ; string btail = "0" ; if (b.length () > bhalflen && bhalflen > 0 ) { bhead = b.substr (0 , bhalflen); btail = b.substr (bhalflen, b.length () - bhalflen); } else { bhead = "0" ; btail = b; }
递归表达式的设计,参考前面将大数a、b的乘法分解为a 1 ∗ b 1 a_1*b_1 a 1 ∗ b 1 、a 1 ∗ b 0 a_1*b_0 a 1 ∗ b 0 、a 0 ∗ b 1 a_0*b_1 a 0 ∗ b 1 、a 0 ∗ b 0 a_0*b_0 a 0 ∗ b 0 四个乘法,这里也设计四个递归表达式对应四个乘法。
string ahbh = cal (ahead, bhead); string atbt = cal (atail, btail); string ahbt = cal (ahead, btail); string atbh = cal (atail, bhead);
对乘法的解进行相应的补位。
ahbh.append ((a.length () - ahalflen) + (b.length () - bhalflen), '0' ); ahbt.append (a.length () - ahalflen, '0' ); atbh.append (b.length () - bhalflen, '0' );
将四个乘法的解合并并返回,其中add
函数是自定义设计的用于大数加法计算的函数
string res = "" ; res = add (ahbh, ahbt); res = add (res, atbh); res = add (res, atbt); return res;
关于add
函数的设计思路:使用int
数组从后往前依次存储大数的每一位数,同时最后的int
数组根据实际情况额外存储一位因进位而产生的数字。
具体流程
获取两个大数中最大的长度,反转两个大数字符串从个位数开始计算。
每次计算取出对应位数上的数字转为int
进行计算,判断其值是否需要做进位处理。
计算完成后,由于此时字符串是反转的状态,还需要对字符串进行一次反转。
这里的反转的循环从后往前,去除掉高位上不需要的0,同时使用zeroStart
来处理需要保留的中间部分的0,将需要保留的数字从后往前拼接起来并返回计算结果。
string add (string a, string b) { int maxlen = max (a.length (), b.length ()); int *sum = new int [maxlen](); reverse (a.begin (), a.end ()); reverse (b.begin (), b.end ()); for (int i = 0 ; i < maxlen; i++) { int a_bit = 0 ; int b_bit = 0 ; if (i < a.length ()) { a_bit = stoi (string (1 , a.at (i))); } if (i < b.length ()) { b_bit = stoi (string (1 , b.at (i))); } sum[i] += (a_bit + b_bit); if (i < maxlen - 1 && sum[i] > 9 ) { sum[i + 1 ] = sum[i] / 10 ; sum[i] %= 10 ; } } string res = "" ; bool zeroStart = true ; for (int i = maxlen - 1 ; i >= 0 ; i--) { if (sum[i] == 0 && zeroStart) { continue ; } zeroStart = false ; res.append (to_string (sum[i])); } return res; }
通过add
函数和cal
函数就能实现任意大数的乘法运算,解题的关键在于考虑将两个大数的乘法分解为多个小数的乘法。
源代码
完整源代码参考如下
#include <algorithm> #include <iostream> using namespace std;string add (string a, string b) { int maxlen = max (a.length (), b.length ()); int *sum = new int [maxlen](); reverse (a.begin (), a.end ()); reverse (b.begin (), b.end ()); for (int i = 0 ; i < maxlen; i++) { int a_bit = 0 ; int b_bit = 0 ; if (i < a.length ()) { a_bit = stoi (string (1 , a.at (i))); } if (i < b.length ()) { b_bit = stoi (string (1 , b.at (i))); } sum[i] += (a_bit + b_bit); if (i < maxlen - 1 && sum[i] > 9 ) { sum[i + 1 ] = sum[i] / 10 ; sum[i] %= 10 ; } } string res = "" ; bool zeroStart = true ; for (int i = maxlen - 1 ; i >= 0 ; i--) { if (sum[i] == 0 && zeroStart) { continue ; } zeroStart = false ; res.append (to_string (sum[i])); } return res; } string cal (string a, string b) { if (a.length () < 2 && b.length () < 2 ) { int ai = stoi (a); int bi = stoi (b); return to_string (ai * bi); } int ahalflen = a.length () / 2 ; int bhalflen = b.length () / 2 ; string ahead = "0" ; string atail = "0" ; if (a.length () > ahalflen && ahalflen > 0 ) { ahead = a.substr (0 , ahalflen); atail = a.substr (ahalflen, a.length () - ahalflen); } else { ahead = "0" ; atail = a; } string bhead = "0" ; string btail = "0" ; if (b.length () > bhalflen && bhalflen > 0 ) { bhead = b.substr (0 , bhalflen); btail = b.substr (bhalflen, b.length () - bhalflen); } else { bhead = "0" ; btail = b; } string ahbh = cal (ahead, bhead); string atbt = cal (atail, btail); string ahbt = cal (ahead, btail); string atbh = cal (atail, bhead); ahbh.append ((a.length () - ahalflen) + (b.length () - bhalflen), '0' ); ahbt.append (a.length () - ahalflen, '0' ); atbh.append (b.length () - bhalflen, '0' ); string res = "" ; res = add (ahbh, ahbt); res = add (res, atbh); res = add (res, atbt); return res; } int main () { string a, b; cin >> a >> b; cout << cal (a, b); }
参考资料
看了就会的大整数乘法运算与分治算法
分治算法详解