Module: 三元搜索


Problem

1/9

三元搜索:开始 (C++)

Theory Click to read/hide

三元搜索
我们需要三元搜索来找到线段上单峰函数的最大值或最小值 [l, r]。当一个函数在一段上有一个极值时,它是单峰的。
寻找函数的最大值通常用于优化问题。例如,我们需要找到直角三角形的最大可能角,在该角处面积最大。 为此,我们将遍历从 090 的角度,并且在该段上我们正在寻找一个先增加然后减少的区域,即该函数将是单峰的。
 
工作原理
运行原理类似于二分查找,但是我们可能会遇到这样的情况,将线段一分为二,线段的中间正好落在极值上, 我们不会得到明确的结果。
因此,为了避免这种情况,需要将线段不是分成两部分,而是分成三部分,并丢弃没有极值的部分等,直到边界收敛于结果。

双 f(双低,双阿尔法){     alpha = (alpha *M_PI)/180;     return 0.5 * hypo * hypo * cos(alpha) * sin(alpha); } 诠释主要(){     双 l = 0;     双 r = 90;     双倍 EPS = 1e-6;     双低 = 100;     while (r - l >=EPS) {         双 m1 = l + (r - l) / 3;         双 m2 = r - (r - l) / 3;         if (f(hypo, m1) < f(hypo, m2)) {             l=m1;         }         否则{             r=m2;         }     }          出<< ((l + r) / 2);     返回0; }
可以使用  黄金分割法,这将收敛速度提高了大约 2 倍。
 
来源
1)  三元搜索和黄金比例
2)  三元搜索


 

Problem

找到 \(y=x \cdot x - b \cdot x + 100\) 函数的最小值,其中系数 b 是从键盘输入。< br />  
例子
<头> <日># <正文>


注意
请注意您的算法正在寻找什么:最大值或最小值。
 
输入 输出
1 10 5
Write the program below
#include<iostream>	
#include"math.h"	
using namespace std;

double f( double x, int b) {
// здесь должна быть ваша функция                     
}


int main() {
	double l = -100;
	double r = 100;
	double EPS = 1e-6; 
	int b;
	cin >> b;                
	cout << ((l + r) / 2);
	return 0;
}                     

     

Program check result

To check the solution of the problem, you need to register or log in!