[ 三分法 ] 单峰(单谷)函数 三分找极点

https://www.luogu.org/problemnew/show/P3382
题目描述
如题,给出一个N次函数,保证在范围[l,r]内存在一点x,使得[l,x]上单调增,[x,r]上单调减。试求出x的值。

输入输出格式
输入格式:
第一行一次包含一个正整数N和两个实数l、r,含义如题目描述所示。

第二行包含N+1个实数,从高到低依次表示该N次函数各项的系数。

输出格式:
输出为一行,包含一个实数,即为x的值。四舍五入保留5位小数。

原理简单,且适用于所有在定义域中单调性只改变一次的函数,
就是比较定义域中的两个三等分点的映射值,若左边的三等分点比较大,则将右边界右移,对于左边界同理,最终不断逼近得到单峰的位置。
三等分点怎么求,左边界右边三分之一的区间长度和右边界左边三分之一的区间长度。

三分法

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> P;

const int maxn = 100000 + 5 ;
const int INF = 0x3f3f3f3f ;
const int mod = 9901 ;
const double eps = 1e-6;

int n;
double a[25];

double fun(double x) {
	double res = 0;
	for(int i = 0; i <= n; i++)
		res = res * x + a[i];
	return res;
}

signed main() {
	// fastio;
	double l, r, midl, midr;
	cin >> n >> l >> r;

	for(int i = 0; i <= n; i++)
		cin >> a[i];

	while(r - l > eps) {
		double d = (r - l) / 3.0;
		midl = (l + d), midr = (r - d);

		if(fun(midl) > fun(midr))
			r = midr;
		else
			l = midl;
	}
	printf("%.5lf\n", l);
	return 0;
}

求导二分

当然 由于这道题是多项式给的好 所以 幂函数求导 然后二分 求导是0的点必然对于这个单峰函数来说是极点

导数的函数对应的值表示每一点的切线斜率,所以当该点的导数值大于0则单调增,小于零则单调减,所以只需判断是否大于零即可。
缺点,如果换一道题不是多项式函数的话就不能用这个求单峰了。

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> P;

const int maxn = 100000 + 5 ;
const int INF = 0x3f3f3f3f ;
const int mod = 9901 ;
const double eps = 1e-6;

int n;
double a[25];

double fun(double x) {
	double res = 0;
	for(int i = 0; i < n; i++) // 常数项 消失 求导完 
		res = res * x + a[i];
	return res;
}

signed main() {
	// fastio;
	double l, r, midl, midr;
	cin >> n >> l >> r;

	for(int i = 0; i <= n; i++)
		cin >> a[i], a[i] *= (n-i);

	while(r - l > eps) {
		double mid = (r + l) / 2.0;

		if(fun(mid) > 0)
			l = mid;
		else
			r = mid;
	}
	printf("%.5lf\n", l);
	return 0;
}
全部评论

相关推荐

不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
你找工作的时候用AI吗?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务