Algorithmik
-
Hallo liebe Community,
ich dachte mir nach einiger Zeit des Denkens könnte ich hier eine Diskussion starten.
Meine Aufgabe ist einen Algorithmus zu finden der ein Array mit Zahlen durchsucht
dabei eine Kombination von 2 Zahlen findet die genau auf eine Vorgabe passt.
Eigentlich ist das ganze ja gar nicht schwer jedoch habe ich die Vorgabe das
ganze soll in einer Laufzeit von Theta(n log n) passieren.
Einen Algorithmus zu finden der es in n² schafft ist trivial.Hier nochmal die Aufgabenstellung wie ich sie bekommen habe.
Entwickeln Sie einen Algorithmus mit Laufzeit Θ(n log n), der folgende Spezifikation erfüllt:
• Eingabe: a[] = {a 0 , . . . , a n−1 }, s mit a i ∈ Z, s ∈ Z, n ∈ N (n + 1 ganze Zahlen)
• Ausgabe: true, falls es zwei Elemente a i , a j gibt mit s = a i + a j , i 6 = j, false sonst
Implementieren und testen Sie Ihren Algorithmus in C, C++, Java oder C#.Hoffentlich könnt ihr mir Denkanstöße geben.
MfG tt1991
-
Sortieren, dann binäre Suche?
-
Bitte gib dir das nächste Mal etwas mehr Mühe bei der Formatierung. Was "i 6 = j" bedeuten soll, kann man nur raten (i != j?).
Sortieren ist schon mal ne gute Sache. Dann nimmst du zwei Iteratoren. Mit dem einen gehst du von vorne nach hinten und mit dem anderen von hinten nach vorne durch das Array. Je nachdem, ob die Summe der beiden aktuellen Elemente größer oder kleiner als s ist, bewegst du den einen oder anderen Iterator. Die Details solltest du selbst erarbeiten können.
-
Die "weniger schlaue" Lösung wäre die Zahlen einfach alle in eine Map/Hash-Map zu stecken (key = Zahl, value = Index). Das Aufbauen so einer Map ist O(N log N) oder besser, und Lookup ist O(log N) oder besser.
Dann gehst du alle Zahlen durch, und checkst einfach bei jeder mit Hilfe der Map ob du ein Gegenstück dazu hast. Zeit für den Check also insgesamt auch O(N log N).
-
Hallo danke für die Antworten.
Entschuldigung das war copy und paste aus einem PDF.Also ich habe jetzt alles mit Mergesort sortiert und dann bin ich mit einer Binäre Suche vorgegangen, hat geklappt danke für die Denkhilfe.
Denke mal den Code sollte ich nicht posten ist ja eine komplette Lösung, sowas macht man ja nicht in einem Forum einfach die Lösung zu posten oder?
Bin mir da immer nicht ganz sicher.
MfG tt1991
-
tt1991@web.de schrieb:
sowas macht man ja nicht in einem Forum einfach die Lösung zu posten oder?
Doch, schon, vor allem wenn die Lösung in einem 12-seitigen Thread gemeinsam entwickelt wurde. Da freut man sich dann als Helfer ordentlich, wenn was feines dabei rausgekommen ist.
Hier aber den Code nicht posten, bitte. Zu einfaches Copy&Pase für andere mit der selben Aufgabenstellung. Und die diesmal beteiligten Helfer können den Code vermutlich schneller selber einklimpern als fremden Code zu lesen, fürchte ich.
Auf jeden Fall danke für die Rückmeldung, daß es so gut geklappt hat. Das freut.
-
Sehe ich genau so.
