《算法竞赛》题解---三分

三分法

模板三分法

#include<bits/stdc++.h>
#define eps 1e-8//或者 const double eps=1e-8;--主要是double
using namespace std;
int n;
double a[15],l,r;
double check(double x)
{
	double ans = 0;
	for(int i=n;i>=0;i--)
		ans=ans*x+a[i];//秦九韶公式
	return ans;
}
 
int main()
{
    //ios::sync_with_stdio(false);cin.tie();cout.tie();
   scanf("%d",&n);
	scanf("%lf%lf",&l,&r);
for(int i=n;i>=0;i--)
		scanf("%lf",&a[i]);
	while(r-l>eps)
	{
		double mid1=l+(r-l)/3,mid2=r-(r-l)/3;
		if(check(mid1)>check(mid2))
			r=mid2;
		else 
			l=mid1;
	}
	printf("%.5lf",l);
    return 0;
}