Sort. v. Schrauben und Muttern < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:02 Fr 11.11.2011 | | Autor: | Physy |
| Aufgabe | Gegeben seien ein Haufen von n Schrauben unterschiedlicher Weite und ein weiterer Haufen mit den n dazu passenden Muttern. Pro Schritt ist es möglich, eine Mutter mit einer Schraube zu vergleichen und dabei die Information zu erhalten, ob die Schraube passt, zu groß ist oder aber zu klein.
Beachten Sie: es sind keine Vergleiche zwischen unterschiedlichen Muttern erlaubt, und ebenso keine Vergleiche zwischen unterschiedlichen Schrauben! Gezählt werden im Folgenden die Schrauben-Muttern-Vergleiche.
(a) Beschreiben Sie einen Algorithmus, der die kleinste Mutter und die dazu passende Schraube
mit maximal 2n Vergleichen findet (es geht sogar mit nur 2n-2 Vergleichen).
(b) Nun soll zu jeder Schraube die passende Mutter gefunden werden. Geben Sie einen Algorithmus an, der dieses Problem in durchschnittlich O(n * log n) Vergleichen löst (Hinweis: Modifizieren
Sie den Quicksort-Algorithmus). |
Ich komme mit dieser Aufgabe leider gerade gar nicht klar und grübele schon seit geraumer Zeit. Hat jemand eine Idee, wie man das machen könnte?
Gruß
|
|
| |
|
Naja wie würdest du das Problem denn angehen, wenn diese Haufen vor dir liegen würden?
Das was du dann tust, musst du nur noch in Maschinensprache übersetzen. Weiß jetzt nicht, ob ihr da eine bestimmte oder nur Pseudocode braucht.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:38 Fr 11.11.2011 | | Autor: | Physy |
Ich würde wahrscheinlich alles durchvergleichen und eine Laufzeit von [mm] n^2 [/mm] haben :) Ich vermute mal wir brauchen Pseudocode aber da bin ich mir nicht sicher. Mir geht es aber auch nur um irgendeine Grundidee :(
Gruß
|
|
|
| |
|
Du hast doch schon eine Grundidee, du musst nur mal genauer aufschreiben, wie(!) du alles vergleichen würdest. Dann kann man dir auch helfen bzw. sagen, ob es falsch ist oder nicht. Wie willst du z.B. auf [mm] $n^2$ [/mm] kommen?
Wieviele Vergleiche brauchst du denn, um die kleinste Mutter zu finden? Fangen wir mal damit an.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:14 Fr 11.11.2011 | | Autor: | Physy |
Mit einer verschachtelten for-Schleife aber das wäre ja eine Laufzeit von [mm] n^2, [/mm] wie gesagt ...
Ich wüsste sonst nicht, wie ich auf das kleisnte Paar kommen kann...
|
|
|
| |
|
Ok, die Version ist brute-force. Durch die lineare Laufzeit ist dein Hypothesenraum aber schon ganz gut eingeschränkt und sollte dir so ungefährt vermitteln, in welche Richtung du suchen sollst. Du kannst z.B. jede Menge Vergleiche sparen, indem du die Information deiner Vergleiche besser nutzt. Was weisst du denn z.B. wenn du eine Mutter mit einer Schraube vergleichst und letztere kleiner ist als die Mutter?
Hast du dir mal ein paar Beispiele mit wenigen Elementen aufgemalt?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 03:08 Sa 12.11.2011 | | Autor: | Physy |
Ja, schon x-mal aber ich komme einfach auf keine Lösung. Die Aufgabe bringt mich noch zum verzweifeln. Ich weiß nicht, wie ich diese Information sinnvoll nutzen kann ...
|
|
|
| |
|
Du suchst die kleinste Mutter und die zu ihr passende kleinste Schraube, was muss für diese kleinste Mutter im Vergleich zu allen Schrauben gelten und was gilt umgekehrt für die kleinste Schraube im Vergleich zu allen Muttern?
Was weisst du jetzt über eine Mutter wenn du sie mit einer kleineren Schraube vergleichst?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:04 Mo 14.11.2011 | | Autor: | Physy |
Mir ist klar, dass ich immer eine Mutter und eine Schraube pro Abfrage ausschließen kann, wenn der Vergleich ein echtes größer oder ein echtes kleiner liefert. Aber was fange ich mit einem ist gleich Ergebnis an?
|
|
|
| |
|
> Mir ist klar, dass ich immer eine Mutter und eine Schraube
> pro Abfrage ausschließen kann, wenn der Vergleich ein
> echtes größer oder ein echtes kleiner liefert. Aber was
> fange ich mit einem ist gleich Ergebnis an?
Du nutzt größer/kleiner-Ergebnisse noch nicht genug aus. Du kannst immer mindestens eine Mutter/Schraube ausschließen, häufig aber viel mehr.
Denk mal darüber nach, was für die kleinste Schraube/Mutter gelten muss (was sind die Ergebnisse aller ihrer Vergleiche?)
Wenn du eine Gleichheit findest, musst du dir diese merken, aber den Rest weiterprüfen, denn es kann ja sein, dass du schon die kleinste Schraube und ihre Mutter gefunden hast und am Ende wieder auf das Paar zurückgreifen musst.
|
|
|
|
