前言

        前面我们已经学习了二分算法。其实，对于一些特定问题，我们还可以使用三分算法。

程序设计思路

        三分，顾名思义，就是把数据分成三段，使用四个指针，其基本方向仍是缩小范围。我们可以重复检查左中指针与右中指针，判断答案在哪一侧，将左指针或右指针移动到中指针，再重新计算左右中指针，实现缩小范围。

        三分算法主要适用于抛物线形函数的求解，因为这类题目一般都是求其在峰上的值。

代码实现

        直接看题目：

        题目要求很清楚：求函数值为峰值时，x的值，看代码——

#include <bits/stdc++.h>

using namespace std;

double n,l,ml,mr,r,iq[13];//l、ml、mr、r分别为左、左中、右中、右指针。iq数组存放系数

double f(double x){//即check，验证函数

	double ans=0;

	for(int i=0;i<=n;i++) ans+=iq[i]*pow(x,n-i);

	return ans;

}

void sett(){//重算左中、右中指针

	ml=l+(r-l)/3;

	mr=l+((r-l)/3)*2;

	return ;

}

int main(){//输入输出，不解释

	scanf("%lf%lf%lf",&n,&l,&r);

	for(int i=0;i<=n;i++) scanf("%lf",&iq[i]);

	while(fabs(l-r)>1e-5){

		sett();

		if(f(ml)>f(mr)) r=mr;

		else l=ml;

	}

	printf("%.5lf",ml);

	return 0;

}

        由此可见，三分实质上就是二分加上了一个指针，从而使答案限制在峰顶，最后求出结果。

结语

        相比于二分，三分的应用场景小了很多。不过对三分的学习，其实也可以当成对二分的复习。我是faryou，再见！

本文链接：https://blog.faryou.eu.org/post/102.html 转载需经作者授权！