Module: 삼항 검색


Problem

1/9

삼항 검색: 시작(C++)

Theory Click to read/hide

3항 검색
[l, r] 세그먼트에서 단봉 함수의 최대값 또는 최소값을 찾으려면 삼항 검색이 필요합니다. 세그먼트에 하나의 극값이 있을 때 함수는 단봉입니다.
함수의 최대 값 검색은 최적화 문제에 자주 사용됩니다. 예를 들어, 우리는 면적이 가장 큰 직각 삼각형의 가능한 최대 각도를 찾아야 합니다.  이를 위해 0에서 90까지의 각도를 살펴보고 이 세그먼트에서 먼저 증가한 다음 감소하는 영역, 즉 함수는 단봉이 됩니다.
 
작동 방식
동작 원리는 이진 검색과 유사하지만 세그먼트를 반으로 나눌 때 세그먼트의 중간이 정확히 극값에 해당하는 경우 & nbsp; 명확한 결과를 얻지 못할 것입니다.
따라서 이러한 경우를 피하기 위해서는 세그먼트를 두 부분이 아닌 세 부분으로 나눌 필요가 있으며, 결과에 경계가 수렴될 때까지 극값이 없는 부분 등을 버립니다.

이중 f( 이중 하이포, 이중 알파 ) {    알파 = (알파 *M_PI)/180;     return 0.5 * 하이포 * 하이포 * cos(알파) * sin(알파); } 정수 메인() {    더블 l = 0;    이중 r = 90;    더블 EPS = 1e-6;    이중 하이포 = 100;     동안 (r - l >=EPS) {        더블 m1 = 1 + (r - 1) / 3;        더블 m2 = r - (r - l) / 3;         if (f(하이포, m1) < f(하이포, m2)) {            l=m1;         }         다른 {             r=m2;         }     }          out<< ((1 + 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!