洛谷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 處。