1、分治法
有两点需要理解：
（1）分治法基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。
（2）递归的解这些子问题，然后将各子问题的解合并得到原问题的解。
分治法的重点是分析问题是否可以划分为规模较小的子问题，难点是如何划分以及划分之后如何将各个子问题的解合并成最终的解。这一般需要用到数学知识或者其他理论。
以大数相乘为例，有A,B两个大数，都为n位，要计算A*B，需要将A和B划分成两等份，如下图所示：
Paste_Image.png
将A分成a1和a0两等份，将B分成b1和b0两等份，长度都为n/2。那么有：
A = a1 * 10^(n/2) + a0
B = b1 * 10^(n/2) + b0
A * B = c2 * 10^n + c1 * 10^(n/2) + c0
其中：
c2 = a1 * b1
c1 = a0 * b1 + b0 * a1 = (a1 + a0) * (b1 + b0) - (c2 + c0)
(尽量减少乘法运算，需要将c1变形成后面的式子)
这样，就进行了一次划分，然后继续递归进行划分，每次划分都按照以上式子进行合并，最终便可得到最终的答案。
2、实现
（1）处理正负号
做乘法处理的时候应该是两个正数，最终的结果的正负可以提前判断。最后只需要将结果按照正负号处理即可。判断代码如下：
Paste_Image.png
（2）符号处理过之后处理长度问题
并不是每次相乘的两个数的长度都是相同的，所以需要做一些预处理，将这两个相乘的数都处理成长度相同的两个数，这需要添加前置0，代码如下：
Paste_Image.png
两个数的长度必须为2的指数倍，因为每次划分都是除以2，所以可能最终的数前面会有0补充，所以最终的两个数长度一致，而且长度应该为离较长的那个数的长度最近的2的指数倍的那个数（有点绕，但是很好理解）。例如
A = 1234334 //长度为7
B = 12343 //长度为5
那么处理后应该是这样的：
A = 01234334 // 长度为8，8是离7最近的2的指数倍的数，2^3 = 8
B = 00012343
若长度大于2，那么处理过后的长度最小应该为4，长度处理代码如下：
Paste_Image.png
到此，长度n就已经处理好了。
（3）关键部分，分治法处理大数相乘逻辑
回顾之前的分析，首先我们需要将其划分成相等的两部分a1,a0和b1,b0，然后按照公式相加和相减，这就需要大数相加和相减的算法。大数相加和相减的算法这里就不多介绍了，直接上代码（大数相减的代码略长，这里就不列出了，最后会附代码链接）：
Paste_Image.png
大数相加会有一个前置0的处理，需要注意的地方就是当数据为0的时候或者为0000（多个0）的情况，最终处理结果应该为0，代码如下：
Paste_Image.png
我们注意到，后面会有一个10^n的运算，其实就是在后面加上n个零，代码如下：
Paste_Image.png
还需要的是字符串和整数的转换处理，代码如下：
Paste_Image.png
![Uploading f_067038.png . . .]
最后就是相乘的逻辑了，递归首先需要一个出口。出口就是当长度为2，有代码可知，当长度为2时，我们将其划分成长度为1的四个数a1,a0,b1,b0，然后便可以按照公式计算最终结果。
当长度不为2时，即长度大于2时，需要进行进一步递归划分。然后分别计算各个部分的c2，c1，c0值，最终合并。代码如下：
Paste_Image.png
这就是大数相乘的分治法解法，其实挺简单的，只是很多细节需要处理。需要代码请戳这里
网友评论