分而治之是我们学习算法时遇到的第一种方法，它的原理很简单。
1、将一个问题的实例划分为一个或较多个较小的实例/
2、解决每一个较小的实例。
3、合并较小的实例，获得原实例的答案。
我们通过分而治之的方法解决的问题，大致有我们曾接触过的快排，Strassen矩阵乘法，大整数乘法。我们往往做题中接触最多的便是大整数乘法，今天我们就以此为例来解释一下分而治之的思想，并解决一下如何进行大整数乘法。
我们都知道在程序中int类型是有范围的，那么当我们遇到超过范围的数字又该怎么办那？
很简单，用我们刚刚所讲到的分而治之，我们可以将一个很长的数字分割到我们可接受的范围，比如这样1234567891313213213，用字符串来存储并将其123/4567/8913/1321/3213这样分割成几份，分别相乘，通过加减来得到最后的结果。
比如我们计算 464546545456*132123132=？
我们这样来 464546545456 = 46454*10e7+6545456
132123132 = 13*10e7+2123132
464546545456*132123132= （46454*10e7+6545456）*（13*10e7+2123132）来计算
用公式表示
u = x*10em+y
v = w*10em+z
uv = (x*10em+y)*(w*10em+z) = xw*10e2m+(xz+wy)*10em+yz
当然如果分开后的数字仍然过大，我们完全可以采用递归的方法，将其继续分割，直到我们规定的阈值。
代码如下
largBig bigMul(string u,string v){
int ns1 = u.length()/2;
int ns2 = v.length()/2;
int n = ns1>ns2?ns1:ns2;
if(s1.length()==0||s2.length()==0){
return 0;
}else if(n<=4){
return u*v;//常规乘法
}else{
m = n/2;
x = u divide 10em; y =u rem 10em;
w = v divide 10em; z =v rem 10em;
return bigMul(x,w)*10e2m+(bigMul(x,z)+bigMul(w,y))*10em+bigMul(y,z);
}
上面的代码很好的展示了，如何用分治法计算大数相乘。
这里是具体实现，将二分改为将每一个数字看作一份，所以效率较低。
#include<iostream> #include<string> #include<vector> using namespace std; int main(){ vector<int> aa,bb,cc; string a,b; cin>>a>>b; for(int i=a.size()-1;i>=0;i--) aa.push_back(a[i]-'0'); for(int i=b.size()-1;i>=0;i--) bb.push_back(b[i]-'0'); for(int i=0;i<a.size()+b.size();i++) cc.push_back(0); //处理乘法 for(int i=0;i<aa.size();i++){ for(int j=0;j<bb.size();j++){ cc[i+j]+=(aa[i]*bb[j])%10; cc[i+j+1]+=(aa[i]*bb[j])/10; //cout<<'\n'<<cc[i+j]<<" "<<cc[i+j+1]; } //cout<<cc[i]<<" "<<'\n'; } //处理进位 for(int i=0;i<aa.size()+bb.size()-1;i++){ cc[i+1]+=cc[i]/10; cc[i]=cc[i]%10; } //将首位为0抹去 if(cc[aa.size()+bb.size()-1]!=0){ cout<<cc[aa.size()+bb.size()-1]; } for(int i=aa.size()+bb.size()-2;i>=0;i--){ cout<<cc[i]; } return 0; }