二分法作為分治中最常見(jiàn)的方法，適用于單調(diào)函數(shù)，逼近求解某點(diǎn)的值。但當(dāng)函數(shù)是凸性函數(shù)時(shí)，二分法就無(wú)法適用，這時(shí)三分法就可以“大顯身手”～～
如圖，類(lèi)似二分的定義Left和Right，mid = (Left + Right) / 2，midmid = (mid + Right) / 2; 如果mid靠近極值點(diǎn)，則Right = midmid；否則(即midmid靠近極值點(diǎn))，則Left = mid;
程序模版如下：
double Calc(Type a)
{
/* 根據(jù)題目的意思計(jì)算 */
}
void Solve(void)
{
double Left, Right;
double mid, midmid;
double mid_value, midmid_value;
Left = MIN; Right = MAX;
while (Left + EPS < Right)
{
mid = (Left + Right) / 2;
midmid = (mid + Right) / 2;
mid_area = Calc(mid);
midmid_area = Calc(midmid);
// 假設(shè)求解最大極值.
if (mid_area >= midmid_area) Right = midmid;
else Left = mid;
}
}
現(xiàn)根據(jù)幾道的OJ題目來(lái)分析三分法的具體實(shí)現(xiàn)。
buaa 1033 Easy Problem
http://acm.buaa.edu.cn/oj/problem_show.php?c=0&p=1033
題意為在一條線段上找到一點(diǎn)，與給定的Ｐ點(diǎn)距離最小。很明顯的凸性函數(shù)，用三分法來(lái)解決。
Calc函數(shù)即為求某點(diǎn)到P點(diǎn)的距離。
ZOJ 3203 Light Bulb
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3203
如圖，人左右走動(dòng)，求影子L的最長(zhǎng)長(zhǎng)度。
根據(jù)圖，很容易發(fā)現(xiàn)當(dāng)燈，人的頭部和墻角成一條直線時(shí)(假設(shè)此時(shí)人站在A點(diǎn))，此時(shí)的長(zhǎng)度是影子全在地上的最長(zhǎng)長(zhǎng)度。當(dāng)人再向右走時(shí)，影子開(kāi)始投影到墻上，當(dāng)人貼著墻，影子長(zhǎng)度即為人的高度。所以當(dāng)人從A點(diǎn)走到墻，函數(shù)是先遞增再遞減，為凸性函數(shù)，所以我們可以用三分法來(lái)求解。
下面只給出Calc函數(shù)，其他直接套模版即可。
double Calc(double x)
{
return (h * D - H * x) / (D - x) + x;
}
heru 5081 Turn the corner 08年哈爾濱regional網(wǎng)絡(luò)賽
http://acm.hrbeu.edu.cn/index.php?act=problem&id=1280
汽車(chē)拐彎問(wèn)題，給定X, Y, l, d判斷是否能夠拐彎。首先當(dāng)X或者Y小于d，那么一定不能。
其次我們發(fā)現(xiàn)隨著角度θ的增大，最大高度ｈ先增長(zhǎng)后減小，即為凸性函數(shù)，可以用三分法來(lái)求解。
這里的Calc函數(shù)需要比較繁瑣的推倒公式：
s = l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);
其中s為汽車(chē)最右邊的點(diǎn)離拐角的水平距離, h為里拐點(diǎn)最高的距離, θ范圍從0到90。
POJ 3301 Texas Trip
http://acm.pku.edu.cn/JudgeOnline/problem?id=3301
題意為給定n(n <= 30)個(gè)點(diǎn)，求出飽含這些點(diǎn)的面積最小的正方形。
有兩種解法，一種為逼近法，就是每次m分角度，求出最符合的角度，再繼續(xù)m分，如此進(jìn)行times次，即可求出較為精確的解。(m 大概取10, times取30即可)
第二種解法即為三分法，首先旋轉(zhuǎn)的角度只要在0到180度即可，超過(guò)180度跟前面的相同的。坐標(biāo)軸旋轉(zhuǎn)后，坐標(biāo)變換為：
X’ = x * cosa - y * sina;
y’ = y * cosa + x * sina;
至于這題的函數(shù)是否是凸性的，為什么是凸性的，我也無(wú)法給出準(zhǔn)確的證明，希望哪位路過(guò)的大牛指點(diǎn)一下～～
例題更新(2010.5.5)
hdu 3400 Line belt
http://acm.hdu.edu.cn/showproblem.php?pid=3400
典型的三分法，先三分第一條線段，找到一個(gè)點(diǎn)，然后根據(jù)這個(gè)點(diǎn)再三分第二條線段即可，想出三分的思路基本就可以過(guò)了。
對(duì)于求解一些實(shí)際問(wèn)題，當(dāng)公式難以推導(dǎo)出來(lái)時(shí)，二分、三分法可以較為精確地求解出一些臨界值，且效率也是令人滿意的。
/* czyuan原創(chuàng)，轉(zhuǎn)載請(qǐng)注明出處。*/
轉(zhuǎn)自：
http://hi.baidu.com/czyuan_acm/blog/item/8cc45b1f30cefefde1fe0b7e.html