三分算法 —(解决凸凹函数的最值)
转载:https://blog.****.net/pi9nc/article/details/9666627
概念:
在二分查找的基础上,在右区间(或左区间)再进行一次二分,这样的查找算法称为三分查找,也就是三分法。
二分查找所面向的搜索序列的要求是:具有单调性(不一定严格单调);没有单调性的序列不是使用二分查找。
与二分查找不同的是,三分法所面向的搜索序列的要求是:序列为一个凸凹性函数。通俗来讲,就是该序列必须有一个最大(或最小值)。
我们都知道 二分查找 适用于单调函数中逼近求解某点的值。如果遇到凸性或凹形函数时,可以用三分查找求那
个凸点或凹点的近似值。如下图,表示一个有最大值的凸性函数:
如图所示,已知左右端点L、R,要求找到白点的位置。
思路:通过不断缩小 [L,R] 的范围,无限逼近白点。
做法:先取 [L,R] 的中点 mid,再取 [mid,R] 的中点 mmid,通过比较 f(mid) 与 f(mmid) 的大小来缩小范围。
当最后 L=R-1 时,再比较下这两个点的值,我们就找到了答案。
1、当 f(mid) > f(mmid) 的时候,我们可以断定 mmid 一定在白点的右边。
反证法:假设 mmid 在白点的左边,则 mid 也一定在白点的左边,又由 f(mid) > f(mmid) 可推出 mmid < mid,与已知矛盾,故假设不成立。
所以,此时可以将 R = mmid 来缩小范围。
2、当 f(mid) < f(mmid) 的时候,我们可以断定 mid 一定在白点的左边。
反证法:假设 mid 在白点的右边,则 mmid 也一定在白点的右边,又由 f(mid) < f(mmid) 可推出 mid > mmid,与已知矛盾,故假设不成立。
同理,此时可以将 L = mid 来缩小范围。
凸函数最值:
double three_divi(double l,double r)
{
double mid,mmid;
while(r-l>=eps)
{
mid = (l+r)/2;
mmid = (mid+r)/2;
if(cal(mid)>cal(mmid)) //比较函数值
r = mmid;
else
l = mid;
}
return cal(l) > cal(r) ? l : r;
}
凹函数最值:
double three_divi(double l,double r)
{
double mid,mmid;
while(r-l>=eps)
{
mid = (l+r)/2;
mmid = (mid+r)/2;
if(cal(mid)<cal(mmid)) //大于改成小于
r = mmid;
else
l = mid;
}
return cal(l) > cal(r) ? l : r;
}
链接:https://www.nowcoder.com/acm/contest/200/E
来源:牛客网
不难推出公式:(据说根据扔东西常识这是凸函数)
AC代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#define pi acos(-1.0)
#define g 9.80665
using namespace std;
const double eps = 1e-8;
double h,v;
inline double cal(double x)
{
return v*v*sin(2*x)/(2*g)+v*cos(x)*sqrt(v*v*sin(x)*sin(x)+2*g*h)/g;
}
double three_divi(double l,double r)
{
double mid,mmid;
while(r-l>=eps)
{
mid = (l+r)/2;
mmid = (mid+r)/2;
if(cal(mid)>cal(mmid))
r = mmid;
else
l = mid;
}
return cal(l) > cal(r) ? l : r;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>h>>v;
double x = three_divi(0.0,pi/2.0); //角度取值0~pi/2
printf("%.5f\n",cal(x));
}
return 0;
}
(ps:高中物理解法看上一篇 )