数学一本通 7.3 函数的凹凸性

众所周知,单调函数可以用二分查找值

而有的函数是单峰(谷)的,这时就可以用三分求极值。

所谓三分,就是将函数分为三部分,每次舍去一部分

最后缩小到答案区间。

如图:

数学一本通 7.3 函数的凹凸性

当lmid>rmid时,[rmid,∞)区间内肯定没有答案

反之,lmid<rmid时,(-∞,lmid]区间内肯定没有答案

而两个相等时,极值肯定在中间,任舍一段即可(仅保留中间段也行)

 代码:

double solve(double left,double right)//三分 
{
    if(right-left<eps) return left;
    double mid=(left+right)/2;
    double lans=cal(mid-eps),rans=cal(mid+eps);
    if(lans>rans) return solve(left,mid);
    if(lans<rans) return solve(mid,right);
    return mid;
}

cal()是所求函数。

上一篇:传送带(信息学奥赛一本通-T1439)


下一篇:【SP15376】RMID-Running Median