Aufgabe zum Thema "Algorithmen"

Neue Frage »

10.04.2013, 14:38	Auf diesen Beitrag antworten »
Dragon_Fighter	Aufgabe zum Thema "Algorithmen" Meine Frage: Hallo, ich habe hier eine eher allgemeine Aufgabe zum Erlernen von Algorithmendenken. Aufgabe: Ich verfüge über eine bestimmte Anzahl von Münzen, die identisch aussehen und die alle gleich schwer sind, mit Ausnahme von einer Münze, die schwerer als die anderen Münzen ist. Weiterhin verfüge ich über eine Balkenwaage, mit der ich bestimmen kann, ob eine Gruppe von Münzen (eine oder mehrere) schwerer ist als eine andere Gruppe. (i) Formuliere eine Algorithmus, der feststellt, welches die schwerere Münze ist. Welche elementaren Aktionen und Bedingungen haben Sie dabei verwendet? (ii) Wie oft muss man wiegen bei neun Münzen? Meine Ideen: Für den Fall, dass man zwei Münzen hat, ist es elementar. Hierbei soll x die schwerere Münze bezeichnen (also entweder am Ende x=1 oder x=2): Algorithmus: Setze x=1; Lege Münze 1 in die eine Schale links, Münze 2 in die andere Schale rechts. Falls Schale links weiter unten Gebe x aus Sonst Setze x=2; Gebe x aus; ENDE Für drei Münzen: Algorithmus: Setze x=1; Leg Münze 1 in linke Schale; Leg Münze 2 in rechte Schale; Falls linke Schale tiefer als rechte Schale Gib x aus; ENDE Sonst Falls rechte Schale tiefer als linke Schale setze x=2; Gib x aus; ENDE Sonst setze x=3; Gib x aus; ENDE Ist das schonmal okay? Aber wie kann man es allgemein für n Münzen ausdrücken?


10.04.2013, 16:32	Auf diesen Beitrag antworten »
Karlito	Hallo, es ist auch gültig in Mengen zu denken. So ist es möglich immer 2 Münzen aus der Menge der zu untersuchenden Münzen zu entnehmen und zu vergleichen... Somit wäre der Algorithmus: ()Solange in der Menge der zu untersuchenden Münzen mindestens 2 Münzen sind: Entnehme 2 Münzen und vergleiche diese. Ist dabei eine schwerer, so gib diese Zurück und beende das Programm. Sind sie gleich schwer, dann verwerfe die Beiden untersuchten Münzen (oder lege sie in der Menge der bereits untersuchten Münzen ab) und gehe zu () Ansonsten gib die letzte Münze zurück, da dies der einzig verbliebene Fall ist. VG, Karlito
10.04.2013, 16:57	Auf diesen Beitrag antworten »
Dragon_Fighter	Hallo, Karlito. Der Algorithmus, den Du beschreibst bezieht sich auf Fragestellung i), korrekt? ------------------------------ Für Fragestellung ii) habe ich Folgendes überlegt: Teile die 9 Münzen in drei 3-er Gruppen. Setze x=1. Wiege zwei 3er-Gruppen, etwa $[latex]G1=\left\{M1,M2,M3\right\}[/latex]$ und $[latex]G2=\left\{M4,M5,M6\right\}[/latex]$ . Falls G1 schwerer als G2 Wiege M1,M2,M3. Falls M1 schwerer als M2 gib x aus Sonst Falls M2 schwerer als M1 x=2 gib x aus Sonst x=3 gib x aus Sonst Falls G2 schwerer als G1 Wiege M4, M5, M6. Falls M4 schwerer als M5 x=4 gib x aus Sonst Falls M5 schwerer als M4 x=5 gib x aus Sonst x=6 gib x aus Sonst Wiege M7,M8,M9 Falls M7 schwerer als M8 x=7 gib x aus Sonst Falls M8 schwerer als M7 x=8 gib x aus Sonst x=8 gib x aus ENDE Man muss also 2 Mal wiegen. Sorry, wenn es vllt. etwas unübersichtlich ist. Wüsste gerne, ob es so geht.
10.04.2013, 17:00	Auf diesen Beitrag antworten »
Dragon_Fighter	Edit: Beim allerletzten Sonst soll es x=9 heißen.
Anzeige

10.04.2013, 17:15	Auf diesen Beitrag antworten »
Dragon_Fighter	Achso, nochwas: @Karlito Mit dem von Dir vorgeschlagenen Algorithmus bräuchte man bei 9 Münzen doch dann minimal 1 und maximal 4 Messungen?
10.04.2013, 19:16	Auf diesen Beitrag antworten »
Karlito	Hallo, ich denke dein Algorithmus geht so. Das Problem ist, dass er nicht ganz allgemein ist, da er Ausgaben nur dann erzeugt, wenn n=9. Du musst dir also was einfallen lassen, so dass ein beliebiges n möglicht ist. Natürlich ist dein Algorithmus für n=9 mit den 3er-Gruppen sehr gut. für höhere n gibt es bessere Methoden. Und ja, mein Algorithmus ist schlechter und braucht wie du sagst im schlechtesten Fall 4 Wiegevorgänge und im besten einen. Vorschlag für einen effizienteren Algorithmus: Ich gehe einfach davon aus, dass man die Elemente der Menge eindeutig zuordnen kann. D.h. Wenn man ein beliebiges Element aus der Menge entnimmt, so kann man eindeutig zuordnen, ob es Münze_1 oder Münze_2 oder ... oder Münze_n ist. Diese Annahme ist leicht zu realisieren. Somit musst Du, wenn du die schwerste Münze ermittelt hast nur schauen, welche es war. Dein Ansatz hat mich aber auf eine Idee gebracht: Teile die Aufgabe immer in 3 Teilmengen. Somit folgender Lösungsvorschlag: Teile die Menge in 3 gleich große Teile (die maximal 2 überschüssigen Elemente werden zufällig auf die 3 Teilmengen verteilt). Sind nur noch genau 2 Elemente in der Menge, so setze die dritte Teilmenge = die leere Menge. Vergleiche die ersten beiden Mengen und nehme die schwerste Menge als Ausgangsmenge von Schritt eis und setze bei Schritt 1 fort Führe Schritt 1 und 2 solage aus, bis nur noch 1 Element in der Menge enthalten ist und gib dieses Element als Ergebnis zurück. Somit sinkt die größe der Aufgabe bei jedem Schritt um den Faktor 3 und es wäre wie in deinem Algorithmus bei n=9 immer nur 2 mal wiegen notwendig. Habe ich dich nur falsch verstanden und Du hattest die selbe Idee? VG, Karlito
10.04.2013, 19:34	Auf diesen Beitrag antworten »
Dragon_Fighter	Cool, dankeschön! Ich hatte schon diese Idee, aber allgemein habe ich es nicht formuliert bekommen.
10.04.2013, 19:57	Auf diesen Beitrag antworten »
Airblader	Man könnte übrigens auch ein beliebiges Sortierverfahren anwenden – optimalerweise natürlich einen mit gutartiger Komplexität, also z.B. Mergesort –, und dann einfach die Münze als Ergebnis nehmen, die nach hinten sortiert wurde. Viele Wege führen nach Rom.

Neue Frage »

Antworten »

Aufgabe zum Thema "Algorithmen"

Verwandte Themen