分治算法：一、基本概念二、基本思想和策略三、分治法场景五、分治法复杂性分析六、可以用分治法求解的几个经典问题(1)二分搜索)2)大整数乘法)3) Strassen矩阵乘法)4)棋盘格
）
一.基本概念
在计算机科学中，分治法是重要的算法。 字面上的解释是“分而治之”，将一个复杂问题分成两个以上相同或相似的子问题，再将子问题分成更小的子问题……直到最后，子问题很容易直接求解，是原问题解的子问题解的综合。 该技术是排序算法(快速排序、合并排序)、傅立叶变换)、快速傅立叶变换)……等许多高效算法的基础。
可以用计算机求解的问题所需的计算时间取决于其规模。 问题的规模越小，直接求解就越容易，求解所需的计算时间也越少。 例如，对于n个元素的排序问题，如果n=1，则不需要计算。 n=2时，只要进行一次比较就可以排名。 n=3的情况下比较3次即可，…。 如果n很大，问题就不那么容易处理了。 直接解决规模巨大的问题有时相当困难。
二、基本思想和战略分治法的设计思想是，把一个难以直接解决的大问题，分成规模不大的同一个问题，各自击破、分而治之。
分治策略是对于一个规模为n的问题，如果该问题容易解决则直接解决，否则分解为k个规模较小的子问题，这些子问题相互独立并以与原问题相同的形式递归求解，综合各子问题的解得到原问题的解。 这种算法设计策略称为分治法。
如果原问题可以分割成k个问题、1kn个问题，并且这些问题可以解决，并利用这些问题的解求出原问题的解，则这种分割统治法是可能的。 分治法产生的子问题往往是原问题的小模式，便于使用递归技术。 在这种情况下，通过反复应用分治的方法，可以使原问题和子问题的类型一致，但其规模继续缩小，最终可以缩小到容易直接求出其解的程度。 这自然会导致递归过程的发生。 分治和递归像孪生兄弟，往往同时应用于算法设计，从而产生许多高效算法。
三、分治法可以用场景分治法解决的问题一般具有以下特点：
1 )只要在一定程度上缩小这个问题的规模就很容易解决
2 )该问题可分解为几个规模较小的同一个问题。 即，该问题具有最优子结构的性质。
3 )利用该问题分解的子问题的解可以集成到该问题的解中；
4 )通过该问题分解的各部分问题相互独立。 也就是说，部分问题之间不包含共同的部分问题。
第一个特点是问题的计算复杂度一般随问题规模的增加而增加，因此大多数问题都能得到满足
第二条特征是应用分治法的前提，它也解决了很多问题，这一特征反映了递归思想的应用，
第三条的特征是关键，能否利用分治法取决于问题是否具有第三条的特征。 具有第一条和第二条特征而不具有第三条特征的，可以考虑使用贪婪法或动态规划法。
第四条的特点涉及分治法的效率。 在各问题不独立的情况下，分治法需要做很多不必要的工作，反复解决公共问题。 在这种情况下，可以使用分治法，但一般使用动态规划法较好。
四、分治法必须得到基本步骤
分治法在每层递归中有三个步骤。
step1分解：将原问题分解为几个规模小、相互独立、与原问题形式相同的子问题；
step2解决：子问题规模小，容易解决时直接解决。 否则，递归求解各子问题
step3合并：将各部分问题的解合并为原问题的解。
典型的算法设计模式如下。
Divide-and-Conquer
1. if |P|n0
2.thenreturn (即席
3 .把p分解成小的子问题P1，P2，Pk
4. for i1 to k
5.doyidivide-and-conquer(Pi )递归解决pi
6.tmerge(y1，y2，…，yk )并合子问题
7 .返回(t )。
其中|P|表示问题p的规模的n0是阈值，如果问题p的规模不超过n0，则表示问题可以简单直接解决，不需要进一步分解。 特殊是这个分割统治法中的基本的辅助算法，用于直接解决小规模的问题p。 因此，p的规模在n0以下时，直接用算法特定求解。 算法merge(y1，y2，yk )是同分支配法中的合并子算法，用于将p的部分问题P1，P2，Pk的相应解y1，y2，yk合并为p的解。
五.分治法的复杂性分析
一个分割统治法将规模为n的问题分为k个规模为n/m的子问题来求解。 分解临界值n0=1，特定解的规模为1的问题需要1个单位时间。 将元问题分解为k个问题，用merge将k个问题的解合并为元问题的解需要f(n )个单位时间。 如果用t(n )表示该分割统治法解决|P|=n的规模问题所需的计算时间，则为：
t(n )=kt ) n/m ) f ) n ) )。
用迭代法求方程的解：
递归方程及其解
只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。 六、可使用分治法求解的一些经典问题（1）二分搜索
二分搜索
（2）大整数乘法（3）Strassen矩阵乘法 （4）棋盘覆盖 （5）合并排序 （6）快速排序
（7）线性时间选择 （8）最接近点对问题 （9）循环赛日程表 （10）汉诺塔详解
在汉诺塔游戏中，有三个分别命名为A、B、C得塔座，几个大小各不相同，从小到大一次编号得圆盘，每个原盘中间有一个小孔。最初，所有得圆盘都在A塔座上，其中最大得圆盘在最下面，然后是第二大，以此类推.
游戏的目的是将所有的圆盘从塔座A移动到塔座B;塔座C用来防止临时圆盘,游戏的规则如下:
1、一次只能移动一个圆盘
2、任何时候都不能将一个较大的圆盘压在较小的圆盘上面.
3、除了第二条限制,任何塔座的最上面的圆盘都可以移动到其他塔座上.
汉诺塔问题解决思想:
在解决汉诺塔问题时,事实上,我们不是关心圆盘1开始应该挪到哪个塔座上,而是关心最下面的圆盘4.当然,我们不能直接移动圆盘4,但是圆盘4最终将从塔座A移动到塔座B.按照游戏规则,在移动圆盘4之前的情况一定如下图
我们仍将分析,如何将前三个圆盘从A移动到C,然后圆盘4从A移动到B,前三个圆盘从C再移动到B.
但是上面的步骤可以重复利用!例如将三个圆盘从A移动到C,那么应该先将前两个圆盘从A移动到B,然后将圆盘3从A移动到C,最后将前两个圆盘从B移动到C.
持续简化这个问题,最终我们将只需要处理一个圆盘从一个塔座移动到另一个塔座的问题.
我们先来想一下我们人类应该怎样操作吧。
我们每次操作都会这样问自己：我们需要将哪个柱子上的多少个盘子通过哪个柱子移动到哪个柱子上呢？
我们必须也只能用这么几个参数：
需要移动的盘子的总数，3个柱子。
所以函数头为：
void hanoi(int n, char x, char y, char z)其中，n代表盘子总数，x，y，z代表柱子
hanoi(n, x, y, z)的意思就是：将n个在x柱子上的盘子通过y这个柱子移动到z这个柱子上。
那不就完了！
hanoi(n, ‘A’, ‘B’, ‘C’)就是这道问题的答案！
那么这一步的前一步是什么？
记住了，在求解f(n, other variables)的时候，我们直接默认f(n - 1, other variables)已经完了就可以了！这个在前面已经解释过了，在此不再鳌述。
我们将n-1个盘子当作一个整体：这就是类似于分治求解子问题的思想
那么，前一步也就是f(n - 1, other variables)显然是先将n -1 个在A柱子上的盘子通过C柱移动到B柱上，再将在A柱子上的编号为n的盘子移动到C柱上，再将B柱子上的n-1个盘子通过A柱移动到C柱上
#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll N=1e5+7;const ll mod=1e9+7;ll cnt,n;void move(ll id,char from,char to){ printf ("step %lld: move %lld from %c->%cn", ++cnt, id, from, to);}void hanoi(ll n,char x,char y,char z){ if(n==0) return; hanoi(n-1,x,z,y);//把n-1个盘子全部从X经过z移动到y柱上 move(n,x,z);//偷偷把第n个盘子从x移动到z上 hanoi(n-1,y,x,z);//把n-1个盘子从y经过x移动到z柱上，结束}int main(){ cin>>n; hanoi(n,'A','B','C'); return 0;} 汉诺塔公式：ans=2n-1 牛牛的汉诺塔牛牛的汉诺塔
输入：
3
就是按照经典汉诺塔的写法写递归函数，然后再写一个结构体，巧妙地用数组把六种情况存起来即可
#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll N=1e5+7;const ll mod=1e9+7;ll cnt,n;struct node{ ll date[6]; node() { memset(date,0,sizeof date); } //a->b 0 //a->c 1 //b->a 2 //b->c 3 //c->a 4 //c->b 5};node dp[3][3][3][105];bool vis[3][3][3][105];node operator+(const node &a,const node &b){ node c; for(ll i=0;i<=5;++i) { c.date[i]=a.date[i]+b.date[i]; } return c;}void moveto(ll x,ll y,node &temp){ if(x==0&&y==1)++temp.date[0]; if(x==0&&y==2)++temp.date[1]; if(x==1&&y==0)++temp.date[2]; if(x==1&&y==2)++temp.date[3]; if(x==2&&y==0)++temp.date[4]; if(x==2&&y==1)++temp.date[5]; return;}node hanoi(ll a,ll b,ll c,ll n)//把a经过b移动到c柱上（第n个）{ if(vis[a][b][c][n])return dp[a][b][c][n]; if(n==1) { moveto(a,c,dp[a][b][c][n]); vis[a][b][c][n]=true;//标记一下 return dp[a][b][c][n]; } node temp;//普通的hanoi塔 temp=temp+hanoi(a,c,b,n-1);//先把n-1个从a经过c移动到b moveto(a,c,temp);//把第n个直接从a移动到c temp=temp+hanoi(b,a,c,n-1);//再把刚刚那n-1个从b经过a移动到c vis[a][b][c][n]=true;//完成！ return dp[a][b][c][n]=temp;}int main(){ cin>>n; node ans=hanoi(0,1,2,n); printf("A->B:%lldn",ans.date[0]); printf("A->C:%lldn",ans.date[1]); printf("B->A:%lldn",ans.date[2]); printf("B->C:%lldn",ans.date[3]); printf("C->A:%lldn",ans.date[4]); printf("C->B:%lldn",ans.date[5]); printf("SUM:%lldn",(ll(1)<<n)-1);//公式ans=2^n-1}注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