三分
- 三分
- 简介+证明
- 模板题1
- 应用
三分
简介+证明
三分算法类似于二分算法，常用于查找元素。
对二分来说，它查找的序列具有单调性（递增或递减），而三分一般则用来查找的数据形状像山峰或山谷的山峰或谷底。（如图）
具体过程和二分差不多。我们先以下图的山峰找山顶为例（山顶为唯一最大元素）。确定 L 和 R （两个不相等的实数 L 为左边界，R 为右边界）后，首先找到 mid1 和 mid2 其中mid1 = (R+L)/2， mid2 = (mid1+R)/2，也就是说 mid1 是 L 和 R 的中点，mid2 是 mid1 和 R 的中点。
下一步，看看 mid1 和 mid2 处的元素大小与它们位置的关系。（设 f(x) 为第 x 个元素的大小）。
假设 f(mid1) > f(mid2) 。
若两点在同侧
那么在山顶的左侧时，mid1 > mid2，在右侧时 mid1 < mid2。很显然，我们的 mid1 固然小于 mid2，所以不可能同在左侧。只可能同在右侧。
若两点在异侧
由于 mid1 必定小于 mid2 ，所以异侧的情况，下 mid1 肯定在左侧，mid2 则在右侧。
所以，在 f(mid1) > f(mid2) 的情况下，我们可以肯定，mid2 肯定在山顶右侧，所以 R 到 mid2 这一段都不可能是山顶，所以我们的 R 可以直接缩到 mid2 的位置。
如果 f(mid1) < f(mid2)
若两点在同侧
同在山顶的左侧时，mid1 < mid2，在右侧时 mid1 > mid2。符合 mid1 < mid2 条件的成立，两者可能同时在左侧。
若两点在异侧
符合 mid1 < mid2 的就是 mid1 在左，mid2 在右。
所以这种情况下，可以肯定 mid1 必定在山顶左边，所以可以排除 L 到 mid1 这段，把 L 缩到 mid1 的位置。
如果 f(mid1) = f(mid2) 呢？
这种情况异侧比较方便，我们先考虑。
异侧
说明 L 到 mid1 和 mid2 到 R 都不包括山顶。
本应该两边都缩，但为了方便我们只缩一边（当然是跨度大的一边）。
同侧
两者可能在同一个点上，吗？不会的。
若 mid1 = mid2
∵ mid2 = (mid1+R)/2
∴ mid1 = R
∵ mid1 = (R+L)/2
∴ L = R
如果 L = R，说明已经找到了，三分已经停止了！
如果不在同一个点上，任然是 mid1 在左 mid2 在右。
但是究竟跑那边呢？（L 往左缩还是 R 往右缩呢？）
很难判断，所以两侧必须分别不严格单调递增递减。这样同侧就不可能相等了。
来个 小题
模板题1
LG-P3382 【模板】三分法
题目描述
如题，给出一个N次函数，保证在范围[l,r]内存在一点x，使得[l,x]上单调增，[x,r]上单调减。试求出x的值。
输入格式：
第一行一次包含一个正整数N和两个实数l、r，含义如题目描述所示。
第二行包含N+1个实数，从高到低依次表示该N次函数各项的系数。
输出格式：
输出为一行，包含一个实数，即为x的值。四舍五入保留5位小数。
输入样例：
3 -0.9981 0.5
1 -3 -3 1
输出样例：
-0.41421
说明
**时空限制：**50ms,128M
数据规模：
**对于100%的数据：**7<=N<=13
样例说明：
如图所示，红色段即为该函数f(x)=x^3-3x^2-3x+1在区间[-0.9981,0.5]上的图像。
当x=-0.41421时图像位于最高点，故此时函数在[l,x]上单调增，[x,r]上单调减，故x=-0.41421，输出-0.41421。
（Tip.l&r的范围并不是非常大ww不会超过一位数）
代码（C++）
#include<cstdio>
#include<cstring>
#include<iOStream>
#include<algorithm>
using namespace std;
int n;
double L,R,a[25];
double qsm(double a,int b)
{
double s=1;
for (;b;b>>=1) if (b&1) s*=a,a*=a;else a*=a;
return s;
}
double F(double x)
{
double ans=0;
for (int i=n;i>=0;i--) ans+=qsm(x,i)*a[i];
return ans;
}
double fin(double L,double R)
{
double mid,mmid;
while (R-L>=1e-15)
{
mid=(R+L)/2,mmid=(mid+R)/2;
if (F(mid)<=F(mmid)) L=mid;else R=mmid;
}
return R;
}
int main()
{
scanf("%d%lf%lf",&n,&L,&R);
for (int i=n;i>=0;i--) scanf("%lf",a+i);
printf("%.5lf",fin(L,R));
return 0;
}
应用
//未来更新
相关阅读
A5创业网（公众号：iadmin5）12月20日报道，近日，有媒体爆出美团将进行裁员，对此美团表示，网传大规模裁员为不实消息，目前美团在职应届生近两
iPhone怎么找回通讯录？手机通讯录里往往保存着很多的联系人，可能我们已经很久联系对方，对于不常联系的还会选择性的删除。但是在紧急
计算用户/物品相似度，以相似度作为权重，对不同物品进行评分预测，从而实现物品。什么是协同过滤先举个生活中的场景，你想听歌却不知道
三分钟掌握位运算符——与（&）、非（~）、或（|）、异或（^）
位运算符的计算主要用在二进制中。实际开发中也经常会遇到需要用到这些运算符的时候，同时这些运算符也被作为基础的面试笔试题。所
如今的互联网保险无疑是互联网金融领域最靓丽的风景之一，据《2016年互联网保险行业研究报告》显示，2015年，互联网保险整体保费规模达