洛谷P3382 三分法求极值详解

题目描述

P3382 三分法 要求在给定区间内寻找一个多项式函数的最大值点。题目保证函数在区间内先严格递增后严格递减（单峰函数），适合使用三分法求解。

算法原理

三分法核心思想

对于单峰函数，在区间 $[l,r]$ 内每次选取两个试探点 $mid1$ 和 $mid2$：

• 若 $f(mid1)<f(mid2)$，说明极值点在 $(mid1,r]$ 区间
• 若 $f(mid1)>f(mid2)$，说明极值点在 $[l,mid2)$ 区间
• 通过不断缩小搜索区间，最终逼近极值点

代码解析与优化

原始代码分析

用户提供的代码存在几个可优化点：

1. 变量命名不清晰：esp 数组应命名为 coeff 更直观
2. 精度控制方式：固定比较 mid±0.000001 可能不够灵活
3. 函数返回值设计：fun 函数返回 0/1 的布尔逻辑可优化

优化后代码

#include <bits/stdc++.h>
using namespace std;int N;
double l, r;
double coeff[15] = {0};  // 存储多项式系数// 计算多项式在x处的值
double calculate(double x) {double res = 0.0;double x_pow = 1.0;  // 缓存x的幂次for (int i = 0; i <= N; ++i) {res += coeff[i] * x_pow;x_pow *= x;}return res;
}int main() {cin >> N >> l >> r;for (int i = N; i >= 0; --i) {cin >> coeff[i];  // 系数按降序输入}const double EPS = 1e-7;  // 精度控制while (r - l > EPS) {double mid1 = l + (r - l) / 3;double mid2 = r - (r - l) / 3;if (calculate(mid1) < calculate(mid2)) {l = mid1;} else {r = mid2;}}printf("%.5lf\n", l);return 0;
}

关键优化点说明

1. 函数计算优化：

   • 使用迭代计算代替 pow 函数，避免浮点精度问题
   • 时间复杂度从 O(N^2) 优化到 O(N)

2. 精度控制改进：

   • 引入 EPS 常量统一控制精度
   • 终止条件改为 r - l > EPS，更符合三分法收敛特性

3. 三分点选取策略：

   • 采用经典的三分点选取方式：

     mid1 = l + (r - l)/3
     mid2 = r - (r - l)/3
     

   • 保证每次迭代区间缩小比例恒定

注意事项

1. 单峰性验证：题目保证函数为单峰函数，实际应用中需先验证
2. 端点处理：当极值点恰好位于区间端点时，需额外判断
3. 系数输入顺序：注意题目要求系数按降幂输入（与常规存储方式不同）

复杂度分析

• 时间复杂度：O(N·log(1/ε))，其中 ε 为精度要求
• 空间复杂度：O(N)，仅需存储多项式系数

扩展思考

1. 与二分法的区别：

   • 二分法要求函数单调，三分法要求单峰
   • 三分法每次迭代减少 2/3 的搜索空间

2. 应用场景：

   • 概率分布中的最大似然估计
   • 经济学中的效用最大化问题
   • 工程优化问题中的参数调优

总结

三分法是解决单峰函数极值问题的有效方法，通过不断缩小搜索区间逼近极值点。本题实现时需特别注意：

1. 浮点数计算的精度控制
2. 多项式计算的效率优化
3. 输入输出的格式要求

掌握三分法的实现原理，可以推广到更高维度的优化问题（如网格搜索法），是算法竞赛和工程实践中常用的数值优化技巧。

附：测试样例
输入：
3 -5 5
1 -8 22 -24 8
输出：
3.00000

该样例对应多项式 $f(x)=x^3-8x^2+22x-24x+8$，其极大值点确实在 x=3 处。