分治算法的基本思想是将一个计算复杂的问题分为规模较小，计算简单的小问题求解，然后综合各个小问题，而得到最终问题的答案。分治算法的执行过程如下：
- 对于一个规模为N的问题，若该问题可以容易地解决（比如说规模N较小），则直接解决，否则执行下面的步骤。
- 将该分解为M个规模较小的子问题，这些子问题互相独立，并且与原问题形式相同。
- 递归地解决这些子问题。
- 然后，将各个子问题的解合并得到原问题的解。
使用分治算法需要待求解问题能够化简为若干个小规模的相同问题，通过逐步划分，能够达到一个易于求解的阶段而直接进行求解。然后，程序中可以使用递归算法来进行求解。
下面我们通过一个例子来看分治算法具体的应用场景。
一个袋子里有30个硬币，其中一枚是假币，并且假币和真币一模一样，肉眼很难分辨，目前只知道假币比真币轻一点。请问如何区分出假币呢？
下面我们来分析一下问题。可以采用递归分治的思想来求解这个问题，操作步骤如下：
- 首先为每个硬币编号，然后可以将所有的硬币分为两份，放在天平的两边。这样就将区分30个硬币的问题，变为区分两堆硬币的问题。
- 因为假硬币的分量较轻，因此天平较轻一侧中一定包含假硬币。
- 再将较轻一侧中的硬币等分为两份，重复上述做法。
- 直到剩下的两枚硬币可用天平直接找出来假硬币来。
public class Solution {
static final int MAXNUM = 30;
public static int FalseCoin(int[] coin, int low, int high) {
int res = 0;
int i, sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0;
if (low + 1 == high) {
if (coin[low] < coin[high]) {
res = low + 1;
return res;
} else {
res = high + 1;
return res;
}
}
if ((high - low + 1) % 2 == 0) { // n是偶数
for(i = low; i <= low + (high - low) / 2; ++i) {
sum1 = sum1 + coin[i]; // 前半段和
}
for (i = low + (high - low) / 2 + 1; i <= high; ++i) {
sum2 = sum2 + coin[i]; // 后半段和
}
if (sum1 > sum2) {
res = FalseCoin(coin, low + (high - low) / 2 + 1, high);
}
else if (sum1 < sum2) {
res = FalseCoin(coin, low, low + (high - low) / 2);
} else {
}
} else { // n是奇数
for (i = low; i <= low + (high - low) / 2 - 1; ++i) {
sum1 = sum1 + coin[i]; // 前半段和
}
for (i = low + (high - low) / 2 + 1; i <= high; ++i) {
sum2 = sum2 + coin[i]; // 后半段和
}
sum3 = coin[low + (high - low) / 2];
if (sum1 > sum2) {
res = FalseCoin(coin, low + (high - low) / 2 + 1, high);
return res;
} else if (sum1 < sum2) {
res = FalseCoin(coin, low, low + (high - low) / 2 - 1);
return res;
} else {
}
if (sum1 + sum3 == sum2 + sum3) {
res = low + (high - low) / 2 + 1;
return res;
}
}
return res;
}
public static void main(String[] args) {
int[] coin = new int[MAXNUM];
int i, n;
int pos;
System.out.println("分治算法求解假硬币问题！");
System.out.print("请输入硬币总的个数:");
Scanner in = new Scanner(System.in);
n = in.nextInt();
System.out.println("请输入硬币的真假:");
for (i = 0; i < n; ++i) {
coin[i] = in.nextInt();
}
pos = FalseCoin(coin, 0, n - 1);
System.out.println("在上述" + MAXNUM + "个硬币中，第" + pos + "个硬币是假的！");
}
}
运行结果
网友评论