Module: Recherche binaire d'une fonction monotone


Problem

1/5

Recherche binaire d'une fonction monotone

Theory Click to read/hide

La recherche binaire peut être utilisée non seulement pour trouver des éléments dans un tableau, mais aussi pour trouver les racines des équations et les valeurs des fonctions monotones (croissantes ou décroissantes).

Donnons-nous une fonction monotone f et une valeur C de cette fonction. Trouvez la valeur de l'argument x de cette fonction, tel que \(f(x)=C\).
 
Exemple de fonction monotone croissante :


Nous choisissons de telles limites où la valeur de la fonction est exactement supérieure et exactement inférieure à la valeur donnée. Choisissons la valeur au milieu de ce segment. S'il est inférieur à celui donné, nous déplaçons la bordure gauche au milieu du segment. Sinon, nous décalerons la bordure droite. Ensuite, nous répétons le processus de réduction des limites. Mais il y a un problème, c'est quand arrêter de chercher. En savoir plusici.
 
Par exemple, considérons le problème de trouver la racine carrée du nombre x. La racine carrée de x (notée par \(\sqrt x\)) est un nombre y tel que < span class="math-tex">\(y^2 = x\).
Formulons le problème comme suit : pour un nombre réel donné x (\(x >= 1\)) trouvez le racine carrée avec une précision d'au moins 5 caractères après le point.
 


Sélection de la bordure du segment pour la recherche

Puisque nous ne pouvons pas vérifier l'infinité des nombres, nous devons définir les limites de la recherche de la racine. Trouvons d'abord la bordure gauche, sélectionnons un point négatif arbitraire (par exemple : -1). Nous le doublerons jusqu'à ce que la valeur qu'il contient soit supérieure à la valeur donnée. Afin de trouver la bonne frontière, on choisit un point positif arbitraire (par exemple : 1). Nous le doublerons jusqu'à ce que la valeur de la fonction à ce stade soit inférieure à celle spécifiée.


Ou, si nous connaissons exactement les limites de la recherche, nous pouvons prendre 1 comme limite gauche, et le nombre lui-même x.
Après cela, nous divisons le segment actuel en deux, équarrissons le milieu, et s'il est supérieur à x, nous remplaçons la face supérieure, sinon  en bas.
 
Mise en œuvre finale :

où,
eps - la précision avec laquelle la solution doit être recherchée,
x - nombre donné dont nous recherchons la racine carrée,
m - le numéro dans lequel le résultat sera stocké après l'exécution de l'algorithme.
 

Problem

Étant donné un nombre naturel x. Calculer la racine cubique d'un nombre.
 
Entrée
Numéro x &ndash ; naturel, ne dépassant pas \(10^6\).
 
Sortie
Le programme doit afficher un seul nombre : la réponse au problème avec une précision d'au moins 6 décimales.

 

Exemples
# Entrée Sortie
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!