【算法】三分法

大家好，欢迎来到IT知识分享网。

原文链接：https://blog.csdn.net/caduca/article/details/

（家人们，转载佬的一篇文章，当笔记啦~）

三分法介绍

     在区间内用两个mid将区间分成三份，这样的查找算法称为三分查找,也就是三分法，三分法常用于求解单峰函数的最值。  

       还有一种理解，即在二分查找的基础上，在左区间或者右区间上再进行一次二分。

三分与二分的区别

     二分法适用于单调函数，而单峰函数用二分明显不太好了，对于有些单峰函数，可以求导后转化为单调函数，从而使用二分，然而很多情况求导是很麻烦的，这时就需要用到三分了。

算法介绍

1.先将区间三分,每个区间的长度为1/3(right-left)

mid1=left+(right-left)/3; mid2=right-(right-left)/3;

2.比较mid1和mid2谁更靠近极值，如果mid1更靠近极值，右区间改为mid2,否则左区间改为mid1(后面的代码都是   以求最大值为例）

if(calc(mid1)<calc(mid2)) left=mid1; else right=mid2;

3.重复1,2过程，直到不满足left+eps<right,也就是找到最值

算法模板

 #define eps 10e-6 double cal() {} //计算题目所需要的值 while(l+eps<r) { m1=l+(r-l)/3; m2=r-(r-l)/3; v1=cal(m1); v2=cal(m2); if(v1<v2)l=m1; else r=m2; }

另一种写法

 double Calc(Type a) { /* 根据题目的意思计算 */ } 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); if (mid_area >= midmid_area) Right = midmid; else Left = mid; } }

个人还是喜欢第一种写法，感觉区间大小相同还是比较和谐一点的O(∩_∩)O~~

几道题目三分题

poj 3737 UmBasketella 

题目：http://poj.org/problem?id=3737

给出椎体的表面积，求最大体积和此时的高和底面半径。
题解：http://blog.csdn.net/caduca/article/details/

hdu 2438 Turn the corner 

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2438

给出街道在x轴的宽度X，y轴的宽度Y，还有车的长l和宽w，判断是否能够转弯成功。
题解：http://blog.csdn.net/caduca/article/details/

hdu 3400 Line belt

题目http://acm.hdu.edu.cn/showproblem.php?pid=3400

已知两条线段，分别知道在两条线段上AB,CD的速度p，q和不在两条线段上的速度r，求从A点到D点的最小时间。
题解：http://blog.csdn.net/caduca/article/details/