百家利网站开发,深圳物流公司联系电话,门户网站推广介绍方案,大连seo外包【题目链接】
ybt 1435#xff1a;【例题3】曲线 洛谷 P1883 函数
【题目考点】
1. 三分
【解题思路】
每个 S i ( x ) S_i(x) Si(x)是一个二次函数#xff0c; F ( x ) m a x ( S i ( x ) ) F(x) max(S_i(x)) F(x)max(Si(x))#xff0c;即为所有二次函数当自变量…【题目链接】
ybt 1435【例题3】曲线 洛谷 P1883 函数
【题目考点】
1. 三分
【解题思路】
每个 S i ( x ) S_i(x) Si(x)是一个二次函数 F ( x ) m a x ( S i ( x ) ) F(x) max(S_i(x)) F(x)max(Si(x))即为所有二次函数当自变量为x时的所有函数值的最大值。 已知 a ≥ 0 a \ge 0 a≥0所以所有的二次函数都是开口向上的为下凸函数。 首先要证明 F ( x ) F(x) F(x)在定义域为[0, 1000]的范围内是下凸函数凸函数定义 已知f(x),g(x)为下凸函数证明h(x)max(f(x),g(x))是一个下凸函数。 证明: 根据凸函数的定义对于任意的 0 ≤ α ≤ 1 0\leq\alpha\leq1 0≤α≤1定义域内的任意 x 1 , x 2 x1, x2 x1,x2总有 f ( α x 1 ( 1 − α ) x 2 ) ≤ α f ( x 1 ) ( 1 − α ) f ( x 2 ) ≤ α h ( x 1 ) ( 1 − α ) h ( x 2 ) f(\alpha{x1}(1-\alpha)x2)\leq\alpha{f(x1)}(1-\alpha){f(x2)}\leq\alpha{h(x1)}(1-\alpha){h(x2)} f(αx1(1−α)x2)≤αf(x1)(1−α)f(x2)≤αh(x1)(1−α)h(x2) 同理对于g(x)也有相似的结论 g ( α x 1 ( 1 − α ) x 2 ) ≤ α g ( x 1 ) ( 1 − α ) g ( x 2 ) ≤ α h ( x 1 ) ( 1 − α ) h ( x 2 ) g(\alpha{x1}(1-\alpha)x2)\leq\alpha{g(x1)}(1-\alpha){g(x2)}\leq\alpha{h(x1)}(1-\alpha){h(x2)} g(αx1(1−α)x2)≤αg(x1)(1−α)g(x2)≤αh(x1)(1−α)h(x2) 将 x α x 1 ( 1 − α ) x 2 x\alpha{x1}(1-\alpha)x2 xαx1(1−α)x2带入 h ( x ) h(x) h(x)有 h ( α x 1 ( 1 − α ) x 2 ) m a x ( f ( α x 1 ( 1 − α ) x 2 ) , g ( α x 1 ( 1 − α ) x 2 ) ) ≤ m a x ( α h ( x 1 ) ( 1 − α ) h ( x 2 ) , α h ( x 1 ) ( 1 − α ) h ( x 2 ) ) α h ( x 1 ) ( 1 − α ) h ( x 2 ) h(\alpha{x1}(1-\alpha)x2)max(f(\alpha{x1}(1-\alpha)x2),g(\alpha{x1}(1-\alpha)x2))\leq max(\alpha{h(x1)}(1-\alpha){h(x2)},\alpha{h(x1)}(1-\alpha){h(x2)}) \alpha{h(x1)}(1-\alpha){h(x2)} h(αx1(1−α)x2)max(f(αx1(1−α)x2),g(αx1(1−α)x2))≤max(αh(x1)(1−α)h(x2),αh(x1)(1−α)h(x2))αh(x1)(1−α)h(x2) h(x)满足下凸函数的定义因此也是下凸函数 已知f(x),g(x)两个函数的较大值h(x)max(f(x),g(x))是下凸函数那么多个函数的最大值 F ( x ) F(x) F(x)也是下凸函数。
已知 F ( x ) F(x) F(x)在定义域[0,1000]中是下凸函数单谷函数因此可以使用三分求单谷函数的极小值点。 首先把左端点l设为0右端点r设为1000 每次循环取三分点lm l(r-l)/3, rm r-(r-l)/3 求出两个三分点位置的函数值f(lm)、f(rm) 设极值点为m注极值点是取到极值时函数自变量的值
当f(lm)f(rm)时可能是lm m rm或m lm rm极值点一定不在[rm, r]的范围内因此使r rm[l, r]的范围缩减1/3。当f(lm)f(rm)时可能是lm m rm或lm rm m极值点一定不在[l, lm]的范围内因此使l lm[l, r]的范围缩减1/3。 当 r − l 1 0 − 10 r-l 10^{-10} r−l10−10时跳出循环此时l或r都是极值点的近似值。 求极值点位置的函数值即为 f ( l ) f(l) f(l)
三分算法的时间复杂度 O ( l o g n ) O(log n) O(logn)n为初始的数值范围大小在本题中为1000。 【注】r与l差值很小时结束循环对于一般的结果保留几位小数的问题比如保留5位8位等将差值取为 1 0 − 10 10^{-10} 10−10是合理的。取 r − l 1 0 − 10 r-l10^{-10} r−l10−10与取 r − l 1 0 − 5 r-l10^{-5} r−l10−5在循环次数上是相同数量级的而且能保证结果的准确性。
【题解代码】
解法1三分
#includebits/stdc.h
using namespace std;
#define N 10005
int a[N], b[N], c[N], n, t;//a[i], b[i], c[i]第i个二次函数的a、b、c
double f(double x)
{double ans -1e9;for(int i 1; i n; i)ans max(ans, a[i]*x*xb[i]*xc[i]);return ans;
}
int main()
{scanf(%d, t);while(t--){scanf(%d, n);for(int i 1; i n; i)scanf(%d%d%d, a[i], b[i], c[i]);double l 0, r 1000;while(r-l 1e-10){double lm l(r-l)/3, rm r-(r-l)/3;if(f(lm) f(rm))l lm;elser rm;}printf(%.4f\n, f(l));}return 0;
}
