三分

三分法用来解决单峰单谷问题,经典二次函数型的变化时,可以使用三分优化

当问题是解决一堆都是整数的问题时,较为简单,模板代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
//下面就是要寻找的二次函数型数组,目标是找到其中的最大值
int a[10] = { 0, 3, 25, 21, 20, 14, 12, 7, 2, 1 };
int main()
{
int z = 0, y = 9;
while (z <= y)
{
//三分,就是将区间尽量平均分成三份
int mid1 = z + (y - z) / 3;
int mid2 = y - (y - z) / 3;
//判断两者中的较大值,那么较小值的一方的元素都不可能是最大值,直接舍去
if (a[mid1] >= a[mid2]) y = mid2 - 1;
else z = mid1 + 1;
}
//最终结果位置与二分类似
cout << a[z] << endl;
return 0;
}

但是要使用三分思路解决的问题往往是要求到实数,问题的变化过程往往是一段连续实数的函数,而不是像数列那样的连续整数,那会有什么变化吗?

上面模板中的循环判断 while(z <= y) 是通过整数 z 和 y,也就是下标的序数进行更替判断,我们知道整数在进行除法会有自动向下取整,但是 double 类型会有一定的小数精确,但是这个精确度是不够用的,在经过多次运算误差就会越来越大,最后很可能就改变答案导致错误!

这里给出三种解决思路

一.直接使用数据本身进行循环判断,既然实数多次计算有误差,while 直接用来判断每次两者差值小于某个 epsilon(例如 1e-7),来控制循环结束(这时候数据已经细分很小,可以直接近似得到最值了)具体精度控制看题目要求

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
double f(double x) {
// 示例函数,此处替换为实际函数
return -x*x + 2*x + 3; // 极大值在x=1处
}
// 精度控制
const double eps = 1e-9;
while (r - l > eps)
{
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(m1) < f(m2))
{
// 求极大值,若求极小值则改为>,极值在[m1, r]
l = m1;
} else
{
// 极值在[l, m2]
r = m2;
}
}
// 返回近似极值点
return (l + r) / 2;

二.我们发现当每一次三分数据总数都会缩小三分之一,那么当循环次数达到一定多时,剩余数据就能够在误差范围内得到正确答案!所以可以固定循环次数为循环条件进行三分!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int T = 100; // 迭代次数,确保精度
double f(double x)
{
return -x*x + 2*x + 3; // 示例函数,极大值在x=1
}
double ternary_search_fixed_loop(double l, double r, int T) {
while (T--)
{
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(m1) < f(m2))
{ // 求极大值
l = m1; // 极值在右区间
} else
{
r = m2; // 极值在左区间
}
}
return (l + r) / 2;
}

三.将要求的实数区间存放在整数数组中,例如:给定一段长度的两端值,我们主动将这段长度均分为 N 份(N 可能是 5000,10000…..),这时候就可以将问题转换为最简单的模板类型解决!

此情况直接附上题目进行理解吧

例题

本题较为复杂,涉及两个三分嵌套,并将三分问题按照法三转换为整数型模板!

ac 代码如下:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cmath>
using namespace std;
const int N = 5005;
struct ty
{
double x, y;
}a, b, c, d, e[N + 5], f[N + 5];
//t1是当前点到A点所需的时间,t2是当前点到D点所需的时间
double t1[N + 5], t2[N + 5];
double p, q, r;
//计算距离的函数
double dis(ty a, ty b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
//第二个三分,用于嵌套在第一个三分内部,返回总时间最小的情况
double sol(int mid)
{
int z2 = 0, y2 = N;
while (z2 <= y2)
{
int mid1 = z2 + (y2 - z2) / 3;
int mid2 = y2 - (y2 - z2) / 3;
if ((t1[mid] + t2[mid1] + (dis(e[mid], f[mid1]) / r)) <= (t1[mid] + t2[mid2] + (dis(e[mid], f[mid2]) / r)))
y2 = mid2 - 1;
else z2 = mid1 + 1;
}
return (t1[mid] + t2[z2] + (dis(e[mid], f[z2]) / r));
}
int main()
{
cin >> a.x >> a.y >> b.x >> b.y;
cin >> c.x >> c.y >> d.x >> d.y;
cin >> p >> q >> r;
//关键步骤!!!用于将实数三分转换为整数型三分,最后分别存放于数组 e 和 f 中。
double dx = (b.x - a.x) / N, dy = (b.y - a.y) / N;
for (int i = 0; i <= N; i++)
{
e[i].x = a.x + dx * i, e[i].y = a.y + dy * i;
t1[i] = dis(a, e[i]) / p;
}
dx = (d.x - c.x) / N, dy = (d.y - c.y) / N;
for (int i = 0; i <= N; i++)
{
f[i].x = c.x + dx * i, f[i].y = c.y + dy * i;
t2[i] = dis(d, f[i]) / q;
}
//外层三分循环,枚举AB段的情况,再结合sol函数,最终求出时间最小的情况!
int z1 = 0, y1 = N;
while (z1 <= y1)
{
int mid1 = z1 + (y1 - z1) / 3;
int mid2 = y1 - (y1 - z1) / 3;
if (sol(mid1) <= sol(mid2)) y1 = mid2 - 1;
else z1 = mid1 + 1;
}
//按照题目要求精度输出即可
printf("%.2f\n", sol(z1));
return 0;
}

其实还有一种妙法!就是求导!利用定义求导,(dy / dx) 当 dx 极小时,整个就是当前点的导数值。这样就可以将三分问题转换为二分求零点的问题!这里留给读者思考(因为我自己其实也没试过,怕写错了误导大家~

再附上一道三分例题:例题