设计原理
1.分治法的基本思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
通常，这种分析方法的基本点在于“分解”，因此这种方法也被称为“划分(Divide)和解决(Con—quer)”方法。也正因为如此，它和语言工具中的递归结下了不解之缘。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
2.分治法的适用条件
分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
3.分治法的基本步骤
分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下： 
DividAndConquer(p(n))//分治法设计原理
{
    if (n <= n0)
        return Adhoc(p(n));
    else
    {
        //将P分解为较小的子问题P1、P2、…、Pk
        Divide p int o smaller subinstances P1, P2, ..., Pk; 
        for (i=1; i<=k; i++)
            yi = DividAndConquer(pi);//递归解决Pi
        return Merge(y1, y2, ..., yk);//合并子问题 
    }
}　　
其中 p(n)表示一个规模为n的问题P， 可以把它分解成k个规模较小的子问题，这些问题相互独立，并且与原来的问题结构相同。在解决这些子问题时，又用相同的方式对每一个子问题进行进一步的分解，直到某个阈值n0为止。递归的解这些子问题，再把各个子问题的解合并起来，就得到原来问题的解。这就是分治法的思想方法。n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。Adhoc(p(n))是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法Adhoc(p(n))求解。 
　　算法Merge(y1, y2, ..., yk)是该分治法中的合并子算法，用于将P的子问题P1、P2、…、Pk的相应的解y1、y2、…、yk合并为P的解。 
　　根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。

经典示例
例1  最大最小问题：老板有一袋金块，共n块。将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重和最轻的金块。
算法分析：这个问题可以转化一个具有n个元素的数组里，寻找最大和最小元素问题。
一般算法是遍历数组，依次将每个元素和当前最大，最小值判断，直至遍历数组结束，返回最大，最小值。
void MaxMin(int a[], int n, int *max, int *min)
{
    int i = 0;
    
    *max = *min = a[0];
    for (i=1; i<n; i++)
    {
        if (a[i] < *min)
            *min = a[i];
        if (a[i] > *max)
            *max = a[i];
    }
}
很清楚，在输入规模为n时，这个算法所执行的元素比较次数是2n-2。用分治法可以较少比较次数地解决上述问题：
如果集合中只有1个元素，则它既是最大值也是最小值；
如果有2个元素，则一次Max(i,j)，一次Min(i,j)就可以得到最大值和最小值； 
如果有多于2个元素，则把集合分成两个规模相当子集合，递归的应用这个算法分别求出两个子集合的最大值和最小值，最后让子集合1的最大值跟子集合2的最大值比较得到整个集合的最大值；让子集合1的最小值跟子集合2的最小值比较得到整个集合的最小值。
void MaxMin2(int a[], int left, int right, int *max, int *min)
{
    int x1, x2, y1, y2;
    int mid;
    
    if ((right-left) <= 1)//相等或相邻
    {
        if (a[right] > a[left])
        {
            *max = a[right];
            *min = a[left];
        }
        else
        {
            *max = a[left];
            *min = a[right];
        }
    }
    else
    {
        mid = (left + right) / 2;
        MaxMin2(a, left, mid, &x1, &y1);// 把数组分成两个规模相当子数组递归
        MaxMin2(a, mid+1, right, &x2, &y2);
        *max = (x1 > x2) ? x1 : x2;
        *min = (y1 < y2) ? y1 : y2;
    }
}
使用分治法法后可以把元素比较次数从原来的2n-2减少为（3n/2）- 2。

