题目描述
给出一个 $N$ 次函数，保证在范围 $\displaystyle [l,r]$ 内存在一点 $x$ ，使得 $\displaystyle [l,x]$ 上单调增， $\displaystyle [x,r]$ 上单调减。试求出x的值。
输入格式
第一行一次包含一个正整数 $N$ 和两个实数 $l$ , $r$ ，含义如题目描述所示。
第二行包含 $N+1$ 个实数，从高到低依次表示该 $N$ 次函数各项的系数。
1
2
3
样例输入
3 -0.9981 0.5
1 -3 -3 1
输出格
输出为一行，包含一个实数，即为 $x$ 的值。若你的答案与标准答案的相对或绝对误差不超过 $10^{-5}$ 则算正确。
什么是三分法？
三分法类似于二分，原理为不断缩小答案所在的求解区间。
二分缩小区间利用函数的单调性，而三分法利用的则是函数的单峰性。
拿样例来说：$\displaystyle y = x^3 - 3x^2 - 3x + 1$ , $x\in[ -0.9981 , 0.5 ]$， 需要求出它在该区间的最大值 $max$:
将 $[ -0.9981 , 0.5 ]$ 均分为三个区间: $[-0.9981,-0.498]$ , $[-0.498,0.00006]$ , $[0.00006,0.5]$ 。
同时得到了两个点 $m_1$ 和 $m_2$ :
我们把 $m_1$ , $m_2$ 中函数值更大的 $m_1$ 称为好点，较小的 $m_2$ 称为坏点。
那么不难发现，好点 $m_1$ 和极值 $max$ 都在坏点 $m_2$ 的左侧，所以可以将搜索的区间缩小为 $[ -0.9981 , 0.00006 ]$ 。( $0.00006$ 即为 $m_2$ 的横坐标)
这样不断缩小搜索的区间，最终就能够获得一个足够小的区间以至接近一个实数值,以达到求值的目的。
代码实现
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;
}
加一减一的细节要注意
