用于找函数极值的三分法

Source
版权声明:转载请注明原出处啦QAQ(虽然应该也没人转载): https://blog.csdn.net/hzk_cpp/article/details/86764148

一.算法引入.

三分算法用于一类求单峰函数极值的峰值,而且设峰值为 x x ,则 [ l , x ] [l,x] [ x , r ] [x,r] 要严格单调才能求极值的算法.

这种算法与二分类似,时间复杂度为 O ( 2 l o g 3 n ) O(2log_3n) ,而且通常比二分的常数大,一般效果不如二分好.


二.算法流程.

这种算法主要与二分类似,维护一个区间 [ l , r ] [l,r] ,每次取出 l m i d lmid r m i d rmid 这两个三等分点,我们就可以每次都判断出我们要的答案肯定不在 [ l , l m i d ] [l,lmid] 或者 [ r m i d , r ] [rmid,r] ,然后就可以将区间缩小到原来的 2 3 \frac{2}{3} ,从而做到的时间复杂度 O ( 2 l o g 3 n ) O(2log_3n) .

貌似能写的也就这么多了,反正这个东西与二分差不多,就是取区间的分类讨论多了点…


三.例题与代码.

题目:luogu3382.

一般来说精度要求为 x x 位的话,我们把eps设为 x + 2 x+2 位就可以了.

代码如下:

#include<bits/stdc++.h>
  using namespace std;

#define Abigail inline void
typedef long long LL;

const int N=20;
const double eps=0.0000001;

int n;
double l,r,lm,rm,f[N+9];

double check(double x){
  double ans=0,now=1;
  for (int i=0;i<=n;++i)
    ans+=f[i]*now,now*=x;
  return ans;
}

Abigail into(){
  scanf("%d%lf%lf",&n,&l,&r);
  for (int i=n;i>=0;--i)
    scanf("%lf",&f[i]);
}

Abigail work(){
  double tmp;
  while (r-l>eps){
    tmp=(r-l)/3.0;
    lm=l+tmp;rm=r-tmp;
    check(lm)<check(rm)?l=lm:r=rm;
  }
}

Abigail outo(){
  printf("%.5lf\n",l);
}

int main(){
  into();
  work();
  outo();
  return 0;
}