例2  二分法求方程近似解：求方程f(x) = x^3 + x^2 - 1 = 0在[0,1]上的近似解，精确度为0.01。
算法分析：二分法求方程近似解的基本思想：将方程的有解区间平分为两个小区间，然后判断解在哪个小区间；继续把有解的区间一分为二进行判断，如此周而复始，直到求出满足精确要求的近似解。
二分法求方程近似解的算法步骤：
⑴确定区间[a,b]，验证f(a).f(b) < 0，给定精确度e
⑵求区间(a, b)的中点mid
⑶计算f(mid)
若f(mid) = 0，则mid就是函数的零点
若f(a).f(mid) < 0，则令b = mid(此时零点a < x0 < mid)
若f(mid).f(b) < 0，则令a = mid(此时零点mid < x0 < b)
⑷判断是否达到精确度e：即若|a-b| < e，则得到零点近似值a（或b）；否则重复⑵-⑷。
代码如下：
double F(double a, double b, double c, double d, double x)//函数表达式 
{
    return (((a * x + b) * x) * x + d) / c;
}

double Function(double a, double b, double c, double d, double low, double high, double e)
{
    double mid = (low + high) / 2;
    if (F(a, b, c, d, mid) == 0)
        return mid; 
    
    while ((high-low) >= e)
    {
        mid = (low + high) / 2;
        if (F(a, b, c, d, mid) == 0)
            return mid; 
        if (F(a, b, c, d, low)*F(a, b, c, d, mid) < 0)
            high = mid;
        else
            low = mid;
    }
    return low;
}

例3  二分法插入排序：插入排序是经典的简单排序法，它的时间复杂度最坏为O（n^2）。代码如下：
//插入法对数组进行排序，从第二个元素开始，依次把元素插入到其左边比其小的元素之后
void InsertSort(int a[], int len)
{
    int i, j, temp;
    
    for (i=1; i<len; i++)//从第二个元素开始，依次从左向右判断
    {
        temp = a[i]; //记录当前被判断的元素 
        j = i - 1;
        while (j >= 0 && a[j] > temp)//把比temp大的元素向后移动一个位置 
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;//把temp插入到适当位置 
    }
}
插入算法的原理是总是使得当前被插入的元素左侧的数组是已经排好序的。在上面的算法中我们是采用遍历a[i] 左侧数组的方法来查找插入位置，而实际上我们完全可以根据二分查找的原理，来实现二分法插入排序。
算法思想简单描述：在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到low > high，然后再把第i个元素前与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。代码如下：
void HalfInsertSort(int a[], int len)
{
      int i, j;
      int low, high, mid;
      int temp;
      for (i=1; i<len; i++)
      {
            temp = a[i];
            low = 0;
            high = i - 1;
            while (low <= high) //在a[low。。。high]中折半查找有序插入的位置
            {
                  mid = (low + high) / 2;
                  if (a[mid] > temp)
                        high = mid - 1;
                  else
                        low = mid + 1;
            } //while

            for (j=i-1; j>high; j--)//元素后移
                  a[j+1] = a[j];
            a[high+1] = temp; //插入
      }//for
}
排序的算法很多，其中多数都要用到分治的思想，如希尔排序，合并排序和快速排序等，这里不再一一叙述，感兴趣的读者可以到我的BLOG查看：
http://blog.programfan.com/blog.asp?blogid=96&columnid=2071

