Module: 三元搜索


Problem

1/9

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

Theory Click to read/hide

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

双 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 />  
例子
<头> <日># <正文>


注意
请注意您的算法正在寻找什么：最大值或最小值。
 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
输入 输出
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!