算法笔记三分三分
scandi三分法用来解决单峰单谷问题,经典二次函数型的变化时,可以使用三分优化
当问题是解决一堆都是整数的问题时,较为简单,模板代码如下:
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; }
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)) { l = m1; } else { 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; } 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];
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; 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; } 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 极小时,整个就是当前点的导数值。这样就可以将三分问题转换为二分求零点的问题!这里留给读者思考(因为我自己其实也没试过,怕写错了误导大家~
再附上一道三分例题:例题