例4  找出伪币：给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。但是很明显，这样的效率实在太低，请设计一种方法，使得比较的次数最少。
算法分析：利用分而治之方法。假如把16硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把16个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先16个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这16个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。
现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题，注意如果只有一个硬币，那么不能判断出它是否就是伪币。（在本题中n= 2^4，所以不可能出现一个或三个硬币一组的情况）在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，16硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。
/*
函数功能：找出伪币，并返回其下标，若无伪币则返回-1，要求硬币的总数为2^n 
输入变量： int a[]，  数组a中存储各硬币的重量
           int left,  数组a的左边界     
           int right, 数组a的右边界     
输出变量：无 
返回值： int，伪币下标，若无伪币则返回-1
*/ 
int FalseCoin(int a[], int left, int right)
{
    int mid = (left + right) / 2;
    int sum1 = 0, sum2 = 0;
    int i;
    
    if ((right-left) == 1)//只有两枚硬币，轻者为伪币，等重则无伪币  
        return (a[left] < a[right]) ? left : (a[left] > a[right]) ? right : -1;

    //多于两枚硬币，将数组分成两半，分而治之 
    for (i=left; i<=mid; i++)
        sum1 += a[i];
    for (i=mid+1; i<=right; i++)
        sum2 += a[i];    
    
    if (sum1 == sum2)//等重则无伪币
        return -1;
    else if (sum1 < sum2)
        return FalseCoin(a, left, mid);
    else 
        return FalseCoin(a, mid+1, right); 
}
在上述算法中我们每次把硬币分成两组，解决16个硬币问题，需要比较的次数为4次。如果我们每次把硬币分成4组，需要的平均比较次数会减少为3次。代码如下；   
/*
函数功能：找出伪币，并返回其下标，若无伪币则返回-1。要求硬币的总数为2^n 
输入变量： int a[]，  数组a中存储各硬币的重量
           int len,  总数组的长度，即总的硬币数量 
           int left,  数组a的左边界     
           int right, 数组a的右边界     
输出变量：无 
返回值： int，伪币下标，若无伪币则返回-1
*/ 
int FalseCoin(int a[], int len, int left, int right)
{
    int left1, right1, left2, right2, left3, right3, left4, right4;
    int sum1, sum2, sum3, sum4;
    int q, i; 
    
    if (right == left)//如果子数组只有一枚硬币，将其与相邻的硬币比较 
    {
        if (left > 0)
            return (a[left]<a[left-1]) ? left : (a[left]>a[left-1]) ? left-1 : -1;
        if (right < len-1)
            return (a[right]<a[right+1]) ? right : (a[right]>a[right+1]) ? right-1 : -1;
        return -1;   
    } 
    if ((right-left) == 1)//如果子数组只有两枚硬币，轻者为伪币，等重则无伪币  
    {
        return (a[left] < a[right]) ? left : (a[left] > a[right]) ? right : -1;
    }
        
    //将硬币分成4等份
    q = (right - left + 1) / 4;
    left1 = left;
    right1 = left1 + q - 1; 
    left2 = right1 + 1;
    right2 = left2 + q - 1; 
    left3 = right2 + 1;
    right3 = left3 + q - 1; 
    left4 = right3 + 1;
    right4 = left4 + q - 1; 

    //累计每组硬币的重量 
    sum1 = sum2 = sum3 = sum4 = 0;
    for (i=left1; i<=right1; i++)
        sum1 += a[i];
    for (i=left2; i<=right2; i++)
        sum2 += a[i];  
    for (i=left3; i<=right3; i++)
        sum3 += a[i];
    for (i=left4; i<=right4; i++)
        sum4 += a[i];  

    //将硬币两两比较  
    if (sum1 != sum2)//伪币在第1，2组硬币中
    {
        if (sum1 < sum2)
            return FalseCoin(a, len, left1, right1);
        else
            return FalseCoin(a, len, left2, right2);
    } 
    if (sum3 != sum4)//伪币在第3，4组硬币中
    {
        if (sum3 < sum4)
            return FalseCoin(a, len, left3, right3);
        else
            return FalseCoin(a, len, left4, right4);
    }
}

例5  比赛安排（1996年全国青少年信息学（计算机）奥林匹克分区联赛高中组复赛试题）
设有2^n（n<=6）个球队进行单循环比赛，计划在2^n-1天内完成，每个队每天进行一场比赛，设计一个比赛安排，使在2^n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为：
队    1    2    3    4    时间
比赛    1 – 2    3 – 4    第一天
    1 – 3    2 – 4    第二天
    1 – 4    2 – 3    第三天
