题解 P3382 【【模板】三分法】
NaCly_Fish
2018-12-26 18:49:06
看见有很多大佬用求导+二分做的，学过高数都知道，其实求导不难。
那没学过高数的怎么办？
这里提供一种用导数本质来计算的方法。
在看导数的计算之前，我们先想一下斜率的计算。
过 $(x_1,y_1),(x_2,y_2)$ 两点的直线斜率为：
$$\text{Slope}=\frac{y_1-y_2}{x_1-x_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)$ 可以这样计算：
$$f'(x)=\lim\limits_{\Delta x\rightarrow0}\frac{f(x+\Delta x)-f(x)}{\Delta x}$$
不过我们只用求导数的数值解，也就是近似值。所以只需要把 $\Delta x$ 设为一个很小的值就可以了。写成代码，就是：
```cpp
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$，还有一个唯一的零点，正好对应最大值，于是就可以愉快的二分啦！
另外，这样做还有一个好处：不用计算导函数具体是多少，比本题其它求导做法适用性更广。
参考代码：
```cpp
#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;
}
```