三分/优选法(黄金分割法)求单峰函数极值

 给出一个N次函数，保证在范围[l,r]内存在一点x，使得[l,x]上单调增，[x,r]上单调减。试求出x的值。

（此题其实当然可以取导用二分做，但是如果有些函数求导很麻烦的话那就用三分）

三分:
此题根据对称性，在(l,r)中间找两个点l',r'，若f(l')<f(r')那就取(l',r)否则取(l,r')  -----其实可以看成粗糙的取导

double f(double x){//秦九昭
double ans=0,k=1;
FFor(i,n,0)ans+=k*a[i],k*=x;
return ans;
}

普通三分

double work(double l,r){
while(fabs(r-l)>eps){
lm=l+(r-l)/3;
rm=r-(r-l)/3;
if(f(rm)>=f(lm))l=lm;
else r=rm;
}
printf("%.5f",l);

优选法三分：
我看了网上大量博客文章，大多数真心没说到点子上（而且代码也没体现出优化性）
实际上就一句话，普通的三分（或者你随意按其他比例缩小范围）都是每次必须取两个点进行计算f(l+len*w),f(r-len*w)，
但黄金分割法除了第一次取两个点外，以后每次就只需要取一个点就OK了，你说快不快。
如图，红点是必须计算的点，灰点因为上一轮已经计算过，所以此轮就不用计算了，这样就实现了每轮只计算一个点的效果

黄金分割数为 (sqrt(5)-1)/2 就不证明了

上代码：

#define gor (sqrt(5)-1)/2
bool fgl=true,fgr=true;

double gold(double l,r){
while(fabs(r-l)>eps){
double midr=(r-l)*gor+l;
double midl=r-(r-l)*gor;
if(!fgr)fr=f(midr);
if(!fgl)fl=f(midl);
if(fl>fr)
r=midr,fgr=true,fgl=false;
else if(fl<fr)
l=midl,fgl=true,fgr=false;
else 
l=midl,r=midr,fgr=true,fgl=true;
}
return r;
}
printf("%.5f",gold(l,r));