分析：已知参加比赛的球队数x(x=2^n)，要设计一个比赛安排表。分析题目要求（单循环比赛的比赛规则），我们可以归纳出比赛安排表必须满足的条件：
①球赛需要在x-1天内完成。
②每个球队每天有且只能有一场比赛。
③任意两个球队必须进行过一场比赛，并且只能进行一场比赛。
当只有两个球队进行比赛时，比赛安排表的设计非常简单，只要让两个球队直接进行一场比赛就可以了。当不止两个球队时，我们可以将所有的球队分成两半。x个球队的比赛安排表就可以通过x/2个球队的比赛安排表来产生。这样递归地使用这种一分为二的方法对球队进行分割，直到只剩下两个球队。
日期\球队    1    2    3    4    5    6    7    8
2    2    1    4    3    6    5    8    7
3    3    4    1    2    7    8    5    6
4    4    3    2    1    8    7    6    5
5    5    6    7    8    1    2    3    4
6    6    5    8    7    2    1    4    3
7    7    8    5    6    3    4    1    2
8    8    7    6    5    4    3    2    1
如图，是一张8个球队的比赛安排表。其中第i行与第j列相交的数字a(i,j)表示第j个球队在第i-1天所遇到的对手。（表的第一行为8个球队的编号）如果用a(i1..i2,j1..j2)表示表中从第i1行到第i2行与从第j1列到第j2列相交的部分，那么，这张8×8的表a(1..8,1..8)可以分成左上角a(1..4,1..4)、右上角a(1..4,5..8)、左下角a(5..8,1..4)和右下角a(5..8,5..8)四个部分。仔细分析这四个部分，我们会发现：右下角a(5..8,5..8)和左上角a(1..4,1..4)完全相同；左下角a(5..8,1..4)和右上角a(1..4,5..8)完全相同。再继续分析每一个部分，都具有同样的规律。比如左上角a(1..4,1..4)，我们又可以把它分成a(1..2,1..2)、a(1..2,3..4)、a(3..4,1..2)和a(3..4,3..4)四个部分，并且a(3..4,3..4)和a(1..2,1..2)完全相同， a(3..4,1..2)和a(1..2,3..4)完全相同。
根据上面分析出来的规律，使用分治算法的思想，我们要设计一张8×8的比赛安排表a(1..8,1..8)，只需要设计出表的上半部分，即两张4×4的安排表a(1..4,1..4)和a(1..4,5..8)即可。之后，通过已经设计出来的表的左上角a(1..4,1..4)复制出表的右下角a(5..8,5..8)，通过右上角a(1..4,5..8)复制出表的左下角a(5..8,1..4)。即一张8×8的比赛安排表a(1..8,1..8)，可以通过两张4×4的比赛安排表a(1..4,1..4)和a(1..4,5..8)产生。同样，4×4的比赛安排表a(1..4,1..4)，可以通过两张2×2的比赛安排表a(1..2,1..2)和a(1..2,3..4)产生；a(1..4,5..8)可以通过a(1..2,5..6)和a(1..2,7..8)产生。
分解到最后，a(1,1)、a(1,2)、……、a(1,8)都是单独的一个数字，分别为8个球队的编号1、2、……、8，即这张8×8的比赛安排表的第一行。
如何将a(1,1)、a(1,2)、……、a(1,8)这8个数字合并 成一张完整的比赛安排表（原问题的解）呢？我们可以将整个合并过程分成三个阶段：
第一阶段，将这8个已知的数字（可以看成8张1×1的比赛安排表）合并成4张2×2的比赛安排表。这一阶段需要进行4次合并操作：①将a(1,1)和a(1,2)合并成a(1..2,1..2)；②将a(1,3)和a(1,4)合并成a(1..2,3..4)；③将a(1,5)和a(1,6)合并成a(1..2,5..6)；④将a(1,7)和a(1,8)合并成a(1..2,7..8)。这一阶段产生表的前两行。
第二阶段，将表的第一二行（可以看成4张2×2的比赛安排表）合并成两张4×4的比赛安排表。这一阶段需要进行两次合并操作：①将a(1..2,1..2)和a(1..2,3..4)合并成a(1..4,1..4)；②将a(1..2,5..6)和a(1..2,7..8)合并成a(1..4,5..8)。这一阶段产生表的前四行。
第三阶段，将表的前四行（可以看成2张4×4的比赛安排表）合并成一张8×8的比赛安排表。这一阶段只需要进行一次合并操作：将a(1..4,1..4)和a(1..4,5..8)合并成a(1..8,1..8)。这一阶段将产生一张完整的比赛安排表。
#include<stdio.h>
#define MAX 64

