分治算法的基本思想是將一個(gè)計(jì)算復(fù)雜的問(wèn)題分為規(guī)模較小，計(jì)算簡(jiǎn)單的小問(wèn)題求解，然后綜合各個(gè)小問(wèn)題，而得到最終問(wèn)題的答案。分治算法的執(zhí)行過(guò)程如下：
- 對(duì)于一個(gè)規(guī)模為N的問(wèn)題，若該問(wèn)題可以容易地解決（比如說(shuō)規(guī)模N較小），則直接解決，否則執(zhí)行下面的步驟。
- 將該分解為M個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立，并且與原問(wèn)題形式相同。
- 遞歸地解決這些子問(wèn)題。
- 然后，將各個(gè)子問(wèn)題的解合并得到原問(wèn)題的解。
使用分治算法需要待求解問(wèn)題能夠化簡(jiǎn)為若干個(gè)小規(guī)模的相同問(wèn)題，通過(guò)逐步劃分，能夠達(dá)到一個(gè)易于求解的階段而直接進(jìn)行求解。然后，程序中可以使用遞歸算法來(lái)進(jìn)行求解。
下面我們通過(guò)一個(gè)例子來(lái)看分治算法具體的應(yīng)用場(chǎng)景。
一個(gè)袋子里有30個(gè)硬幣，其中一枚是假幣，并且假幣和真幣一模一樣，肉眼很難分辨，目前只知道假幣比真幣輕一點(diǎn)。請(qǐng)問(wèn)如何區(qū)分出假幣呢？
下面我們來(lái)分析一下問(wèn)題。可以采用遞歸分治的思想來(lái)求解這個(gè)問(wèn)題，操作步驟如下：
- 首先為每個(gè)硬幣編號(hào)，然后可以將所有的硬幣分為兩份，放在天平的兩邊。這樣就將區(qū)分30個(gè)硬幣的問(wèn)題，變?yōu)閰^(qū)分兩堆硬幣的問(wèn)題。
- 因?yàn)榧儆矌诺姆至枯^輕，因此天平較輕一側(cè)中一定包含假硬幣。
- 再將較輕一側(cè)中的硬幣等分為兩份，重復(fù)上述做法。
- 直到剩下的兩枚硬幣可用天平直接找出來(lái)假硬幣來(lái)。
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是偶數(shù)
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是奇數(shù)
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("分治算法求解假硬幣問(wèn)題！");
System.out.print("請(qǐng)輸入硬幣總的個(gè)數(shù):");
Scanner in = new Scanner(System.in);
n = in.nextInt();
System.out.println("請(qǐng)輸入硬幣的真假:");
for (i = 0; i < n; ++i) {
coin[i] = in.nextInt();
}
pos = FalseCoin(coin, 0, n - 1);
System.out.println("在上述" + MAXNUM + "個(gè)硬幣中，第" + pos + "個(gè)硬幣是假的！");
}
}
遞推算法是一種理性思維模式的代表，其根據(jù)已有的數(shù)據(jù)和關(guān)系，逐步推導(dǎo)而得到結(jié)果。遞推算法的執(zhí)行過(guò)程如下：
- 根據(jù)已知結(jié)果和關(guān)系，求解中間結(jié)果。
- 判斷是否達(dá)到要求，如果沒(méi)有達(dá)到，則繼續(xù)根據(jù)已知結(jié)果和關(guān)系求解中間結(jié)果；如果滿足要求，則表示尋找到一個(gè)正確的答案。
遞推算法往往需要用戶知道答案和問(wèn)題之間的邏輯。在許多數(shù)學(xué)問(wèn)題中，都有著明確的計(jì)算公式可以遵循，因?yàn)橥梢圆捎眠f推算法來(lái)實(shí)現(xiàn)。
下面通過(guò)一個(gè)斐波那契數(shù)列來(lái)看一下遞推的具體應(yīng)用場(chǎng)景：
如果有一對(duì)兩個(gè)月大的兔子以后每一個(gè)月都可以生一對(duì)小兔子，而一對(duì)新生的兔子出生兩個(gè)月后才可以生小兔子。也就是說(shuō)，1月份出生，3月份才可以產(chǎn)仔。那么假定一年內(nèi)沒(méi)有兔子死亡事件，那么1年后共有多少對(duì)兔子呢？
我們先來(lái)分析一下兔子產(chǎn)仔問(wèn)題。來(lái)逐月看一次每月的兔子對(duì)數(shù)：
第一個(gè)月：1對(duì)兔子；
第二個(gè)月：1對(duì)兔子；
第三個(gè)月：2對(duì)兔子；
第四個(gè)月：3對(duì)兔子；
第五個(gè)月：5對(duì)兔子；
......
從上面可以看出，從第3個(gè)月開(kāi)始，每一個(gè)月的兔子總對(duì)數(shù)等于前兩個(gè)月兔子數(shù)的總和。相應(yīng)的計(jì)算公式如下：
第n個(gè)月兔子總數(shù)Fn = Fn-1 + Fn-2。
這里，初始第一個(gè)月的兔子數(shù)為：F1 = 1，第二個(gè)月的兔子數(shù)為F2 = 1。
import java.util.Scanner;
public class Solution {
public static int fibonacci(int n) {
int t1, t2;
if (n == 1 || n == 2) {
return 1;
} else {
t1 = fibonacci(n - 1);
t2 = fibonacci(n - 2);
return t1 + t2;
}
}
public static void main(String[] args) {
System.out.println("遞推算法求解兔子產(chǎn)仔問(wèn)題！");
System.out.println("請(qǐng)先輸入時(shí)間：");
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int num = fibonacci(n);
System.out.println("經(jīng)過(guò)" + n + "月的時(shí)間，共能繁殖成" + num + "對(duì)兔子！");
}
}
