1. 前言

   所谓分治算法就是指分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称为二分法。

   比如，我们玩过最简单的猜数游戏，一开始，对方先想一个1000以内的正整数，然后你给出一个数x。对方只要回答“比x大”或者“比x小”或者“猜中”。

   开始猜测是1到1000之间，你可以先猜500。运气好的一次猜中，如果比500大，显然结果不是1到500之间，那么下一次就猜501到1000。如果比500下，那么下次就猜1到499。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。这样不超过10次询问区间就可以缩小为1，答案就会猜中了，这就是二分的基本思想。

2. 基本思想及策略

   分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

    分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

     如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法适用的情况

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

应用

（1）二分搜索

 （11）一元三次方程求解

快速排序：

void qsort(int left, int right){  	int i=left; j =right;  	mid=a[left+right]/2;  	while(i<=j){  		while(a[i]<mid) i++;   		while(a[j>mid]) j--;  		if(i<=j){  			swap(a[i],a[j]);  			i++;  			j--;  		}  	}  	if(left<j) qsort(left,j);  	if(i<right) qsort(i,right);  }

一元三次方程求解：

描述

有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。

给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。

输入

一行，包含四个实数a，b，c，d，相邻两个数之间用单个空格隔开。

输出

一行，包含三个实数，为该方程的三个实根，按从小到大顺序排列，相邻两个数之间用单个空格隔开，精确到小数点后2位。

样例输入

1.0 -5.0 -4.0 20.0

样例输出

-2.00 2.00 5.00

方法一：枚举法，枚举每一个解看是否成立。

#include<cstdio>  #include<cmath>  #include<cstdlib>  using namespace std;  double a,b,c,d;  int main()  {      double x;      scanf("%lf%lf%lf%lf",&a,&b,&c,&d);      for (x=-100;x<=100;x+=0.01)      {          if (abs(a*x*x*x+b*x*x+c*x+d)<=0.00001)              printf("%.2f ",x);      }  }

方法二：分治法，枚举区间，看解存在于哪个区间里，逐渐缩小区间范围，确定解。

#include<cstdio>  #include<cmath>  #include<cstdlib>  using namespace std;  double a,b,c,d;  double f(double x)  {      return a*x*x*x+b*x*x+c*x+d;  }  int main()  {      double x,x1,x2,xx;      scanf("%lf%lf%lf%lf",&a,&b,&c,&d);      for (x=-100;x<=100;x+=1)      {           x1=x;x2=x+1;          if (f(x1)==0) printf("%.2f ",x1);              else if (f(x1)*f(x2)<0)              {                  while (x2-x1>=0.001)                  {                      xx=(x1+x2)/2;                      if ((f(x1)*f(xx))<=0)                          x2=xx;                      else x1=xx;                  }                  printf("%.2f ",x1);              }      }  }

(adsbygoogle = window.adsbygoogle || []).push({});