void Arrange(int a[][MAX], int n, int left, int right);

int main()
{
    int a[MAX][MAX] = {0};
    int i, j, n = 8;

    for (i=0; i<n; ++i)//先确定第1行：球队的编号 
        a[0][i] = i + 1;
        
    Arrange(a, n, 0, n-1);//递归产生各个方阵
    
    for (i=0; i<n; i++)
    {
        for (j=0; j<n; j++)
            printf("%3d", a[i][j]);
        printf("\n");
    }

    getchar();
    return 0;       
}

/*
函数功能：比赛安排，为n（=2^k）个球队安排比赛，使在n-1天内每个队都与不同的对手比赛 
输入变量： int a[][MAX]，  数组a中存储各球队的比赛情况 
           int n,  球队的数量，也即方阵的大小 
           int left,  数组a的左边界     
           int right, 数组a的右边界     
输出变量：int a[][MAX]，  数组a中存储各球队的比赛情况
返回值： 无 
*/ 
void Arrange(int a[][MAX], int n, int left, int right)//递归产生各个方阵
{
    if (n < 2)//球队数量少于2，不做任何操作 
        return;
        
    int i, j;
    int mid = (left+right)/2;//把方阵分成两半   
    n /= 2;
    
    Arrange(a, n, left, mid);//递归处理左上角方阵 
    Arrange(a, n, mid+1, right);//递归处理右上角方阵 
    
    for (i=0; i<n; i++)
    {
        for (j=left; j<=mid; j++)//已经得到方阵的左上角，则由左上角推出右下角   
{
            a[i+n][j+n] = a[i][j];
        }
        for (j=mid+1; j<=right; j++)//已经得到方阵的右上角，则由右上角推出左下角
        {
            a[i+n][j-n] = a[i][j];
        }
    }
}
也可以写成非递归的方式：
/*
函数功能：比赛安排，为n（=2^k）个球队安排比赛，使在n-1天内每个队都与不同的对手比赛 
输入变量： int a[][MAX]，  数组a中存储各球队的比赛情况 
           int max,  球队的数量，也即方阵的大小 
输出变量：int a[][MAX]，  数组a中存储各球队的比赛情况
返回值： 无 
*/ 
void Arrange(int a[][MAX], int max)
{
    int i, j, k, n, left, right, mid;
    
    for (i=0; i<max; ++i)//先确定第1行：球队的编号 
        a[0][i] = i + 1;
        
    for (n=2; n<=max; n*=2)//依次安排2，4，8。。。个球队 
    {
        for (left=0; left<max-1; left+=n)//当前被安排的球队的左边界 
        {
            right = left + n - 1;//当前被安排的球队的右边界
            mid = (left + right) / 2;
            k = n / 2;//将球队分成左右两半处理，每半有k个球队 
            for (i=0; i<k; i++)
            {
                for (j=left; j<=mid; j++)//由左上角推出右下角
                {
                    a[i+k][j+k] = a[i][j];
                }
                for (j=mid+1; j<=right; j++)//由右上角推出左下角
                {
                    a[i+k][j-k] = a[i][j];
                }
            }
        }
    }
}

练习
1．    计算x的N次方(N>=0)。


