Module: Ricerca binaria di una funzione monotona


Problem

1/5

Ricerca binaria di una funzione monotona

Theory Click to read/hide

La ricerca binaria può essere utilizzata non solo per trovare elementi in un array, ma anche per trovare le radici di equazioni e i valori di funzioni monotone (crescenti o decrescenti).

Diamoci una funzione monotona f e qualche valore C di questa funzione. Trova il valore dell'argomento x di questa funzione, in modo tale che \(f(x)=C\).
 
Esempio di funzione monotona crescente:


Scegliamo tali limiti in cui il valore della funzione è esattamente maggiore ed esattamente minore del valore dato. Scegliamo il valore al centro di questo segmento. Se è inferiore a quello dato, spostiamo il bordo sinistro al centro del segmento. Altrimenti, sposteremo il bordo destro. Successivamente, ripetiamo il processo di restringimento dei confini. Ma c'è un problema è quando smettere di cercare. Ulteriori informazioni qui.
 
Ad esempio, considera il problema di trovare la radice quadrata del numero x. La radice quadrata di x (indicata da \(\sqrt x\)) è un numero y tale che < span class="math-tex">\(y^2 = x\).
Formuliamo il problema come segue: per un dato numero reale x (\(x >= 1\)) trova il radice quadrata con una precisione non inferiore a 5 caratteri dopo il punto.
 


Selezione del bordo del segmento per la ricerca

Poiché non possiamo controllare l'intera infinità di numeri, dobbiamo definire i confini della ricerca della radice. Innanzitutto, troviamo il bordo sinistro, selezioniamo un punto negativo arbitrario (ad esempio: -1). Lo raddoppieremo finché il valore in esso contenuto non sarà maggiore del valore dato. Per trovare il confine giusto, scegliamo un punto positivo arbitrario (ad esempio: 1). Lo raddoppieremo finché il valore della funzione a questo punto non sarà inferiore a quello specificato.


Oppure, se conosciamo esattamente i confini della ricerca, possiamo prendere 1 come limite sinistro e il numero stesso x.
Successivamente, dividiamo il segmento corrente a metà, quadratiamo il centro e, se è maggiore di x, sostituiamo la faccia superiore, altrimenti  inferiore.
 
Implementazione finale:

dove,
eps - l'accuratezza a cui deve essere cercata la soluzione,
x - dato il numero di cui stiamo cercando la radice quadrata,
m - il numero in cui verrà memorizzato il risultato dopo l'esecuzione dell'algoritmo.
 

Problem

Dato un numero naturale x. Calcola la radice cubica di un numero.
 
Input
Numero x – naturale, non superiore a \(10^6\).
 
Uscita
Il programma dovrebbe visualizzare un solo numero: la risposta al problema con una precisione di almeno 6 cifre decimali.

 

Esempi
# Input Uscita
1 2 1.259921

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++
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!