CZQ_King
2019-07-31 21:10:00
找单峰函数的峰值有什么用? 怎么找单峰函数的峰值?
别急,让这篇文章来告诉你。
肯定要先听听度娘的解释啦!
单峰函数是在所考虑的区间中只有一个严格局部极大值
( 峰值) 的实值函数。如果函数f(x) 在区间[a, b] 上只有唯一的最大值点C ,而在最大值点C 的左侧,函数单调增加;在点C 的右侧,函数单调减少,则称这个函数为区间[a, b] 上的单峰函数。——百度百科
引用百度的原图大概的说一下:
就是函数
也可以这样解释:
如果
寻找一个单峰函数的峰值有什么用?
本节中以
这里使用
double f(double x){
return pow(x,1/x);
}
最普通的方法肯定是暴力啦!
这个不用说了吧,设置步长,从左到右扫记录最大值。
优点:相对稳定。
缺点:耗时长,精度低。
#include<bits/stdc++.h>
using namespace std;
const int pre=2;//精度可调
int main(){
double p=pow(10,-pre);//计算步长
double l=0,r=10,maxx=-1;//看情况来定maxx的初始值
for(double i=l+pre;i<=r;i+=p)//由于使用x^(1/x)为f函数,所以i不能为0
maxx=max(maxx,f(i));//寻找最大值
cout<<fixed<<setprecision(pre)<<maxx;
}
时间复杂度:
像这种带有单调性的函数,让人不由自主的想起——二分。
但是我们不能只取一个点,因为这是无法得出峰值在哪里的,所以我们需要取两个点,通过比较这两个点来得出峰值的位置。
俩学家阮大佬曾在他的博客中介绍了三分查找,主要是分一半再分一半的思想(
比较
证明在链接里有,这里就照着我的思路再讲一遍吧(其实是差不多的):
当
同样可以证第二个。
既然这样,我们就可以进行三分,每次可以舍去原长度的
那么时间复杂度最优
另外,在链接里有提及到写法,一种是控制迭代次数
,一种是直接控制精度
,接下来的本节的代码都是直接控制精度
。
优点:速度快。
缺点:不稳定。
#include<bits/stdc++.h>
using namespace std;
const int pre=10;//设置精度
int main(){
double p=pow(10,-pre);//计算精度限制
double l=0,r=10,mid,mmid;//初始化
while(r-l>p){
mid=(l+r)/2;//计算mid
mmid=(mid+r)/2;//计算mmid
if(f(mid)-f(mmid)>=0)r=mmid;//大于时舍去右边
if(f(mid)-f(mmid)<=0)l=mid;//小于时舍去左边
}
cout<<fixed<<setprecision(pre)<<max(f(l),f(r));//输出更大的
}
这里有一个问题:
代码中
if(f(mid)-f(mmid)>0)r=mmid;
else l=mid;
为什么要换成
if(f(mid)-f(mmid)>=0)r=mmid;
if(f(mid)-f(mmid)<=0)l=mid;
因为我在测试的过程中,发现若换成带else
的代码,那么当else
后的语句
另外,我们并没有提到过当
然而度娘告诉我们:我们应该“蒙”中间,也就是说把左右都去掉(如图):
于是就有了这样一段代码。
为了让算法变得更稳定,我们可以把这两个点设在三等分处,这样每次都一定会舍弃原长度的
优点:速度快,相对更稳定。
#include<bits/stdc++.h>
using namespace std;
const int pre=10;
int main(){
double p=pow(10,-pre);
double l=0,r=10,m1,m2;
while(r-l>p){
m1=(l+r+l)/3;
m2=(l+r+r)/3;//这两句需要注意!!!
if(f(m1)-f(m2)>=0)r=m2;
if(f(m1)-f(m2)<=0)l=m1;
}
cout<<fixed<<setprecision(pre)<<max(f(l),f(r));
}
在代码中有一处是需要注意的。
千万不要写成m1=(l+r)3和m2=(l+r)2/3!!
很多人认为二分时
这样写是错误的,例如
因为我们截取的是一段,所以原长度的
那为什么二分是
其实也是一样的道理,
我们发现只要
可以想到我们如果把
如图中(
优点:速度比普通三分快
缺点:语言浮点运算误差必须小
#include<bits/stdc++.h>
using namespace std;
const int pre=10;
int main(){
double p=pow(10,-pre);
double l=0,r=10,m;
while(r-l>=p){
m=(l+r)/2;//取中点
if(f(m-p)-f(m+p)>=0)r=m;
if(f(m-p)-f(m+p)<=0)l=m;//比较中点两端
}
cout<<fixed<<setprecision(pre)<<max(f(l),f(r));
}
注意:如果常数
时间复杂度大约是
为什么可以这样做?
如果你学过高中数学,你会知道导数的零点就是原函数的峰值。
因为是单峰,所以只需要找
那么问题就转化成了二分
做法:
首先,你需要先对函数求导。
个人不太支持这种,毕竟复杂的函数很难求导,如果是多项式求导就比较简单一些,直接用幂函数求导公式。
求导后是
优点:用着舒服,基本不会出
缺点:复杂函数难求导
这里给出P3382 【模板】三分法的求导其实是不会)
因为懒,我这里直接放出小黑AWM大佬的题解。
#include<cstdio>
using namespace std;
int n;
double a[20],L,R,k;
double f(double x){
double ans=0;
for(int i=n;i>=1;i--) ans=ans*x+a[i];//常数项没了
return ans;
}
int main(){
scanf("%d%lf%lf",&n,&L,&R);
for(int i=n;i>=0;i--)scanf("%lf",&a[i]),a[i]*=i;//a[i]*=i求导
while(R-L>=1e-6){//二分
double mid=(R+L)/2;
f(mid)>0?L=mid:R=mid;//等价于if(f(mid)>0)L=mid;else R=mid;
}
printf("%.5lf\n",L);//输出答案
return 0;
}
然而这些做法都不能很好地优化。(除了求导二分)
最好的做法是循环利用上一次比较时剩下的点。使一个点被去掉后另一个点正好是下一次比较的其中一个点。这就是
那么这两个点应该取在哪里呢?
直接看P3382的题解你就会发现有很多玄学大法:什么粒子群优化(by yuy_)啊、模拟退火(by Soulist)啊、梯度下降法(by 平衡树森林)啊、甚至还出现了四分(by Youngsc_AFO)。(顺便膜拜这些大佬)
若题目要求多项式的峰值,可以通过秦九韶算法简化多项式,从而使效率更高。
多项式
但是我们学过乘法分配律,你会发现除
在括号内除
以此类推,最后就会变成:
int f(int x){
int ans=0;
for(int i=0;i<=n;i++)
ans+=a[i]*pow(x,i);
return ans;
}//普通算法
int f(int x){
int ans=a[n];
for(int i=n-1;i>=0;i--)ans=ans*x+a[i];
return ans;
}//秦九韶算法
题意:给你一张边长为
我们知道,它的体积是
所以可以用三分,三分
代码:
#include<bits/stdc++.h>
using namespace std;
double n,l,r,m1,m2;
double f(double x){
return x*(n-2*x)*(n-2*x);//返回体积
}
int main(){
cin>>n;
r=n/2.0;//题目说了x<n/2
while(r-l>1e-7){
m1=(l+r+l)/3;
m2=(l+r+r)/3;
if(f(m1)-f(m2)>=0)r=m2;
if(f(m1)-f(m2)<=0)l=m1;
}
cout<<fixed<<setprecision(5)<<f(l)<<" "<<l<<" "<<sqrt(f(l)/l);//a*a*h=f(h)
}
当你测试几个测试点的时候,你就会发现答案似乎是一些循环小数。
确实是这样,这里是公式
正解就有另一种解法:
#include<bits/stdc++.h>
using namespace std;
double n;
int main(){
cin>>n;
cout<<fixed<<setprecision(5)<<2*n*n*n/27<<" "<<n/6<<" "<<2*n/3;//直接套用公式
}
题意:输入圆锥表面积
先证明它是单峰函数(只看正数部分):
圆锥体积公式:
知道这些后,就可以开始三分了。
做法:三分
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<math.h>//poj不给用万能头QAQ
#define M_PI acos(-1)
/*上面这句其实可以不加,因为math.h里有,但如果不加在poj就会CE*/
using namespace std;
double S,V,H;//表面积,体积,高
double f(double R){
H=sqrt((S/(M_PI*R)-R)*(S/(M_PI*R)-R)-R*R);//通过表面积和底面半径算出高
V=M_PI*R*R*H/3;//先存到V里
return V;//返回体积
}
int main(){
while(cin>>S){//有多个数据
double l=0,r=sqrt(S/M_PI),m1,m2,t=50;//初始化
/*因为表面积是πr(r+l)那么r大概就是sqrt(表面积/π)*/
while(t--){//控制迭代次数,50次
m1=(l+l+r)/3;
m2=(l+r+r)/3;
if(f(m1)<f(m2))l=m1;
else r=m2;
/*这部分基本一样*/
}
cout<<fixed<<setprecision(2)<<V<<endl<<H<<endl<<l<<endl;//照题意输出
}
return 0;
}
当然,你也可以三分
其实一般的三分题,只需要:
f(x)
函数就可以轻松
蒟蒻第一次写文章,可能还不够熟练,如果文章有什么问题欢迎各位大佬指正,如果有什么漏掉的也欢迎各位大佬补充!
参考: