模板三分法

三等分

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-6;                              //三分的精确度
int n;
double a[15];
double f(double x){                                   //计算函数值
  double s = 0;
  for(int i=n;i>=0;i--) s = s*x + a[i];               //类似递归的方式将mid带入x值
  return s;
}
int main(){
  double L,R; scanf("%d%lf%lf",&n,&L,&R);
  for(int i=n;i>=0;i--) scanf("%lf",&a[i]);
  while(R-L > eps){ // for(int i = 0; i<100; i++){    //用for也行
    double k =(R-L)/3.0;                              //三分
    double mid1 = L+k, mid2 = R-k;                    //中间值设置两个
    if(f(mid1) > f(mid2)) R = mid2;                   //比较两个mid数值，哪个数值高就移动相反的端点，去掉多余区间，逼近峰值
    else L = mid1;
  }
  printf("%.5f\n",L);
  return 0;
}

笔记：三分法每次计算可以减少三分之一的长度，它适合计算单峰函数，通过两个中间值比较确定最终的极值点，根据题目的要求设定好精确度

近似三等分

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
int n; double a[15];
double f(double x){
  double s=0;
  for(int i=n;i>=0;i--) s = s*x + a[i];
  return s;
}
int main(){
  double L,R;
  scanf("%d%lf%lf",&n,&L,&R);
  for(int i=n;i>=0;i--) scanf("%lf",&a[i]);
  while(R-L > eps){                           // for(int i = 0; i<100; i++){ //用for也行
    double mid = L+(R-L)/2;
    if(f(mid - eps) > f(mid)) R = mid;        //mid1和mid2的区间类似窗口锁定了
    else L = mid;
  }
  printf("%.5f\n",L);
  return 0;
}

笔记：近似三等分的计算方式类似二等分，将二分法的mid的点变成一个区间来寻找极值点