洛谷P3382 【模板】三分法
三分法求 函数最大值
三分 适用于求凸峰函数 或者凹峰函数
但听dalao说不大适合 /
---
/
这种有平的情况
还有我觉得 f(mid1) == f(mid2 ) 也可特判一下 此时 l = mid1 r = mid2
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 #include <iomanip> 9 using namespace std ; 10 const int maxn = 14 ; 11 const double eps = 1e-7 ; 12 int n ; 13 double k[maxn] ; 14 double l,r,mid1,mid2 ; 15 16 inline double f(double x ) 17 { 18 double ans = 0.0 ; 19 double y = 1 ; 20 for(int i=n+1;i>=1;i--) 21 { 22 ans = ans + k[ i ] * y ; 23 y*=x ; 24 } 25 return ans ; 26 } 27 28 int main() 29 { 30 scanf("%d%lf%lf",&n,&l,&r) ; 31 for(int i=1;i<=n+1;i++) scanf("%lf",&k[ i ]) ; 32 while(abs(r-l)>eps) 33 { 34 mid1 = l+(r-l) / 3 ; 35 mid2 = r-(r-l) / 3 ; 36 if( f(mid1) < f(mid2) ) 37 l = mid1 ; 38 else 39 r = mid2 ; 40 } 41 printf("%.5lf ",l) ; 42 43 return 0 ; 44 }