三分的更优?写法

容易发现单峰函数取到极值时导数为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;
}
上一篇:vscode 新建代码块


下一篇:PTA-56 求给定精度的简单交错序列部分和