Minimum
-
Hallo!
Ich hab mehrere Werte und ich muss das Minimum der Werte herausfinden, gibt's da eine Funktion oder muss ich das selbst programmieren?
-
Wenn du STL-Container nimmst gibt es da entsprechende Algorithmen.
-
-
Geht das dann einfach mit
min_element(Wert1, Wert2, Wert3,....)
Oder wie?
-
Nein, du musst die Werte so bereitstellen das du durch diese iterieren kannst.
grüße
-
Ich weiß nicht, ob das das ist, was ich suche.
Ich will ja nur, dass ich z.B. die Werte (8,7,300,655,1000) habe und dann gibt er mir aus der kleinste Wert ist 7.
-
Dann bastel dir halt fix was:
template< typename T > const T &minimum( const T &t1, const T &t2 ) { return t1 < t2 ? t1 : t2; } template< typename T > const T &minimum( const T &t1, const T &t2, const T &t3 ) { return t1 < minimum( t2, t3 ) ? t1 : minimum( t2, t3 ); } template< typename T > const T &minimum( const T &t1, const T &t2, const T &t3, const T &t4 ) { return t1 < minimum( t2, t3, t4 ) ? t1 : minimum( t2, t3, t4 ); }Oder ähnliches...
-
Und diese Werte gibt Du in den Programmcode ein?
-
int x = std::min(std::min(std::min(std::min(8,2), -5), 44), 50);
-
Ja, aber wenn ich z.B. 3000 Werte habe und soll da den geringsten finden, ist es halt nicht mehr fix gebastelt, deshalb frag ich mich ob's da irgendwas gibt.
-
Plotzenhotz schrieb:
int x = std::min(std::min(std::min(std::min(8,2), -5), 44), 50);Wunderschön...
becks schrieb:
Ja, aber wenn ich z.B. 3000 Werte habe und soll da den geringsten finden, ist es halt nicht mehr fix gebastelt, deshalb frag ich mich ob's da irgendwas gibt.
Dann legst du die Werte in einen Container ab und nimmst min_element.
grüße
-
Hmm. Ich habe ja leider (noch) kaum Ahnung von C++, deshalb weiß ich nicht wie ich das mit den Werten ablegen machen soll.
-
Hi!
#include <iostream> #include <vector> #include <algorithm> // ... std::vector< int > container; // Irgendwelche Werte in den Kontainer schieben container.push_back( 50 ); container.push_back( 400 ); container.push_back( 620 ); container.push_back( 20 ); container.push_back( 233 ); std::cout << *std::min_element( container.begin(), container.end() );So ungefähr.
grüße
-
Vielen Dank! Jetzt müsste ich's hinbekommen.
-
Kann ich auch Variablen ablegen?
container.push_back( x );
-
Ja... Aber versuchs doch einfach!
-
Ich würde einfach einen binären Baum nehmen, nach dem Einfügen ist der min. Wert dann im linken Unterbaum, der max. Wert im rechten Unterbaum.
aus http://www.informatiktreff.de/materialien/sek_ii/algorithmen/baum/baum.htm
6. Baumsortieren als Sortierverfahren
Eine Anwendungsmöglichkeit des binären Suchbaums ist es, ihn zum Sortieren einer Feldstruktur zu benutzen. Nehmen wir also an, wir wollten eine Feldstruktur mit den folgenden Werten sortieren:
55 , 14 , 98 , 54 , 17 , 56 , 86 , 87 , 9 , 1 , 45 , 75
Als ersten Schritt erzeugen wir einen leeren Suchbaum.
Als zweiten Schritt sortieren wir die Zahlen der Feldstruktur der Reihe nach in diesen Suchbaum ein, unter Beachtung der für das Einfügen geltenden Bedingungen.
Der nächste Schritt ist dann, die im Suchbaum sortierten Zahlen mit einem geeigneten Durchlauf auszulesen und in die mittlerwelie geleerte Feldstruktur zurückzuschreiben. Ein binärer Suchbaum erfüllt ja die Bedingung, dass im linken Unterbaum eines Knotens niedrigere, im rechten Unterbaum höhere Zahlen stehen als in ihm selbst. Diese Eigenschaft kann man sich mit der Inorder-Traversierung zu nutze machen, da diese dann die Zahlen in der geordneten Reihenfolge ausliest.
Während des Durchlauf muss man nun nur noch die Zahlen in die Feldstruktur kopieren, die danach aufsteigend sortiert ist:
1 , 9 , 14 , 17 , 45 , 54 , 55 , 56 , 75 , 86 , 87 , 98
Weiter Möglichkeit wäre es, die Werte in einen Vector zu packen und ihn dann mit einem Sortieralgo zu sortieren. Der Baum hat den Vorteil, dass die Werte schon beim Einfügen sortiert werden.
-
Wieso würde man einen Baum verwenden wollen wenn man O(N) haben kann?
-
Plotzenhotz schrieb:
Wieso würde man einen Baum verwenden wollen wenn man O(N) haben kann?
Wo hast du O(N)?
Ausserdem ist der Aufwand für das Einfügen in einen Baum O(log n), im schlimmsten Fall O(n).
-
Einmal drüber laufen und das kleinste merken ist Laufzeit O(N), allein den Baum aufzubauen oder zu sortieren kostet O(N log N) Laufzeit. Aber hey, dafür wird ja ein Baum vewendet.
-
Jester schrieb:
Einmal drüber laufen und das kleinste merken ist Laufzeit O(N), allein den Baum aufzubauen oder zu sortieren kostet O(N log N) Laufzeit. Aber hey, dafür wird ja ein Baum vewendet.
Ich glaub du brauchst eine Auffrischung deiner Kenntnisse in Bäumen. Einfügen kostet dich O(log n), nachdem du _alles_ eingefügt hast, ist der Baum sortiert.
Ausserdem was ist wenn er dann das 2. kleinste Element braucht? Nochmal alles durchsuchen?