Module: Binäre Suche nach einer monotonen Funktion


Problem

1/5

Binäre Suche nach einer monotonen Funktion

Theory Click to read/hide

Die Doppelsuche kann nicht nur zur Suche nach den Elementen in der Masse, sondern auch zur Suche nach den Wurzeln der Gleichungen und den Werten monotoner (Wachstum oder äußerer) Funktionen verwendet werden.

Lassen Sie uns eine monotone Funktion haben. f und so was C diese Funktion. Die Bedeutung des Arguments ist erforderlich. x Diese Funktion ist: - Ja.♪
Beispiel für eine wachsende monotone Funktion:


Wir wählen Grenzen, wenn der Wert der Funktion genau größer und kleiner als der zugewiesene Wert ist. Wir holen die Bedeutung mitten in diesem Schnitt. Wenn es weniger als die beabsichtigte ist, bewegen wir die linke Linie in die Mitte des Schnittes. Sonst bewegen wir die richtige Linie. Dann wiederholen wir den Verengungsprozess. Aber das Problem ist, wenn Sie aufhören zu suchen. DetailsHier.♪
Zum Beispiel betrachten wir die Aufgabe, eine Quadratwurzel der Zahl zu finden x♪ Quadratische Wurzel x (bezeichnet) - Ja.) diese Nummer genannt y♪ ?♪
Für diese Stoffnummer x (seufzt)- Ja.c) Eine Quadratwurzel mit einer Genauigkeit von mindestens 5 Markierungen nach dem Punkt zu finden.


Auswahl der Grenze zur Suche

Da wir die Unendlichkeit der Zahlen nicht überprüfen können, müssen wir die Grenzen der Wurzelsuche definieren. Zuerst finden wir die linke Linie, wir wählen einen beliebigen negativen Punkt (z.B.: -1). Wir verdoppeln es, solange es wichtiger ist. Um die richtige Linie zu finden, wählen wir einen beliebigen positiven Punkt (z.B. (1)). Wir werden es verdoppeln, solange der Wert der Funktion an diesem Punkt geringer ist als der beabsichtigte.


Entweder wenn wir genau die Grenzen der Suche kennen, können wir die linke Linie 1 und die oberste Nummer selbst nehmen. x♪
Danach teilen wir die Stromschnitte in der Hälfte, bauen wir den Mittelquare und wenn es mehr x ist, ersetzen wir den oberen Rand, ansonsten tiefer.
Ergebnis:

Wo,
eps - die Präzision, mit der eine Lösung gefunden werden soll,
x eine bestimmte Zahl, deren Quadratwurzel gesucht wird,
m - Nummer, wo der Algorithmus gespeichert wird Ergebnis♪

Problem

Дано натуральное число x. Вычислите кубический корень из числа.
 
Входные данные
Число x – натуральное, не превосходящее \(10^6\).
 
Выходные данные
Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.

 

Примеры
№ Входные данные Выходные данные
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!