分治算法详细讲解（含经典例题分析）

分治法思路：

将整个问题分解成若干小问题后再分而治之。如果分解得到的子问题相对来说还是太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。
分治算法可以由递归过程来表示，因为分治法就是一种找大规模问题与小规模问题关系的方法，是递归设计的一种具体策略。

步骤

1.分解
将原问题分解为若干规模较小，相互独立，与原问题相同的子问题。
2.解决
若干子问题较小而容易被解决则直接解决，否则再继续分解为更小的子问题，直到容易解决。
3.合并
将已求解的各个子问题的解，逐步合并为原问题的解。

有的问题分解后不需要合并子问题的解，此时就不需要再做第3步了。多数问题需要子问题的解，按照题意使用恰当的方法合并成为整个问题的解。需要具体问题具体分析。

算法框架

分治法的一般算法设计模式如下：

Divide-and-Conquer(int n){ 
    if(n<=n0){ 
   //n为问题规模 ,n0为可解子问题的规模 解子问题; return(子问题的解); } for(i=1;i<=k;i++){ 
   //分解成较小的子问题p1,p2,...,pk yi=Divide-and-Conquer(|Pi|);//递归解决 } T=MERGE(y1,y2,...yk);//合并子问题 return(T);//返回问题的解 } 

典型二分法

（一）

在算法设计中，每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。
二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。

问题：金块问题

老板有一袋金块（共n块），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块，假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。

方法1：逐个查找比较

最简单的方就是逐个的比较查找，算法类似于选择排序。先拿两块进行比较，留下最重的与下一块比较，直到全部比较完毕就找到了最重的金子

完整代码如下：

//金块算法1：逐个查找比较 #include 
     int main(){ 
    void maxmin(float a[],int n);//定义查找比较的函数 float a[5]={ 
   5,3,1,9,0}; int i; maxmin(a,5); return 0; } void maxmin(float a[],int n){ 
    float max,min; int i; int count=0; max=min=a[0]; for(i=1;i<n;i++){ 
    if(max<a[i]) { 
   //记录每次比较重量最大的金块 max=a[i]; count++; } if(min>a[i]){ 
   //记录每次比较重量最小的金块 min=a[i]; count++; } } printf("max=%.2f\nmin=%.2f\ncount=%d\n",max,min,count);//输出结果 } 

方法2：分治法（二分法）

1.将数据等分为两组（两组数据可能差1），目的是分别选取其中最大值（最小值）。
2.递归分解直到每组元素的个数不大于2，可简单的找到最大值（最小值）。
3.回溯时将分解的两组解大者取大，小者取小

用分治法可以用较少的比较次数解决问题。

完整代码如下：

//金块算法2:运用递归实现分半查询  #include 
     float a[5]={ 
   3,6,9,2,5}; int main(){ 
    void maxmin(int i,int j,float &fmax,float &fmin,int &count);//fmax的地址,fmin的地址  float fmax=0,fmin=0; int count=0; maxmin(0,4,fmax,fmin,count); //传递地址是为了能够把值带出来  printf("fmax=%f\nfmin=%f\ncount=%d\n",fmax,fmin,count); return 0; } void maxmin(int i,int j,float &fmax,float &fmin,int &count){ 
    int mid; int k; float lmax,lmin,rmax,rmin; count++; //递归结束条件(子问题的解) //当分到只剩一个数 if(i==j){ 
    fmax=a[i];fmin=a[i]; } else if(i==j-1){ 
   //(i,j为下标，在分解过程中,i总在左,j总在右 )假如只剩两个数  if(a[i]>a[j]){ 
    fmax=a[i]; fmin=a[j]; } else if(a[j]>a[i]){ 
    fmax=a[j]; fmin=a[i]; } } else{ 
   //其他情况（还剩很多数），则继续递归分解  mid=(i+j)/2;//继续分半 maxmin(i,mid,lmax,lmin); maxmin(mid+1,j,rmax,rmin); if(lmax>rmax) fmax=lmax; else fmax=rmax; if(lmin<rmin) fmin=rmin; else fmin=rmin; } } 

（二）二分法不相似情况

需要构造与原问题相似子问题。

问题：残缺棋盘
残缺棋盘是一个有2k*2k（k>0）个方格的棋盘，其中恰有一个方格残缺，其中残缺的方格用蓝色阴影表示。

解决：
以k=2为例（此时共有16个小方格），用二分法进行分解，得到的是由4个k=1的棋盘组成。

#include 
     using namespace std; int count=0; int size=1; int Board[8][8]; int main(){ 
    void Cover(int tr,int tc,int dr,int dc,int size);//填充棋盘的函数  void OutputBoard(int size); int x,y; int i; int k; //输入棋盘规模 cout<<"请确认棋盘规模，输入k大小（2k×2k）:"<<endl ; cin>>k; for(i=1;i<=k;i++) size=size*2; cout<<"请输入残缺棋子位置（行号，列号）:"<<endl; cin>>x>>y; Cover(0,0,x,y,size); OutputBoard(size); } void Cover(int tr,int tc,int dr,int dc,int size){ 
    if(size<2) return; int t=count++; int s=size/2; //如果残缺在左上角 if(dr<tr+s&&dc<tc+s){ 
    Cover(tr,tc,dr,dc,s); Board[tr+s-1][tc+s]=t; Board[tr+s][tc+s-1]=t; Board[tr+s][tc+s]=t; //返回，填充其他部分  Cover(tr,tc+s,tr+s-1,tc+s,s); Cover(tr+s,tc,tr+s,tc+s-1,s); Cover(tr+s,tc+s,tr+s,tc+s,s); } //右上角  else if(dr<tr+s&&dc>=tc+s) { 
    Cover(tr,tc+s,dr,dc,s); Board[tr+s-1][tc+s-1]=t; Board[tr+s][tc+s-1]=t; Board[tr+s][tc+s]=t; //返回，填充其他部分  Cover(tr,tc,tr+s-1,tc+s-1,s); Cover(tr+s,tc,tr+s,tc+s-1,s); Cover(tr+s,tc+s,tr+s,tc+s,s); } else if(dr>=tr+s&&dc<tc+s){ 
    Cover(tr+s,tc,dr,dc,s); Board[tr+s-1][tc+s-1]=t; Board[tr+s-1][tc+s]=t; Board[tr+s][tc+s]=t; //返回，填充其他部分  Cover(tr,tc,tr+s-1,tc+s-1,s); Cover(tr,tc+s,tr+s-1,tc+s,s); Cover(tr+s,tc+s,tr+s,tc+s,s); } else if(dr>=tr+s&&dc>=tc+s){ 
    Cover(tr+s,tc+s,dr,dc,s); Board[tr+s-1][tc+s-1]=t; Board[tr+s-1][tc+s]=t; Board[tr+s][tc+s-1]=t; //返回，填充其他部分  Cover(tr,tc,tr+s-1,tc+s-1,s); Cover(tr,tc+s,tr+s-1,tc+s,s); Cover(tr+s,tc,tr+s,tc+s-1,s); } } void OutputBoard(int size){ 
   //输出棋盘的内容 for(int i=0;i<size;i++){ 
    for(int j=0;j<size;j++){ 
    cout<<Board[i][j]; } cout<<endl; } } 

（三）二分法不独立情况

上面的例题，经过二分法分解或经过简单处理后，就得到了相似且相互独立的子问题。对于分解后不独立的情况，主要表现在子问题之间包含公共子问题。
问题：求数列的最大字段和
给定n个元素的整数列（可能为负整数）(斜体标注的都为下标)
a1,a2,…,an.
求形如:ai,ai+1,…aj(i/j=1…n,i<=j)的子段
使其和为最大。当所有整数为负整数时定义其最大字段和为0。
例如当（a1,a2,a3,a4,a5,a6）=(-2,11,-1,13,-5,-2)
最大字段和为i=2,j=4(下标从1开始).
解决：
用二分法将数据分为两组，找出两个子问题的解，两个子问题的解不能简单地得到原问题的解，因为两个子问题的中间还有公共子问题，也就是说两个子问题不能真正的分开。此时再想使用二分法，则需要对公共子问题单独处理。
代码思路：
使用二分法将原问题分解，虽然分解得到的子问题并不相互独立，但是对公共子问题进行单独的处理。
将原问题分解成三部分
（从中间分开）
左边部分
右边部分

#include 
     int len=5; int main(){ 
    double max_sum(double a[],int left,int right);//left,right是数组下标范围 这是一个递归函数 double max=0; double a[5]={ 
   -1,-2,0,3,6}; max=max_sum(a,1,5); printf("%.2f\n",max); return 0; } double max_sum(double a[],int left,int right){ 
    int i; double s1=0,s2=0;//中间部分左边为s1,中间部分右边为s2  double lefts=0,rights=0;//临时变量标示左边部分的和，和右边部分的和  double left_sum=0; double right_sum=0; double center_sum=0; if(left==right){ 
   //如果这个数为正数就返回，如果为负数就返回0  if(a[left]>0) return (a[left]); else return (0); } else{ 
    //递归求左边部分和右边部分最大和 int center=(left+right)/2; left_sum=max_sum(a,left,center); right_sum=max_sum(a,center+1,right); //对公共子问题进行单独求解 //求中间部分最大和 for(i=0;i<center;i++){ 
    lefts=lefts+a[center-i]; if(lefts>s1) s1=lefts; rights=rights+a[center+i+1]; if(rights>s2) s2=rights; } center_sum=s1+s2; //比较三部分大小 if(left_sum>right_sum){ 
    if(left_sum>center_sum) return (left_sum); else return (center_sum); } else{ 
    if(right_sum>center_sum) return (right_sum); else return (center_sum); } } } 

