三分法

Zxsoul · 2021-08-19 19:52:50 · 个人记录

三分法

简单说明和提一下要点+板子

首先是求一元二次方程求单峰用，两次二分，分成三个区间，注意缩小范围。

注：// 三分针对是一个区间内的单峰值，而不是仅仅一条抛物线

代码理解：

大于就证明最值已经不在midmid 到 r 区间值，显然要删去区间，更新右端点。对于答案的更新，很简单，缩短区间

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int B=100;
double a[B];
int n;
double l,r;
double eps=1e-5;
double f(double x)
{
    double res=0;
    for (int i=1;i<=n+1;i++)
    {
        res=res*x+a[i];
    }
    return res;
}
signed main()
{
    cin>>n;
    scanf("%lf%lf",&l,&r);
    for (int i=1;i<=n+1;i++) scanf("%lf",&a[i]);
    double ans=0;
    while (l+eps<r)
    {
        double mid=(l+r)/2;
        double midmid=(mid+r)/2;
        double d1=f(mid); double d2=f(midmid);
        if (d1>=d2) r=midmid;
        else l=mid;
    }
    printf("%.5lf",r);
}