上节中我们讲述了分治法，分治法是把一个大问题划分为若干子问题，分别求解子问题，然后再把子问题的解进行合并得到原问题的解。而减治法同样是把大问题分解成为若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，也无需对子问题进行合并。所以，可以说减治法是退化的分治法。
【减治法思想】：
减治法（reduce and conquer method）将原问题的解分解为若干个子问题，并且原问题的解与子问题的解之间存在某种确定关系，如果原问题的规模为n，则子问题的规模通常是n/2 或n-1；
【查找问题中的减治法】
【折半查找】：
问题，应用折半查找方法在一个有序序列中查找值为k的记录。若查找成功，返回记录k在序列中的位置，若查找失败，返回失败信息。
【思考】：
折半查找（binary search），利用了记录有序序列的特点，其查找过程是： 取得序列中的中间记录作为比较对象， 若给定值与中间记录相等，则查找成功；若给定值小于中间记录，则在中间记录的左边去继续查找；若给定值大于中间记录，则在中间的右半区继续查找。不断重复上述过程，直到查找成功；若干区域中没有记录，查找则是查找失败。
【例题】：
a、设置初始区间： 指针low指向第一个数字，high指向最后一个数字。查找区间为1~13，mid指向中间位置mid=7。
b、比较mid=7时对应的数字31 和 查找目标14比较，因为14<31，所以high指针指向6（high=6），同时mid=3。
c、mid指向的数字为18，因为18>14 所以移动指针，high=2，mid=1。
d、因为mid=1指向的数字7<14，所以low=mid=2，此次mid指向的恰好是14，查找成功返回mid位置。
【折半查找伪代码】：
输入：有序序列{ r1,r2,r3,....rn }
输出：若查找成功，返回记录为k的位置，若查找失败返回记录为0的位置。
1、设置初始查找区间：low=1，high=n；
2、测试查找区间[low，high]是否存在，若不存在，则查找失败；否则
3、取中间点mid=（low+high）/2；比较k与r(mid)有三种情况：
3.1 若k<r(mid) 则high=mid-1；查找在左半区进行，转步骤2；
3.2 若k>r(mid)则low=mid+1;查找在右半区进行，转到步骤2；
3.3 若k=r(mid)则查找成功，返回记录在表中的位置mid。
【组合问题中的减治法】：
【问题】：
国王赏赐大臣30枚金币，但是有一枚是假的，并且假的金币较轻，国王让大臣仅用一个天平，比较最少的次数得到答案。也就是，在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻，可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些。
【思考】：
我们可以把假币一分为二，也就是把n枚硬币分为两组，每组有n/2个硬币，如果n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。
如果两组硬币的重量相同，那么留下的硬币就是假币；否则用同样的方法对较轻的那组硬币进行同样的处理，因为假币一定在较轻的那组里。
这属于一个减治算法，因为每次用天平比较后，只需解决一个规模减半的问题，所以属于减治法算法。
那如果把假币分为三堆可以吗？ 或者分为四堆？哪种效率更高呢？
【C代码】：
假设求解30枚硬币的问题。
#include <stdio.h>
int getFalseCoin(int coin[], int low, int high)
{
int tmp1,tmp2,tmp;
tmp1 = 0;
tmp2 = 0;
tmp = 0;
if(low+1 == high){ //当比较最后两个时，判断那个值最小，返回小的那个值
if(coin[low] < coin[high])
return low;
else
return high;
}
tmp = high - low + 1;
if(tmp % 2 == 0){
tmp1 = getCoinSum(coin,low,low+tmp/2-1);
tmp2 = getCoinSum(coin,low+tmp/2,high);
if(tmp1 < tmp2)
return getFalseCoin(coin,low,low+tmp/2-1);
else
return getFalseCoin(coin,low+tmp/2,high);
}
else{
tmp1 = getCoinSum(coin,low,low + tmp/2-1);
tmp2 = getCoinSum(coin,low + tmp/2+1,high);
if(tmp1 < tmp2)
return getFalseCoin(coin,low,low+tmp/2-1);
else if(tmp1>tmp2)
return getFalseCoin(coin,low+tmp/2+1,high);
else
return low+tmp/2;
}
}
int getCoinSum(int coin[], int low, int high)
{
int sum = 0;
while(low <= high){
sum += coin[low++];
}
return sum;
}
int main(int argc, char *argv[])
{
int coin[30] = {1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2};
int result = getFalseCoin(coin,0,29);
printf("the result is : %d\n",++result);
return 0;
}
本节完毕，下一节动态规划算法。