# Irelia

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

posted on 2019-08-31 15:02:20 | under 题解 |

# 爬山算法

## 程序实现

// 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;
}