Module: 단조 함수에 대한 이진 검색


Problem

1/5

단조 함수에 대한 이진 검색

Theory Click to read/hide

이진 검색은 배열의 요소를 찾는 것뿐만 아니라 방정식의 근과 단조(증가 또는 감소) 함수의 값을 찾는 데에도 사용할 수 있습니다.

단조 함수 f와 이 함수의 일부 값 C가 주어집니다. \(f(x)=C\)와 같은 이 함수의 x 인수 값을 찾습니다.
 
증가하는 단조 함수의 예:


함수의 값이 주어진 값보다 정확히 크고 정확히 작은 경계를 선택합니다. 이 세그먼트의 중간에 있는 값을 선택하겠습니다. 주어진 것보다 작으면 왼쪽 테두리를 세그먼트 중앙으로 이동합니다. 그렇지 않으면 오른쪽 경계를 이동합니다. 다음으로 경계를 좁히는 과정을 반복합니다. 그러나 문제는 언제 검색을 중지해야 하는가입니다. 자세히 알아보기여기.
 
예를 들어, 숫자 x의 제곱근을 찾는 문제를 생각해 보십시오. x(\(\sqrt x\)로 표시됨)의 제곱근은 다음과 같은 숫자 y입니다. < span class="math-tex">\(y^2 = x\).
다음과 같이 문제를 공식화해 봅시다. 주어진 실수 x(\(x >= 1\))에 대해 점 뒤 5자 이상의 정확도를 가진 제곱근.
 


검색할 세그먼트의 테두리 선택

숫자의 전체 무한대를 확인할 수 없기 때문에 루트 검색의 경계를 정의해야 합니다. 먼저 왼쪽 테두리를 찾아 임의의 음수 점(예: -1)을 선택합니다. 그 값이 주어진 값보다 클 때까지 두 배로 늘릴 것입니다. 올바른 경계를 찾기 위해 임의의 양수 지점(예: 1)을 선택합니다. 이 시점에서 함수의 값이 지정된 값보다 작을 때까지 두 배로 합니다.


또는 검색의 경계를 정확히 알고 있는 경우 왼쪽 경계로 1을 사용하고 숫자 자체를 x로 사용할 수 있습니다.
그 후 현재 세그먼트를 반으로 나누고 가운데를 제곱하고 x보다 크면 윗면을 교체하고 그렇지 않으면  바닥.
 
최종 구현:

여기서
eps - 솔루션을 찾아야 하는 정확도
x - 우리가 찾고 있는 제곱근의 주어진 숫자,
m - 알고리즘이 실행된 후 결과가 저장될 숫자입니다.
 

Problem

자연수 x가 주어집니다. 숫자의 세제곱근을 계산합니다.
 
입력
숫자 x – 자연스럽고 \(10^6\)를 초과하지 않습니다.
 
출력
프로그램은 소수점 이하 6자리 이상의 정확도로 문제에 대한 답인 단일 숫자를 표시해야 합니다.

 

예
<헤드> <일># <몸>

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

Teacher commentary

Insert the missing code snippets
C++
입력 출력
1 2 1.259921
Write the program below 
#include <iostream>
using namespace std;

double Search_Binary(int x)
{           
	
}

int main()
{
	
	int x;
	cin >> x;
	
	double res = Search_Binary(x);
	printf("%.8lf", res);


}

     

Program check result

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