P3382 【模板】三分

思路

为什么用分治

首先，你不能枚举，因为精度未知 其次，你不能用求根公式，因为次数不定，再者高次方程的求根公式比集成电路还复杂，光是一个三次方程求根公式就能打到手软。

为什么用三分而不是二分

题目有个隐藏条件，那就是该函数次数一定为偶数（奇数次函数在[-inf,inf]区间总是单调递增或单调递减的），也就是说，函数存在一个拐点，若只用二分的话，你无法确定函数处于递增区间还是递减区间。

如何实现

老师讲过了

代码（老师给的）

#include<bits/stdc++.h>
using namespace std;
const double VERY_SMALL=1e-12; 
int n;
double a[16];
double f(double x){
	double s=0;
	for(int i=n;i>=0;i--){
		s=s*x+a[i];
	}
	return s;
}
int main(){
	double L,R;
	cin>>n>>L>>R;
	for(int i=n;i>=0;i--){
		cin>>a[i];
	}
	while(R-L>VERY_SMALL){
		double k=(R-L)/3.00;
		double mid1=L+k,mid2=R-k;
		if(f(mid1)>f(mid2)) R=mid2;
		else L=mid1;
	}
	cout<<L;
	return 0; 
}

二分过法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 510;
int n;
double l,r,mid,eps=1E-10, a[15];
double f(double x){
	double ans=0;
	for(int i=0;i<=n;i++){
		ans=ans*x+a[i];//秦九昭公式求多项式
	}
	return ans;
}

int main(){
	cin>>n>>l>>r;
	for(int i=0;i<=n;i++)	 cin>>a[i];
//	cout<<f(2);
	while(l+eps<r){
		mid=(l+r)/2;
		if(f(mid+eps)-f(mid)>0){//二分+求导lim eps->0 
			l=mid;
		}else{
			r=mid;
		}
	}
	printf("%.5lf", l);
	return 0;
}