非等分分治

问题：选择第k小的数
对于给定的n个元素的数组a[0,n-1],要求从中找出第k小的数。
解决：
通过改写快速排序算法来解决选择问题。
（快速排序算法回忆：首先选择第一个数作为分界数据，将比它小的数据存储在它的左边，将比它大的数据存储在它的右边，它存储在左右两个子集中间。这样左右两个子集就是原问题分解后的独立子问题，再用同样的方法解决这些子问题，直到每个数据只有一个数据，就自然有序了，也就完成了全部数据的排序工作。）
代码思路：
一趟排序中分解出的左子集中元素个数nleft，有以下几种情况：
1. nleft=k-1，则分界数据就是选择问题的答案。
2. nleft>k-1,则选择问题的答案在左子集中找，问题规模变小了。
3. 则选择问题的答案在右子集中找，问题变为寻找第k-nleft-1小的数了，问题规模变小了。（因为随着子区间下标不同，k这个答案下标也会变化）

#include 
     #include 
     #include 
     void swap(int a[],int x,int y);//交换函数 int main(){ 
    //比较两种算法的时间复杂度 //快速排序算法函数 int a[7]={ 
   -1,3,-2,7,6,0,9}; int len=7;//数组长度  int k; int n=20,i=0; double time; int num; clock_t start,end; void kuaisupaixu(int a[],int left,int right); //非等分分治算法 int feidengfenfenzhi(int a[],int len,int k); //输入k  printf("查找数组中第k小的数，请输入k（0~7）:"); scanf("%d",&k); /*------------------------------*/ //调用快速排序算法  start=clock(); for(;i<n;i++){ 
    kuaisupaixu(a,0,len-1);//一次运行时间太短，运行100次取平均值  } end=clock(); time=(double)(end-start)/CLOCKS_PER_SEC/n; printf("您要查找的第k小的元素为:%d\n",a[k-1]); printf("函数调用时间为：%.30lf\n",time); /*------------------------------*/ //调用非等分分治  start=clock(); for(;i<n;i++){ 
    num=feidengfenfenzhi(a,len,k); } end=clock(); time=(double)(end-start)/CLOCKS_PER_SEC/n; printf("您要查找的第k小的元素为:%d\n",num); printf("函数调用时间为：%.30lf\n",time); /*------------------------------*/ return 0; } void kuaisupaixu(int a[],int left,int right){ 
    int temp=a[left];//把第一个变量设置为分界变量  int i=left;//左指针赋初值  int j=right;//右指针赋初值  if(left==right){ 
    return; } if(left==right-1){ 
    if(a[left]>a[right]) swap(a,left,right); return; } //把比分界变量小的数放前面，把比分界变量大的数放在后面 (利用递归把数从小到大排列) //实现一次排序  while(1&&j>=left&&i<=right){ 
    //右边扫描 (找出小于分界变量的数 ) while(a[j]>=temp&&j>=left){ 
    if(j>i) j=j-1; else break; } //左边扫描(找出大于分界变量的数 ) while(a[i]<=temp&&i<=right){ 
    if(i==j) break; else i=i+1; } if(i==j){ 
   //每轮探测以i==j结束  swap(a,i,left); break; } if(i>=j){ 
    break; } swap(a,i,j); } //左边递归 if(i!=left){ 
    digui(left,i-1); } //右边递归 if(i!=right){ 
    digui(i+1,right); } } int feidengfenfenzhi(int a[],int len,int k){ 
    int digui(int a[],int left,int right,int k); int i; if(k<0||k>=len){ 
    printf("您查找的数字不在数组中！\n"); } else{ 
    return digui(a,0,len-1,k); } } int digui(int a[],int left,int right,int k){ 
    //利用快速排序思路，找到一个基准数（选第一个），小于基准数的放左边，大于基准数的放右边  int i,j; int p; int temp; if(left>=right) return a[left]; i=left,j=right+1;//指定左右指针（因为用do while循环所以j先加一）  temp=a[left];//指定基准数 //把小数放前面，大数放后面（从小到大排列）  //右边循环 //指针指向小于基准数的下标，等待交换  while(1){ 
    do{ 
    i=i+1; }while(a[i]<temp);//指针向后移动，直到碰到大于temp的数  do{ 
    j=j-1; }while(a[j]>temp); //指针向前移动，直到碰到小于temp的数  //左边循环  //指针指向大于基准数的下标，等待交换  if(i>=j) break; swap(a,i,j); } //从循环里出来的时候i==j,且以此时指针指向的数为分界点，划分新的区间进行递归  if(j-left+1==k) { 
    return temp; } a[left]=a[j]; a[j]=temp; if(j-left+1<k){ 
   //查找的数在右边  return digui(a,j+1,right,k-j-1+left);//k的值改变  } else{ 
   //查找的数在左边 return digui(a,left,j-1,k); } } void swap(int a[],int x,int y){ 
   //传入的x,y为下标  int t;//借助额外变量实现两个数的交换  t=a[x]; a[x]=a[y]; a[y]=t; } 

最后

原创不易，如果对您有帮助，请点个赞再走呀（づ￣3￣）づ╭❤ ～拜托啦