Module: Búsqueda binaria de una función monótona


Problem

1/5

Búsqueda binaria de una función monótona

Theory Click to read/hide

La búsqueda binaria se puede utilizar no solo para encontrar elementos en una matriz, sino también para encontrar las raíces de ecuaciones y los valores de funciones monótonas (crecientes o decrecientes).

Nos dan una función monotónica f y algún valor C de esta función. Encuentre el valor del argumento x de esta función, tal que \(f(x)=C\).
 
Ejemplo de una función monótona creciente:


Elegimos esos límites donde el valor de la función es exactamente mayor y exactamente menor que el valor dado. Elijamos el valor en el medio de este segmento. Si es menor que el dado, desplazamos el borde izquierdo al centro del segmento. De lo contrario, desplazaremos el borde derecho. A continuación, repetimos el proceso de estrechar los límites. Pero hay un problema que es cuando dejar de buscar. Leer más aquí.
 
Por ejemplo, considere el problema de encontrar la raíz cuadrada del número x. La raíz cuadrada de x (denotado por \(\sqrt x\)) es un número y tal que < abarcan clase="matemáticas-tex">\(y^2 = x\).
Formulemos el problema de la siguiente manera: para un número real dado x (\(x >= 1\)) encuentre el raíz cuadrada con una precisión de no menos de 5 caracteres después del punto.
 


Seleccionar el borde del segmento para buscar

Ya que no podemos verificar la infinidad de números, necesitamos definir los límites de la búsqueda de la raíz. Primero, busquemos el borde izquierdo, seleccione un punto negativo arbitrario (por ejemplo: -1). Lo duplicaremos hasta que el valor en él sea mayor que el valor dado. Para encontrar el borde derecho, elegimos un punto positivo arbitrario (por ejemplo: 1). Lo duplicaremos hasta que el valor de la función en este punto sea menor que el especificado.


O, si conocemos exactamente los límites de la búsqueda, podemos tomar 1 como el límite izquierdo y el número en sí mismo x.
Después de eso, dividimos el segmento actual por la mitad, elevamos al cuadrado el medio y, si es mayor que x, reemplazamos la cara superior; de lo contrario,  abajo.
 
Implementación final:

donde,
eps - la precisión con la que se debe buscar la solución,
x - número dado cuya raíz cuadrada estamos buscando,
m: el número en el que se almacenará el resultado después de que se ejecute el algoritmo.
 

Problem

Dado un número natural x. Calcula la raíz cúbica de un número.
 
Entrada
Número x – natural, sin exceder \(10^6\).
 
Salida
El programa debe mostrar un solo número: la respuesta al problema con una precisión de al menos 6 decimales.

 

Ejemplos

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++
# Entrada Salida
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!