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

NaCly_Fish · 2018-12-26 18:49:06 · 题解

看见有很多大佬用求导+二分做的，学过高数都知道，其实求导不难。
那没学过高数的怎么办？
这里提供一种用导数本质来计算的方法。

在看导数的计算之前，我们先想一下斜率的计算。
过 (x_1,y_1),(x_2,y_2) 两点的直线斜率为：

而导数计算的就是过函数某一点切线的斜率。

在函数 f(x) 一点 (x,f(x)) 上，如果向右移动一点点（设移动了 \Delta x），就到了 (x+\Delta x,f(x+\Delta x))。
当 \Delta x 趋于 0 时，计算过这两点直线的斜率，就是过 (x,f(x)) 这点的切线斜率了。

然后很容易就能得出，函数 f(x) 的导函数 f'(x) 可以这样计算：

不过我们只用求导数的数值解，也就是近似值。所以只需要把 \Delta x 设为一个很小的值就可以了。写成代码，就是：

double derivative(double x){
    double dx = 1e-10;
    double dy = f(x+dx)-f(x);
    return dy/dx;
}   

其中 f 就是计算函数值的。

对于求导的结果，也可以表示成一个函数变化的快慢（显然），导数值为正表示函数值在增加，导数值为负表示函数在减小。

那么，如果导数值为零，且左边导数值为正，右边导数值为负，那么我们就找到了最小值，

由于这题中保证给定的 f(x) 在 [l,r] 上一段单调增，一段单调减；也就是说，f'(x) 在 [l,r] 上是一部分大于 0，一部分小于 0，还有一个唯一的零点，正好对应最大值，于是就可以愉快的二分啦！

另外，这样做还有一个好处：不用计算导函数具体是多少，比本题其它求导做法适用性更广。

参考代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define eps (1e-10)
using namespace std;

double l,r;
int n;
double a[20];

inline double f(double x){
    //秦九昭公式求多项式
    double u[20];
    u[n] = a[n];
    for(int i=n-1;i>=0;--i)
        u[i] = u[i+1]*x+a[i];
    return u[0];    
}

double check(double x){
    double dx = eps;
    double dy = f(x+dx)-f(x);
    return dy/dx;
}

int main(){
    scanf("%d",&n);
    scanf("%lf%lf",&l,&r);
    for(int i=0;i<=n;++i)
        scanf("%lf",&a[n-i]);
    double mid;    
    while(r-l>eps){
        mid = (l+r)/2;
        if(check(mid)>0) l = mid;
        else r = mid;
    }    
    printf("%.5lf",mid);
    return 0;    
}