Selektion < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:40 Sa 31.05.2008 | | Autor: | Wimme |
| Aufgabe | Bestimmen Sie das zweitkleinste Elemente einer Folge von n nicht sortierten Integer Zahlen.
Im Worst Case sollen dabei [mm] n+log_2{n} [/mm] -2 (beim log obere Gauß-Klammer) Vergleiche benötigt werden.
|
Hallo!
Das ganze soll eine Erweiterung für ein Verfahren sein, das kleineste Element einer Liste zu finden.
Mein dazu gefundenes Verfahren, dass n-1 Vergleiche brauchen soll und jedes Element maximal (obere Gaußklammer) [mm] log_2{n} [/mm] vergleichen soll:
Teile Folge in Folge von 2-er Paketen. Nimm von allen 2-er Paketen nur die kleinsten mit in die nächste Ebene etc bis nur noch ein 2-er Paket übrig bleibt. Das kleinere der beiden Elemente ist das Minimum.
Wie schaffe ich es jetzt darauf aufbauend das 2.kleinste zu finden? (man beachte die erlaubte Anzahl Vergleiche!).
Das Problem besteht ja darin,dass mein 2.kleinstes Element schon ganz oben verschwinden kann,wenn es neben dem kleinsten steht. Ich nehme an, ich muss irgendwie wieder rekursiv hochsteigen. Dann kann ich ja viele Vergleiche rausschmeißen, weil ich schon oft weiß, dass die Zahlen drüber nur größer sein können.
Aber ich weiß noch nicht so recht, wie ich das gut formulieren kann um alle Fälle abzudecken und so.
Jemand eine Idee?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:55 Sa 31.05.2008 | | Autor: | Gilga |
Komische Aufgabe. Trivial-lösung:
Stack mit maxInteger initialisieren. Vergleiche jedes Element der Folge mit oberstem Stackelement.
Falls Feldelement <= oberstem Stackelement: schmeiß Feldelement auf Stack.
Oberste Stackelement wegwerfen. Ergebnis liegt auf dem Stack
Benötigt n Vergleiche.
Offensichtlich gültig für n>=3
n=2: ein Vergleich => größeres nehmen
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:07 So 01.06.2008 | | Autor: | Wimme |
hi!
Richtig, das funktioniert, baut aber leider nicht auf meinem obigen Verfahren auf, wie es ja in der Aufgabe verlangt wird.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Di 03.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:27 Di 03.06.2008 | | Autor: | Gilga |
Interessante Aufgabe.
Also ich würde den Baum wieder absteigen und dabei ausgehend vom dem min. Element in der Wurzel immer die beiden Söhne des kleinsten Elments betrachten. Eines ist das kleinste Element und das andere ist ein Kandidat für das 2. kleinste. Diese musst du alle durchgehen bis du auf der untersten ebene bist.
...........
hört sich leider recht kompliziert an. .... male es dir auf
|
|
|
|
