分治法的基本思想:把一个规模为n的问题分解为k个规模较小的自问题，这些子问题互相独立且与原问题相同。
一般的算法设计模式：
Divide-and-Conquer(P)
{
if(|P|<=n0)
Adhoc(P);
divide P into smaller subinstances
P1,P2,...,Pk;
for(int i = 1;i <= k;++i)
yi = Divide-and-Conquer(Pi);
return Merge(y1,y2,...,yk);
}
|P|表示问题的规格
n0表示当P规模不超过n0那么问题就已经容易解决不需要去分解
Adhoc(P)是该分治算法的基本子算法，当规模不超过n0就可以直接用它得出结果
Merge()的作用是该分治算法中的合并子算法，将所有子问题的解合并成P的解
例子，就是一个合并排序
template<class Type> void Merge(Type *sd,Type *si,int left,int m,int right) { int i = left,j = m+1; int k = left; while(i<=m && j<= right) { sd[k++] = si[i] < si[j]? si[i++]:si[j++]; } while(i<=m) { sd[k++] = si[i++]; } while(j<=right) { sd[k++] = si[j++]; } } template<class Type> void MergePass(Type *ar,Type *br,int n,int s) {// s = 2; // 0 1 2 3 //4 5 6 7 //8 9 cout<<"s = "<<s<<endl; for(int i = 0;i+2*s-1 <= n-1; i+=2*s) { Merge(ar,br,i,i+s-1,i+2*s-1); cout<<i<<" "<<i+s-1<<" "<<i+2*s-1<<endl; } if(n-1 > i+s-1) { Merge(ar,br,i,i+s-1,n-1); cout<<i<<" "<<i+s-1<<" "<<n-1<<endl; } else//两个作用，一个是预防后面没有值了，还有一个是确保br给了ar，这个看后面你就懂了 { for(int j = i;j<n;++j) { ar[j] = br[j]; } } Print_Array(ar,n); }
template<class Type> void MergeSort(Type *ar,int n) { Type *br = new Type[n]; int s = 1; while(s < n) { MergePass(br,ar,n,s);//分治，分成小段小段，顺便的MergePass完成了分治中的合并子算法，和子算法的计算 s+=s; MergePass(ar,br,n,s);//同上，顺便把所有数据给ar s+=s; } delete []br; }
在用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。
分治算法棋盘覆盖的思路:
采用的是L型骨牌覆盖棋盘
(1)先看2*2，有一个点和其他的不同，另外三个被同一个L给覆盖了
(2)递推2^2*2^2,如果左上的2*2有，那么[1][2],[2][2],[2][1]构成了一个L，然后再分看，四个部分各一个L就补全了
要是8*8那么[3][4],[4][3],[4][4]，找出规律，n*n,[n/2-1][n/2],[n/2][n/2-1],[n][n]构成第一个，然后n=n/2，一直到n=1为止
void CheseBoard(Array ar,int tr,int tc,int dr,int dc,int size)
dr,dc表示特殊点所在的位置,行列,tr,tc,棋盘左上角放个行号，棋盘左上角方格列号
