三分法求凸性函数极大极小值
直接贴模板,理解很容易,网上的题解一搜便是。
唉,贴一个大佬吧:http://blog.csdn.net/pi9nc/article/details/9666627
模板(上凸函数模板):
const double eps = 1e-6;
double Calc(double k)
{
return ...(计算表达式);
}
double SanFen(double l, double r)
{
double mid, mmid;
while(r-l > eps)
{
mid = (r+l)/2.0;
mmid = (mid+r)/2.0;
if(Calc(mid) > Calc(mmid)) r = mmid;
else l = mid;
}
return r;
}
再给一个模板例题ZOJ-3203
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;
const double eps = 1e-6;
double H, h, D;
double Calc(double x){
double ans = h*x/(H-h);
if(ans+x > D){
double g = ans+x-D;
ans = ans - g + g*(H-h)/x;
}
return ans;
}
double SanFen(double l, double r)
{
double mid, mmid;
while(r-l < eps)
{
mid = (r+l)/2.0;
mmid = (mid+r)/2.0;
if(Calc(mid) > Calc(mmid)) r = mmid;
else l = mid;
}
return r;
}
int main(){
int t;
cin >> t;
while(t--){
scanf("%lf %lf %lf", &H, &h, &D);
double id = SanFen(0, D);
printf("%.3f\n", Calc(id));
}
return 0;
}
继续加油~