三分法求最大值

"三分法求最大值" 三分法是求解凸性函数的极值问题的一种方法。凸性函数是指函数在定义域内的所有点的函数值都是非负的或非正的函数。三分法是一种分治方法，适用于求解凸性函数的极值问题。 三分法的基本思想是将函数的定义域分为两个部分，分别计算两个部分的函数值，然后根据函数值的大小关系来确定极值点的位置。具体来说，三分法的步骤如下： 1. 初始化左边界 Left 和右边界 Right，通常取函数的定义域的最小值和最大值。 2. 计算中点 mid = (Left + Right) / 2 和 midmid = (mid + Right) / 2。 3. 计算 mid 和 midmid 两个点的函数值 mid_value 和 midmid_value。 4. 如果 mid_value >= midmid_value，则 Right = midmid，否则 Left = mid。 5. 重复步骤 2-4，直到 Left + EPS < Right，EPS 是一个很小的正数。 三分法的优点是计算速度快、精度高，适用于求解凸性函数的极值问题。下面通过几个具体的 OJ 题目来分析三分法的具体实现。 buaa 1033 Easy Problem：在一条线段上找到一点，与给定的 P 点距离最小。这个问题可以用三分法来解决。Calc 函数即为求某点到 P 点的距离。 ZOJ 3203 Light Bulb：人左右走动，求影子 L 的最长长度。这个问题也可以用三分法来解决。Calc 函数即为求影子 L 的长度。 heru 5081 Turn the corner：汽车拐弯问题，给定 X, Y, l, d 判断是否能够拐弯。这个问题可以用三分法来解决。Calc 函数需要比较繁琐的推倒公式。 POJ 3301 Texas Trip：给定 n(n <= 30)个点，求出饱含这些点的面积最小的正方形。这个问题可以用三分法来解决。Calc 函数即为求出饱含这些点的面积最小的正方形的边长。 三分法是一种非常有用的方法，适用于求解凸性函数的极值问题。它的优点是计算速度快、精度高，适用于各种实际问题。