简要介绍：
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。下面的硬币问题就是分治算法的一种典型算法题。
●硬币问题
在下面我们将硬币分为1和0两个值，1为真硬币，0为假硬币。找偶数枚硬币和奇数枚硬币将其随机排成一列，其中有一个假硬币，用分治算法寻找出这枚假硬币所在的位置。如下两图所示：
当硬币个数为偶数时（10枚）：
当硬币个数为奇数时（13枚）：
代码实现：
#include<iostream> using namespace std; #define maxsize 20 class fenzhi { public: int falsecoin(int low, int high); void showresult(); int num; int coin[maxsize]; int result; }; int fenzhi::falsecoin(int low, int high) { int sum1=0; int sum2=0; int sum3=0; if (low + 1 == high) //只有两枚硬币 { if (coin[low] < coin[high]) { result = low + 1; return result; } else { result = high + 1; return result; } } //分治算法 if((high-low+1)%2==0) //n是偶数 { for (int i = low; i <= low+(high-low)/2; i++) { sum1 += coin[i];//前半段和 } for (int j = low + (high - low) / 2+1; j <= high; j++) { sum2 += coin[j];//后半段和 } if (sum1 > sum2) { result = falsecoin(low + (high - low) / 2 + 1, high); //递推后半段 return result; } else if(sum1 < sum2) { result = falsecoin(low, low + (high - low) / 2); //递推前半段 return result; } } else //n是奇数 { for (int i = low;i<=low+(high-low)/2-1;i++) { sum1 += coin[i]; //中位数的前半段和 } for (int j = low + (high - low) / 2+1; j <= high; j++) { sum2 += coin[j]; //中位数的后半段和 } sum3 = coin[low + (high - low) / 2]; //中位数 if (sum1 > sum2) //前半段和大于后半段和 { result = falsecoin(low + (high - low) / 2 + 1, high);//递推后半段 return result; } else if (sum1 < sum2) //前半段和小于后半段和 { result = falsecoin(low, low + (high - low) / 2 - 1);//递推前半段 return result; } if (sum1 + sum3 == sum2 + sum3) //前半段和加中位数等于后半段和加中位数，所以中位数为目标寻找值 { result = low + (high - low) / 2+1; return result; } } } void fenzhi::showresult() { cout << "假币所在的位置：" << this->result << endl; } void text() { fenzhi fz; cout << "输入硬币的总数目：" << endl; cin >> fz.num; cout << "请输入硬币的真假（1真/0假）：" << endl; for (int i = 0; i < fz.num; i++) { cin >> fz.coin[i]; } fz.falsecoin(0, fz.num - 1); fz.showresult(); } int main() { text(); }