2．元三次方程求解(noip2001tg)
问题描述  有形如：ax3+bx2+cx+d=0  这样的一个一元三次方程。给出该方程中各项的系数
(a，b，c，d  均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，
且根与根之差的绝对值>=1。
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后5位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*(x2)<0，则在(x1，x2)之间一定有一个根。
样例
输入：1   -5   -4   20
输出：-2.00   2.00   5.00


3．例4的分而治之算法扩充到n> 1个硬币的情形。需要进行多少次重量的比较？

参考程序
1．常规算法，复杂度为O(N):
double Power(double x, unsigned int N)
{
    double result = 1.0;
    for (unsigned int i=0; i<N; i++)
        result *= x;
    return result;
}
折半算法（二分法），复杂度为O(logN):
double Power(double x, unsigned int N)
{
    if (N == 0)
        return 1.0;
        
    double t = Power(x, N/2);
    if (N % 2 == 0)
        return t * t;
    else
        return t * t * x;
}
2．算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。
由题意知（i,i+1）中若有根，则只有一个根，我们枚举根的值域中的每一个整数x(-100≤x≤100),设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若：
⑴f(x1)=0，则确定x1为f(x)的根；
⑵f(x1)*f(x2)<0，则确定根x在区间[x1，x2]内。
⑶f(x1)*f(x2)>0，则确定根x不在区间[x1，x2]内，设定[x2，x2+1]为下一个搜索区间；
若确定根x在区间[x1，x2]内，采用二分法，将区间[x1，x2]分成左右两个子区间：
左子区间[x1，x]和右子区间[x，x2]（其中x=（x1+x2）/2）。如果f(x1)*f(x)≤0，
则确定根在左区间[x1，x]内，将x设为该区间的右界值（x2=x），继续对左区间进行对分；
否则确定根在右区间[x，x2]内，将x设为该区间的左界值（x1=x），继续对右区间进行对分；
上述对分过程一直进行到区间的间距满足精度要求为止（即x2-x1<0.000005）。此时确定x1为f(x)的根。
#include<stdio.h>
#include<stdlib.h>

void Function(double xa[], double a, double b, double c, double d, double left, double right, double e);//解方程 
double F(double a, double b, double c, double d, double x);//函数表达式 

int main()
{
    double low = -100, high = 100;
    double e = 0.000005;
    double a = 1, b = -5, c = -4, d = 20;
    double x[8] = {0};
 
    printf("%f  %f  %f  %f\n", a, b, c, d);
    
    Function(x, a, b, c, d, low, high, e);//解方程
    
    printf("%.5f  %.5f  %.5f\n", x[0], x[1], x[2]);
    
    system("pause");
    return 0;       
}
double F(double a, double b, double c, double d, double x)//函数表达式 
{
    return ((a * x + b) * x + c) * x + d;
}

void Function(double xa[], double a, double b, double c, double d, double left, double right, double e)
{
    double low, high, mid, i;
    int top = 0;
    
    for (i=left; i<right; i+=1)
    {
        low = i;
        high = low + 1;
        while ((high-low) >= e)
        {
            mid = (low + high) / 2;
            if (F(a, b, c, d, mid) == 0)
            {
                xa[top++] = mid;
                break;
            }
            if (F(a, b, c, d, low)*F(a, b, c, d, mid) <= 0)
                high = mid;
            else if (F(a, b, c, d, mid)*F(a, b, c, d, high) <= 0)
                low = mid;
            else 
                break;
        }
        if ((high-low) < e)
            xa[top++] = low; 
        if (top > 1 && abs(xa[top-1] - xa[top-2]) < e)//消除重复的解 
            top--;
    }
}

3．分成两组：
#include<stdio.h>

int count = 0;

int FalseCoin(int a[], int left, int right);

int main()
{
    int a[60] = {0};
    int i, n = 15;
    
    for (i=0; i<=n; i++)
    {
        count = 0;
        a[i] = -1;
        printf("n = %d, count = %d\n", FalseCoin(a, 0, n), count);
        a[i] = 0;
    }

    getchar();
    return 0;       
}
/*
函数功能：找出伪币，并返回其下标，若无伪币则返回-1。此算法适用于任何情况，且伪币越靠前，越容易找到 
输入变量： int a[]，  数组a中存储各硬币的重量
           int left,  数组a的左边界     
           int right, 数组a的右边界     
输出变量：无 
返回值： int，伪币下标，若无伪币则返回-1
*/ 
int FalseCoin(int a[], int left, int right)
{
    int mid = (left + right) / 2;
    int num;
    
    if (left >= right)//如果只有一枚硬币，无法找出伪币，相当于无伪币 
    {
        count++;
        return -1;
    }    
    if ((right-left) == 1)//只有两枚硬币，轻者为伪币，等重则无伪币  
    {
        count++;
        return (a[left] < a[right]) ? left : (a[left] > a[right]) ? right : -1;
    }
        
    if ((right-left) == 2)//如果只有三枚硬币，轻者为伪币，等重则无伪币 
    {
        count++;
        if (a[left] < a[left+1])
            return left;
        else if (a[left] > a[left+1])
            return left + 1;
        else if (a[right] < a[left])
            return right;
        else
            return -1;
    }
    //多余三枚硬币，将数组分成两半，分而治之 
    num = FalseCoin(a, left, mid);
    if (num != -1)//找到伪币，直接返回 
        return num;
    else //否则查找另一半 
        return FalseCoin(a, mid+1, right);   
}
分成4组：
int FalseCoin(int a[], int len, int left, int right)
{
    int left1, right1, left2, right2, left3, right3, left4, right4;
    int sum1, sum2, sum3, sum4;
    int q, i; 
    
    if (left > right)//如果子数组没有硬币 
    {
        return -1;
    }   
    if (right == left)//如果子数组只有一枚硬币，将其与相邻的硬币比较
    {
        if (left > 0)
            return (a[left]<a[left-1]) ? left : (a[left]>a[left-1]) ? left-1 : -1;
        if (right < len-1)
            return (a[right]<a[right+1]) ? right : (a[right]>a[right+1]) ? right-1 : -1;
        return -1;   
    } 
    if ((right-left) == 1)//只有两枚硬币，轻者为伪币，等重则无伪币  
    {
        count++;
        return (a[left] < a[right]) ? left : (a[left] > a[right]) ? right : -1;
    }
        
    if ((right-left) == 2)//如果只有三枚硬币，轻者为伪币，等重则无伪币 
    {
        count++;
        if (a[left] < a[left+1])
            return left;
        else if (a[left] > a[left+1])
            return left + 1;
        else if (a[right] < a[left])
            return right;
        else
            return -1;
    }
    
    //将硬币分成4等份，若硬币总数不是4的倍数，则把另外不足4个的硬币先放在一边 
    q = (right - left + 1) / 4;
    left1 = left;
    right1 = left1 + q - 1; 
    left2 = right1 + 1;
    right2 = left2 + q - 1; 
    left3 = right2 + 1;
    right3 = left3 + q - 1; 
    left4 = right3 + 1;
    right4 = left4 + q - 1; 

    //累计每组硬币的重量 
    sum1 = sum2 = sum3 = sum4 = 0;
    for (i=left1; i<=right1; i++)
        sum1 += a[i];
    for (i=left2; i<=right2; i++)
        sum2 += a[i];  
    for (i=left3; i<=right3; i++)
        sum3 += a[i];
    for (i=left4; i<=right4; i++)
        sum4 += a[i];  

    //将硬币两两比较  
    count++; 
    if (sum1 != sum2)//伪币在第1，2组硬币中
    {
        if (sum1 < sum2)
            return FalseCoin(a, len, left1, right1);
        else
            return FalseCoin(a, len, left2, right2);
    }   
    count++;  
    if (sum3 != sum4) //伪币在第3，4组硬币中
    {
        if (sum3 < sum4)
            return FalseCoin(a, len, left3, right3);
        else
            return FalseCoin(a, len, left4, right4);
    }
    
    return FalseCoin(a, len, right4+1, right);//等重，伪币在剩余的硬币中 
}

先顶后看

最近考试,需要用此题,但我看,许多算法都好像将硬币的重量用数组存好了,真币既然重量都相同,假币比真币轻,重量你又存好了,那就没必要再去进行对重量进行操作了,直接在其中找最小的不就是了.再分治的法,还得调用栈,还用许多运算需要用,有点多此一举呀