题解 P3382 【【模板】三分法】

很多人对模拟退火算法的讲解都说过类似这样的话 >为了避免落入局部最优解，我们要随机接受一个更坏的值来跳出局部最优解 然而，区间单峰函数并不存在让人落进去的局部最优解，所以我们引入一个更简单的算法—— # 爬山算法 ## 算法思想 顾名思义，我们在函数上“爬山”，**每次看左右哪边是“上坡”，就往哪边爬一点**。代码实现极其简单，思维难度几乎为0 ## 程序实现 ```cpp // luogu-judger-enable-o2 #include <iostream> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; int n; double l, r; double co[15]; int Rand() {//我们不想随机出一个太大的数，那样每次移动的就太小了 return rand() % 1000 + 500; } double Func(double x) {//暴力计算函数 double res = 0; for (int i = 0; i <= n; i++) { double tmp = 1; for (int j = 1; j <= i; j++) tmp *= x; res += co[i] * tmp; } return res; } double Move(double x, int typ) {//左右移动，0为左1为右，注意是否跨过0 if (x < 0) { if (typ == 1) { if (x > -1e-5) x += 1e-5; else x *= (1.000000 - 1.000000 / Rand()); } else { x *= (1.000000 + 1.000000 / Rand()); } } else { if (typ == 1) { x *= (1.000000 + 1.000000 / Rand()); } else { if (x < 1e-5) x -= 1e-5; else x *= (1.000000 - 1.000000 / Rand()); } } return x; } int main() { srand(114514); cin >> n >> l >> r; for (int i = n; i >= 0; i--) cin >> co[i]; double cur = (l + r) / 2.000000; //随便找个初始开爬的点，强迫症让我选了中点 double f = Func(cur); double f1, f2, nxt1, nxt2, mx = f, mxans = cur; for (int i = 1; i <= 100000; i++) { // cerr << cur << "\n"; nxt1 = Move(cur, 0);//尝试左右移动 nxt2 = Move(cur, 1); f1 = Func(nxt1);//计算两种函数值 f2 = Func(nxt2); if (f1 > f) { cur = nxt1; f = f1; } else { cur = nxt2; f = f2; } if (f > mx) {//更新最优解 mx = f; mxans = cur; } } cout << fixed << setprecision(5) << mxans << "\n"; return 0; } ```