三分法 学习笔记

模板及讲解

三分和二分区别

二分法用于单调函数上逼近某值,而三分法用于单峰函数 (凸函数/凹函数)上逼近极值点。

基本思路

对于区间$[l,r]$,我们求出$[l,r]$中点$mid$,再求出$[mid,r]$的中点$mmid$.

如果$f(mid) > f(mmid)$,那么$mmid$在极值点右边
如果$f(mid) < f(mmid)$,那么$mmid$在极值点左边

以上直接用反证法可以证明,根据单调性的定义。

然后就可以用这个方法来更新了,最后$l,r$大的那个点是极值点。

代码

例题:P3382 三分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define pb push_back
#define sec second
#define fir first
using namespace std;
int n;
db l, r, a[20];
const db eps = 1e-7;
db f(db x) {
db ret = a[1];
for (int i = 2; i <= n + 1; i++) ret = ret * x + a[i];//秦九韶算法 (提取各项的x)
return ret;
}
void clean() {}
int solve() {
clean();
for (int i = 1; i <= n + 1; i++) scanf("%lf", &a[i]);
f(2);
db mid, mmid;
while (fabs(r - l) > eps) {
mid = (l + r) / 2, mmid = (mid + r) / 2;
if (f(mid) > f(mmid)) r = mmid; else l = mid;
}
printf("%.5f\n", mid);
return 0;
}
int main() {
scanf("%d%lf%lf", &n, &l, &r), solve();
return 0;
}

常见题型

1、三分法
Q:见讲解
解:见讲解
例题:P3382 三分法
2、三分套三分
Q:有两个点需要三分
解:有两个点需要三分,就三分后再三分一次
例题:Bzoj 1857

------ 本文结束 ------