三分:求解凸函数极值

三分算法:三分算法(简称三分法)用于求解凸性函数的极值问题。二分法适用于单调函数,当需要求凸性函数的极值点时,三分法便可派上用场。使用二分法不能判断函数极值点在哪部分,而使用三分法将区间分成三部分,可以明确判定一定不在哪部分,每次舍弃三分之一的查找空间,效率也很高。


题目

TOJ3777 Function Problem

#include<bits/stdc++.h>

using namespace std;

double a1,b1,c1,a2,b2,c2;

double f(double x)
{
    return max(a1*x*x + b1*x +c1, a2*x*x + b2*x + c2);
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf%lf%lf",&a1,&b1,&c1,&a2,&b2,&c2);
        double left = 0.0,right = 1000.0;
        while(right - left >= 1e-8){
            double mid1 = left + (right - left)/3.0;
            double mid2 = right - (right - left)/3.0;

            if(f(mid1) < f(mid2) + 1e-8) right = mid2;
            else left = mid1;
        }
        printf("%.4lf
", f(left));
    }
    return 0;
}
View Code
原文地址:https://www.cnblogs.com/solvit/p/9789396.html