题目描述
给出一个 N 次函数，保证在范围 [l,r] 内存在一点 x ，使得 [l,x] 上单调增， [x,r] 上单调减。试求出x的值。
输入格式
第一行一次包含一个正整数 N 和两个实数 l , r ，含义如题目描述所示。
第二行包含 N+1 个实数，从高到低依次表示该 N 次函数各项的系数。
1
2
3
样例输入
3 -0.9981 0.5
1 -3 -3 1
输出格
输出为一行，包含一个实数，即为 x 的值。若你的答案与标准答案的相对或绝对误差不超过 10−5 则算正确。
什么是三分法？
三分法类似于二分，原理为不断缩小答案所在的求解区间。
二分缩小区间利用函数的单调性，而三分法利用的则是函数的单峰性。
拿样例来说：y=x3−3x2−3x+1 , x∈[−0.9981,0.5]， 需要求出它在该区间的最大值 max:
将 [−0.9981,0.5] 均分为三个区间: [−0.9981,−0.498] , [−0.498,0.00006] , [0.00006,0.5] 。
同时得到了两个点 m1 和 m2 :
我们把 m1 , m2 中函数值更大的 m1 称为好点，较小的 m2 称为坏点。
那么不难发现，好点 m1 和极值 max 都在坏点 m2 的左侧，所以可以将搜索的区间缩小为 [−0.9981,0.00006] 。( 0.00006 即为 m2 的横坐标)
这样不断缩小搜索的区间，最终就能够获得一个足够小的区间以至接近一个实数值,以达到求值的目的。
代码实现
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
#include <iostream>
#include <cstdio>
using namespace std;
int n; // 函数次数
double l, r; // 左区间和右区间
double t[15]; // 各项系数
double f(double d) // 计算横坐标为d时的函数值
{
double ans = 0;
for (int i = n + 1; i >= 1; i--) // 高次向低次计算
{
double x = t[i];
for (int j = 1; j <= i - 1; j++) // 计算每一项的值（注意
x *= d;
ans += x; // 相加
}
return ans;
}
int main()
{
cin >> n >> l >> r; // 读入函数次数，左区间和右区间
for (int i = n + 1; i >= 1; i--) // 读入函数各项系数
cin >> t[i];
double lmid, rmid;
while (r - l > 0.00000001)
{
lmid = l + (r - l) / 3; // 相当于上面的m1的横坐标
rmid = r - (r - l) / 3; // 相当于上面的m2的横坐标
if (f(lmid) < f(rmid)) // 比较m1,m2哪个是好点，哪个是坏点
l = lmid; // 若m1是坏点，将左区间更新为m1的横坐标
else
r = rmid; // 若m2是坏点，将右区间更新为m2的横坐标
}
printf("%0.5lf\n", r); // 保留5位小数输出
return 0;
}
加一减一的细节要注意
