4.12 三分法学习笔记

标签：三分法 4.12 rmid db 笔记 单调 lmid 最值

三分的思路和二分有一点像。正好这两天数学在学函数的单调性，所以感觉还不错。但是三分法出题似乎有一定的局限性，所以应用并不广泛，但是还是需要学习一下。

---

P3382 【模板】三分法 一个洛谷三分的板子。三分求单峰函数极值。

三分适用的情况：有唯一的最大值，满足最大值左侧严格单调递增，右侧严格单调递减（或左减右增）。强调严格单调，这样在确定最值是才能判断最值的位置，否则三分法不能缩小左右边界。

 此处以该题为例，即该单峰函数存在最大值，最大值左侧严格单调递增，最大值右侧严格单调递减。

不妨将当前所找的区间 [l, r] 用 lmid 与 rmid 划分为三个区间，lmid < rmid。 此时 f(lmid) > f(rmid) 会有两种情况：1.lmid 与 rmid 均在最值右侧；2.lmid 在最值左侧，rmid 在最值右侧。 会发现无论是哪种情况，rmid 都在最值的右侧，那么我们就可以将所寻找的区间缩小，即使 r = rmid。同理，当 lmid > rmid 时使 l = lmid。 其他没什么需要特别注意的。鉴于本题涉及到浮点数，所以关注一下判断两个浮点数相同时，相减，若差小于一个很小的数即可（精度一般 1e-6 或 1e-7 就行）。

#include<bits/stdc++.h>
#define db double
using namespace std;
const db eps = 1e-7;
int n;
db a[15];
db l, r, midl, midr;
db f(db x)
{
    db s = 0;
    for(int i = n; i >= 0; i -- ) s = s * x + a[i];
    return s; 
}
int main()
{
    scanf("%d%lf%lf", &n, &l, &r);
    for(int i = n; i >= 0; i -- ) scanf("%lf", &a[i]);
    while(r - l > eps)
    {
        midl = l + (r - l) / 3.0;
        midr = r - (r - l) / 3.0;
        if(f(midl) > f(midr)) r = midr;
        else l = midl;
    }
    printf("%.5lf", l);
    return 0;
}

---

 

标签：三分法,4.12,rmid,db,笔记,单调,lmid,最值
From： https://www.cnblogs.com/Moyyer-my/p/17308879.html