经典示例
例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);
}
}
评论