Module: Ternäre Suche


Problem

1/9

Ternäre Suche: Anfang (C ++)

Theory Click to read/hide

Ternar Suche
Ternar-Suche müssen wir ein Maximum oder ein Minimum einer optimalen Funktion auf dem Schnitt finden.[l, r]♪ Eine optimale Funktion ist, wenn sie ein Extrem auf dem Schnitt hat.
Die Suche nach maximalen Funktionswerten wird häufig zur Optimierung verwendet. Zum Beispiel müssen wir die Möglichste Ecke eines rechteckigen Dreiecks finden, wo die Fläche am größten ist. Das werden wir nehmen. 0 vor 90und auf diesem Schnitt suchen wir nach einem Bereich, der zuerst zunimmt und dann abnimmt, d.h. die Funktion wird uninformiert.
Arbeitsprinzip
Das Prinzip der Arbeit ist ähnlich wie eine Doppelsuche, aber wir haben vielleicht einen Fall, wenn wir auf halbem Weg teilen, wenn wir in der Mitte des Schnittes bis zum Extrem sind, und wir bekommen nicht das Ergebnis.
Um einen solchen Fall zu vermeiden, ist es daher erforderlich, die Schnitte nicht in zwei Teile, sondern auf drei, und den Teil, in dem es keinen Extremisten gibt, zu trennen, usw., bis die Grenzen zu Frucht kommen.

Doppel f( doppelter Hypo, Doppel alpha) {~}
alpha = (alpha *M_PI)/180;
zurück 0.5 * Hypo * Hypo * cos(alpha) * sin(alpha);
♪

int main() {~}
Doppel l = 0;
doppelt r = 90;
Doppel-EPS = 1e-6;
doppelte Hypo = 100;
während (r - l grad= EPS) {
doppelt m1 = l + (r - l) / 3;
doppelt m2 = r - (r - l) / 3;
wenn (f(hypo, m1) PER f(hypo, m2)) {~}
l = m1;
♪
andere
r = m2;
♪
♪

cout Kanal ((l + r) / 2);
Rückkehr 0;
♪

Ternar-Suche kann mitGoldschnittmethodedie die Geschwindigkeit der Bequemlichkeit um etwa zwei Mal erhöht.
Quellen
(1) Thernar-Suche und Goldschnittmethode
(2)Thernar Suche


Problem

Найти минимум функции \(y=x \cdot x - b \cdot x + 100\), где коэффициент b вводится с клавиатуры.
 
Примеры
№ Входные данные Выходные данные
1 10 5


Примечание
Внимательно смотрите, что ваш алгоритм ищет: максимум или минимум.
 

time 1000 ms
memory 256 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>	
#include"math.h"	
using namespace std;

double f( double x, int b) {
// здесь должна быть ваша функция                     
}


int main() {
	double l = -100;
	double r = 100;
	double EPS = 1e-6; 
	int b;
	cin >> b;                
	cout << ((l + r) / 2);
	return 0;
}

     

Program check result

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