首页 > 代码库 > 三分法
三分法
区别于二分法 ， 二分法只适用于单调函数 （在一个单调的序列中对某一个元素进行查找）
三分法 突破了这种限制 ， 可以用于凸函数或凹函数 ， 这是因为凸函数或凹函数必存在一个最值
三分 顾名思义 要将一个线段分成 3 份 ， 可以以线段 1/3 与 2/3 的位置 作为 3 分的 基准 ，将此函数分为3段 ， 再分别计算 lm 与 lr 所对应的值 ， 将较小的一侧全部舍去 ， 并且重新赋予 left 与 right , 一直重复此过程下去 ， 直到 right - left > 1e-7 。此时被分割的线段可以近似看成一个点 ， 也就是此函数的极值 。
代码示例
double f( int x ) {
return f(x) ; // f(x) 则代表所要三分的函数
}
double sf ( int left , int right ) { // 三分求最大值
double lm , lr ; // 定义两个三分的中间变量
while ( right - left < 1e-7 ) { // 当最三分的线段无线小时 ， 此时近似为一个点 ， 即函数的最值
lm = l + ( right - left ) / 3.0 ; // 选取线段的 1/3 点为一个基准点
lr = r - ( right - left ) / 3.0 ; // 选取线段的 2/3 点为另一个基准点
if ( f(lm) > f(lr) ) right = lr ;
else left = lm ;
}
return left ; // 此时被三分的线段无线小 ， 因此任意返回一个点就行
}
三分法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。