容易发现单峰函数取到极值时导数为0,而导数又是单调的,所以可以直接在导数上二分。
洛谷板子:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define eps 1e-10
int n;
double a[20], l, r, mid, res;
inline double f(double x) {
double res = 0, t = 1;
for (int i = 0; i <= n; ++i, t *= x)
res += a[i] * t;
return res;
}
inline double detf(double x) {
double res = 0, t = 1;
for (int i = 1; i <= n; ++i, t *= x) {
res += a[i] * i * t;
} return res;
}
int main() {
scanf("%d", &n); scanf("%lf%lf", &l, &r);
for (int i = n; ~i; --i) scanf("%lf", &a[i]);
while (r - l > eps) {
mid = (l + r) / 2.0;
if (detf(mid) >= 0) l = (res = mid);
else r = mid;
} printf("%.6lf", res);
return 0;
}
对于某些不易求导(没有显式定义)但能快速求出值的函数,我们考虑导数的定义式:
\[f'(x)=\lim_{\Delta x\rightarrow 0} {f(x + \Delta x)-f(x)\over \Delta x} \]我们只需要令 \(\Delta x\) 取极小值近似 \(0\) 即可:
#define eps 1e-10
inline double detf(double x) {
return (f(x + eps) - f(x)) / eps;
}