三分法的定义

在二分的查找的基础上，在右区间（或左区间）再进行一次二分，这样的查找算法称为三分查找。

三分法的应用场景

03

—

三分法使用要求

无论是二分查找还是三分查找，都需要满足单调性（序列是递增还是递减），如果不满足将不能使用二分/三分。

三分法所面向的搜索序列的要求是：序列为一个凹凸函数。通俗来讲，就是该序列必须有一个最大值（或最小值），在最大值（最小值）的左侧序列，必须满足严格单调递增（递减），右侧序列必须满足严格单调递减（递增）

补充知识

二次函数的基本表示形式为y=ax²+bx+c（a≠0）。二次函数最高次必须为二次， 二次函数的图像是一条对称轴与y轴平行或重合于y轴的抛物线

（当a>0时，开口朝上，拥有最小值）

（当a<0时，开口朝下，拥有最大值）

在教学的过程当中，肯定还有很多小朋友对此不能很好理解，在这里安利一个数学画图网站：https://www.desmos.com/，输入函数表达式即可生成图像，并且改系数即可拥有不同图形效果。

三分查找实现步骤

（1）先取整个区间的中间值mid

mid=(left+right)/2;

（2）再取右侧区间的中间值midmid，从而把区间分为三个小区间。

midmid=(mid+right)/2;

（3）我们mid比midmid更靠近最值，我们就舍弃右区间，否则我们舍弃左区间。

（4）案例实现

#include


using namespace std;


const double eps=10e-9;//对双精度数值来说eps表示从 1.0 到下一个最大双精度数的距离


double f(double x){


return x*x*x-3*x*x-3*x+1;


//凸函数


}


double three(double left,double right){
double mid=0,mmid=0;
while(left+eps mid=(left+right)/2; mmid=(mid+right)/2; if(f(mid)>f(mmid)){ right=mmid; }else{ left=mid; } } return f(mid);//}
int main(){ cout<<three(-0.9981,0.5); return 0; //其输出结果为1.65685 }

以上思路参考了《三分查找》，但也对代码按照我自己的理解，进行了修改，也方便给学生解释。

另外一种取值方法

lmid与rmid的取值：一般可以将这两个点取为[l,r]的三等分点。即

lmid=l+(r-l)/3.0;rmid=r-(l-r)/3.0;

信息学本身是一门比较难的学科，很多学生会因为老师讲的不够详细，不够透彻，而心生怯意。在上课时，喜欢给学生讲多种方法，看他们能够接受哪一种。

案例应用

明明做作业的时候遇到了 n 个二次函数 Si(x)= ax^2 + bx + c，他突发奇想设计了一个新的函数 F(x) = max{Si(x)}, i = 1、2、3、......、 n。明明现在想求这个函数在 [0,1000] 的最小值，要求精确到小数点后四位，四舍五入。

Input

输入包含 T 组数据，每组第一行一个整数 n；接下来 n 行，每行 3 个整数 a, b, c ，用来表示每个二次函数的 3 个系数。

Output

每组数据输出一行，表示新函数 F(x) 的在区间 [0,1000] 上的最小值。精确到小数点后四位，四舍五入。

Sample Input

• 
  2
  
  1
  
  2 0 0
  
  2
  
  2 0 0
  
  2 -4 2
  

• Sample Output

• 
  0.0000
  
  0.5000
  

#includeusing namespace std;const int N=1e5+5;const double inf=1e9;const double eps=1e-9;double a[N],b[N],c[N];int n;
double f(double x){ double mx=eps; for(int i=1;i<=n;i++){ mx=max(mx,a[i]*x*x+b[i]*x+c[i]); } return mx;}
double three(int left,int right){ double l=left,r=right; //第一种写法：// double mid=0,mmid=0;// while(l+eps// mid=(l+r)/2;// mmid=(mid+r)/2;// if(f(mid)>f(mmid)){// l=mid;// }else{// r=mmid;// }// } //第二种写法： double lmid=0,rmid=0; while(l+eps lmid=l+(r-l)/3.0; rmid=r-(l-r)/3.0; //判断lmid,rmid谁离最小值近，画个凹函数图更好理解， if(f(lmid)r=rmid; }else{ l=lmid; } }// return f(mid); return f(l);}
int main(){ int t; cin>>t; while(t--){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]>>c[i]; } printf("%.4lf\n",three(0,1000)); }}

福利分享

（复赛入门提高必背算法模板）

获取方法：vx关注scratch-coco之后，回复“c++”，按照步骤即可领取。