2017-08-06 22:47:36
区别于二分法 ， 二分法只适用于单调函数 （在一个单调的序列中对某一个元素进行查找）
三分法 突破了这种限制 ， 可以用于凸函数或凹函数 ， 这是因为凸函数或凹函数必存在一个最值
三分 顾名思义 要将一个线段分成 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 ; // 此时被三分的线段无线小 ， 因此任意返回一个点就行 }
/***********/ 特别注意下 上面的精度控制 right - left > 1e-7 , 1e-7 的精度可能并不符合题目要求 ， 有两种方法解决 ， 一是将精度提升为 1e-10 ， 二是直接三分 100 次函数 。
例题 示例 ： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3203
问题分析 ：
题目所求影子的长度 ， 包括两部分 地上的和墙上的 或者 人较靠左站 ，只在地上有影子 ，想要有最长的影子 ， 显然是考虑人的影子同时出现在墙上和地上的情况 。推导出公式 ， 进而求解 。
代码示例 ：
#include#include using namespace std ;double H , h , d ; double f( double x ) { double ans = ( x - d ) * ( H - h ) * 1.0 / x + h + d - x ; return ans ;}int main ( ) { int t ; double lm , lr ; while ( cin >> t ) { while ( t-- ) { cin >> H >> h >> d ; double l = d * ( H -h ) / H , r = d ; while ( r - l > 1e-9 ) { lm = l + 1.0 / 3 * ( r - l ) ; lr = r - 1.0 / 3 * ( r - l ) ; if ( f(lm) >= f(lr) ) r = lr ; else l = lm ; } printf ( "%.3f\n" , f(lm) ) ; } } return 0 ;}