题解 P3382 【【模板】三分法】

· · 题解

既然看到没什么人介绍这个算法，那我来讲这样一个不实用的算法

梯度下降

（不确定是不是这么叫的叫错了大佬们别打我~） 梯度下降是一种用来逼近函数最小值的算法

（这题求的是最大值，和求最小值几乎一样，所以我先说说最小值的求法）

什么是梯度呢？对于一元函数，你可以理解为函数图像在某一点上升的方向和坡度或者说是它的导数

所谓梯度下降，就是沿着与梯度相反的方向走。可以形象的理解为，从函数图像的某一点往下滑，一直滑到最低点。

下面给出梯度下降显而易见的公式：

x_new=x_old−η∇f(x)

其中，∇f(x)为f(x)的梯度，η为步长

看一下下降的过程：(注：这个图不是我画的)

这样就能逼近函数最小值了

回到本题，怎么求最大值呢？只要把梯度下降的过程反过来就行了：沿着梯度向上爬

本题的函数f(x)的导数f'(x)非常好求：

f'(x)=(AnX^n + An-1X^n-1 + An-2X^n-2 + ... + A1X + A0)'

 =n(AnX^n) + (n-1)(An-1X^n-1) + (n-2)(An-2X^n-2) + ... + A1X
double fun_(LLd x)
{
    double ans=0;
    for (int i=n;i>=1;i--)
    {
        ans=ans*x+a[i]*i;
    }
    return ans;
}

从哪开始计算呢？l到r范围内任意一点都可以，这里我们取中点

至于η的取值，本题应取得很小（实测需取到0.0000001）。因为l和r相距很 近，而斜率可能很大，容易跳出l,r的范围

然后就可以开心的迭代啦

这个算法有多不靠谱呢？

AC代码TLE了样例！！！qwq

上代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#define LL long long
#define LLd long double
using namespace std;

const LL maxn=15;
const LLd eta=0.0000001;
LLd a[maxn];
LLd n;

LLd fun_(LLd x)
{
    LLd ans=0;
    for (LL i=n;i>=1;i--) ans=ans*x+a[i]*i;
    return ans;
}

int main()
{
    LLd l,r;
    cin>>n>>l>>r;
    for (LL i=n;i>=0;i--) cin>>a[i];
    LLd x=(l+r)/2;
    while (abs(fun_(x))>0.000001) x=x+eta*fun_(x);
    printf("%.5Lf\n",x);
    return 0;
}

(想测试样例把η(eta)改大到0.0001就行了)

这种算法还能扩展到多元函数(不过导数变成了偏导数)

事实上现在的人工智能大多也是用梯度下降训练的qwq