分治算法：分治算法由两部分组成，分和治，分是使问题规模变小，递归解决较小的问题，治是从子问题的解中构建原问题的解。
传统上，在正文中至少含有两个递归调用的例程叫做分治算法，而正文中只含有一个递归调用的例程不是分治算法。
我们一般坚持子问题是不相交的。
在前面写的归并排序和快速排序就是分治算法的一种例程。
所有有效的分治算法都是把问题分成一些子问题，每个子问题都是原问题的一部分，然后进行某些附加的工作，以算出最后的答案。
分治算法解决大整数相乘。
如果X = 61438521，而Y = 94736407，那么XY = 5820464730934047
如果把x和y拆成两半，分别由最高几位和最低几位数字组成。
XL = 6143，XR = 8521，YL=9473，YR = 6407.
则 X = XL10⁴ +XR，Y = YL10⁴ + YR。
则 XY = XLYL10⁸ + YL10⁴XR + XL10⁴YR + XRYR
则 XY = XLYL10⁸ + (XRYL+XLYR)10⁴+ XRYR
则 XY = XLYL*10⁸ + ((XL+XR)(YR+YL)-XLYL-XRYR)10⁴+ XRYR
则 XY可以由3次乘法组成，即 XLYL，XRYR，（XL+XR）(YR+YL)
它们每一个都是原来问题大小的一半(N/2)，10⁸和10⁴作乘法实际就是添加一些0。
核心算法
string multiply(string &x, string &y) {bool flag = false;//最终结果的正负号,0为正号，1为负号if (x.at(0) == '-' && y.at(0) !='-' || x.at(0) != '-' && y.at(0) == '-') {//一正一负，最终符号为负flag = true;}if (x.at(0) == '-') {//去除负号x = x.substr(1);}if (y.at(0) == '-') {//去除负号y = y.substr(1);}int init_len = 4;if (x.length() > 2 || y.length() > 2) {// 长度大于2时，最小长度应该为4，故初始值为4if (x.length() >= y.length()) {while (init_len < x.length())init_len *= 2; //计算两个数最终的长度//添加前置0if (x.length() != init_len) {addPreZero(x, init_len - x.length());}addPreZero(y, init_len - y.length());}else {while (init_len < y.length())init_len *= 2;//添加前置0addPreZero(x, init_len - x.length());if (y.length() != init_len) {addPreZero(y, init_len - y.length());}}}int n = x.length();string result;if (n <= 2) {//长度为2时，结束递归int x1 = strToInt(x);int y1 = strToInt(y);int z = x1 * y1;result = intToStr(z);}else {string xl, xr, yl, yr;xl = x.substr(0, n / 2);xr = x.substr(n / 2, n);yl = y.substr(0, n / 2);yr = y.substr(n / 2, n);string xlyl = multiply(xl, yl);string xryr = multiply(xr, yr);string xlAddXr = add(xl, xr);string ylAddYr = add(yl, yr);string t = add(xlyl, xryr);string t1 = multiply(xlAddXr, ylAddYr);string t2 = subtract(t1, t);addLastZero(t2, n / 2);addLastZero(xlyl, n);result = add(add(t2, xlyl), xryr);}if (flag) {//结果为负数result.insert(0, "-");}return result;}
其它函数
#include <iostream>#include <malloc.h>#include <algorithm>#include <sstream>using namespace std;int strToInt(string k) {//string字符串变整数型int back;stringstream instr(k);instr >> back;return back;}string intToStr(int intValue) {string result;stringstream stream;stream << intValue;//将int输入流stream >> result;//从stream中抽取前面放入的int值return result;}void removePreZero(string &str) {//去掉前置0,需要考虑只有一个0或者全部是0的情况if (str.length() == 1)return;int k = 0;for (int i = 0; i < str.length(); i++) {if (str.at(i) == '0') {k++;}else {break;}}if (k == str.length())str = "0";else {str = str.substr(k);}}//大数相加，不考虑前置0的情况string add(string x, string y) {string result = "";//去掉前置0removePreZero(x);removePreZero(y);//反转字符串方便相加reverse(x.begin(), x.end());reverse(y.begin(), y.end());for (int i = 0, j = 0; j || i < max(y.length(), x.length()); i++) {int t = j;if (i < x.length())t += (x.at(i) - '0');if (i < y.length())t += (y.at(i) - '0');int q = t % 10;result.insert(0, intToStr(q));j = t / 10;}return result;}string subtract(string &x, string &y) {string result = "";//去掉前置0removePreZero(x);removePreZero(y);int len_x = x.length();int len_y = y.length();int len = len_x > len_y ? len_x : len_y;int *tempResult = (int *)malloc(sizeof(int) * len);string sign;if (len_x > len_y) {// x - y为正数sign = "+";}else if (len_x < len_y) {//x-y为负数sign = "-";}else {//长度相同则判断各位的大小int i;for (i = 0; i < len_x; i++) {if (x.at(i) == y.at(i))continue;else if (x.at(i) > y.at(i)) {sign = "+";break;}else {sign = "-";break;}}//说明没有break，说明x == yif (i == len_x) {return "0";}}//反转字符串方便相减reverse(x.begin(), x.end());reverse(y.begin(), y.end());int q = 0;//若x大，则直接相减，否则用y-x，并且最终加上负号for (int i = 0; i < len; i++) {int aint = i < len_x ? x.at(i) - '0' : 0;int bint = i < len_y ? y.at(i) - '0' : 0;if (sign.at(0) == '+') {tempResult[q++] = aint - bint;}else {tempResult[q++] = bint - aint;}}for (int i = 0; i < q; i++) {if (tempResult[i] < 0) {tempResult[i + 1] -= 1;tempResult[i] += 10;}}q--;while (tempResult[q] == 0)q--;for (int i = q; i >= 0; i--) {result += intToStr(tempResult[i]);}if (sign.at(0) == '-')return sign + result;return result;}//添加前置0void addPreZero(string &str, int zero_num) {for (int i = 0; i < zero_num; i++)str.insert(0, "0");}//添加后置0void addLastZero(string &str, int zero_num) {for (int i = 0; i < zero_num; i++)str += "0";}
如果觉得《第十章分治算法(大数相乘)》对你有帮助，请点赞、收藏，并留下你的观点哦！
