Algorithmus (Münzen wiegen) schreiben



  • Hallo, folgende Aufgabe:

    Wir verfügen über eine bestimmte Anzahl von Münzen, die alle gleich aussehen und gleich schwer sind - bis auf eine Münze, die schwerer ist als die anderen Münzen. Zudem verfügen wir über eine Balkenwaage, mit der bestimmt werden kann, ob eine Gruppe von Münzen (bestehend aus einer oder mehrerer Münzen) schwerer ist als eine andere Gruppe von Münzen.

    a) Formulieren Sie einen Algorithmus, welcher festellt, welche die schwerere Münze ist. Welche elementaren Aktionen und Bedingungen haben Sie dabei verwendet?

    b) Wie oft muss man wiegen, wenn man neun Münzen hat?

    ----

    Also ich beginne mal mit b). Da habe ich heraus, dass man minimal 1 Mal und maximal 3 Mal wiegen muss und zwar habe ich folgenden Algorithmus hierbei mir ausgedacht (man teilt immer in Gruppen mit einer geraden Anzahl von Münzen):

    Die Variable x soll am Ende die schwerere Münze angeben.
    Mit M1,...,M9 bezeichne ich die Münzen 1 bis 9.
    Und mit g(M1),...,g(M2) meine ich das Gewicht der Münzen 1 bis 9.

    Also:

    Setze x=1;
    Bestimme g(G1)=g({M1,...,M4})g(G1)=g(\left\{M1,...,M4\right\}) und g(G2)=g({M5,...,M8})g(G2)=g(\left\{M5,...,M8\right\}).

    Falls g(G1)>g(G2)g(G1)>g(G2)
    Bestimme g(G3)=g({M1,M2})g(G3)=g(\left\{M1,M2\right\}) und g(G4)=g({M3,M4})g(G4)=g(\left\{M3,M4\right\}).

    Falls g(G3)>g(G4)g(G3)>g(G4)
    Bestimme g(M1)g(M1) und g(M2)g(M2).

    Falls g(M1)>g(M2)g(M1)>g(M2)
    gib x aus;

    Sonst
    x=2;
    gib x aus;

    Sonst
    Bestimme g(M3)g(M3) und g(M4)g(M4)

    Falls g(M3)>g(M4)g(M3)>g(M4)
    x=3;
    gib x aus;

    Sonst
    x=4;
    gib x aus;

    Sonst
    Fallsg(G1)<g(G2)g(G1)<g(G2)
    Bestimme g(G5)=g({M5,M6})g(G5)=g(\left\{M5,M6\right\}) und g(G6)=g({M7,M8})g(G6)=g(\left\{M7,M8\right\}).

    Falls g(G5)>g(G6)g(G5)>g(G6)
    Bestimme g(M5)g(M5) und g(M6)g(M6)

    Falls g(M5)>g(M6)g(M5)>g(M6)
    x=5;
    gib x aus;

    Sonst
    x=6;
    gib x aus;

    Sonst
    Bestimme g(M7)g(M7) und g(M8)g(M8)

    Falls g(M7)>g(M8)g(M7)>g(M8)
    x=7;
    gib x aus;

    Sonst
    x=8;
    gib x aus;

    Sonst
    x=9;
    gib x aus;

    ENDE

    Liegt die schwerere Münze also in den Gruppen G1 oder G2, sind maximal 3 Messungen nötig.
    Ist die neunte Münze die schwerere Münze, ist nur eine Messung nötig.

    Kann mir wohl jemand sagen, ob das so stimmt (ich hoffe, man kann es einigermaßen verstehen)? Und wie könnte man das allgemein für n Münzen ausdrücken?



  • Ich brauche bei 9 Muenzen nur 2mal wiegen. Desweiteren kann ein Algorithmus auch in "normaler Sprache" formuliert sein. In diesem Fall faellt die Beschreibung dadurch wesentlich kuerzer als auch verstaendlicher aus.



  • Hallo, wie machst du das, dass Du zwei Mal wiegen musst?



  • Hier die Algorithmenbeschreibung: Man teile die 9 Muenzen in 3 gleich grosse Gruppen. D.h. jede Gruppe enthaelt 3 Muenzen. Nun wiegt man zwei davon mit der Balkenwaage. Benutze die schwerere Gruppe im folgenden weiter. Wenn beide Gruppen gleich schwer sind, so muss die gesuchte Muenze in der nicht gewogenen Gruppe sein und ist weiter zu benutzen. Wende nun obige Vorgehensweise auf die verbliebenen Muenzen an, um die schwerste zu finden.

    Anmerkung: Du setzt eine Funktion g(M) voraus, die nach deiner Beschreibung das Gewicht der Muenzen zurueckliefert. Diese wird aber nicht durch die Balkenwaage realisiert. Du hast maximal eine Funktion g'(M, N), die bestimmt, welche Muenzmenge groesser ist. Du wiegst das Gewicht der Muenzen immer nur in Relation zu anderen Muenzen.



  • Danke, das verstehe ich.

    Nur frage ich mich, was genau an meinem Algorithmus nicht stimmt (abgesehn davon, dass er sehr unübersichtlich ist) und wieso ich so ein komisches Ergebnis habe:

    minimal 1 Mal, maximal 3 Mal messen

    Oder ist es vielmehr so, dass mein Algorithmus auch korrekt ist - nur eben viel zu umständlich?



  • Und wie könnte man den Algorithmus allgemein angeben - also für eine beliebige Anzahl an Münzen?

    Ich sehe das irgendwie nicht.

    Bei gerader Anzahl könnte man in 2er-Gruppen aufteilen.

    Aber bei ungerader Anzahl?.. wie kann man es da verallgemeinern (was ist z.B. bei 11 Münzen)?



  • was genau an meinem Algorithmus nicht stimmt

    Viele Wege fuehren nach Rom. Nur weil deiner anders ist, muss er nicht falsch sein. Er unterscheidet sich aber. Ich habe mir deinen Algorithmus auch nicht genauer angesehen, da er viel zu umstaendlich formuliert ist. Du versuchts den Algorithmus als Programm zu formulieren, was aber nicht noetig ist.

    Desweiteren habe ich dich schon auf die Problematik deiner Gewichtsfunktion hingewiesen. Weiter definierst du die Funktion g(M), die eine Muenze als Argument akzeptieren und setzt dann Mengen von Muenzen ein. Das geht nicht.

    wie kann man es da verallgemeinern

    Na ich muss immer fuer meine Balkenwaage 2 Teilmengen haben mit gleicher Muenzanzahl und einen Rest. Dann kann man eine Funktion definieren, choose(Set1, Set2, Set3), die entscheidet, welche davon die schwerste ist. Dann definiert man eine Funktion split(Set), die eine Menge in 3 Teilmengen entsprechend den beschriebenen Vorgaben zerlegt. Dann wendet man diese beiden suksessiv an, solange bis die gewaehlte Menge von choose nur noch ein Element enthaelt.



  • Vielen Dank. Stimmt, es führen viele Wege nach Rom und daher:

    Ich würde die ganze Aufgabe noch ein bisschen vereinfachen.

    Teilaufgabe a) würde ich so lösen:

    ALGORITHMUS

    (*)Solange in der Menge der n Münzen sich mindestens zwei Münzen befinden

    Entnehme zwei beliebige Münzen und lege je eine auf eine Waagschale.
    Falls eine Münze schwerer ist, gib diese Münze aus.
    ENDE

    Sind beide Münzen gleich schwer, nimm beide Münzen und leg sie weg. Sie kommen nicht in Frage. Kehre zurück zu (*).

    Ansonsten
    gib letzte übriggebliebene Münze aus, sie ist die gesuchte.

    Das müsste doch auch ein möglicher Algorithmus sein.

    Mit DIESEM Algorithmus braucht man bei 9 Münzen 1-4 Versuche, korrekt?

    Viele Grüße und besten Dank für die Hinweise. Allerdings bin ich noch ganz am Anfang und Funktionen usw. hatten wir noch gar nicht. Dennoch find ich es interessant. 👍



  • Ja.

    Welche elementaren Aktionen und Bedingungen haben Sie dabei verwendet?

    Das waere dann auswaehlen/ziehen und wiegen/vergleichen.



  • 🙄 nochmal DANKE



  • Oh, vergessen. Zu einem Algorithmus gehoert Eingabe, Handlungsanweisung und Ausgabe. Bisher wurde die Eingabe (obwohl durch die Aufgabenstellung offensichtlicht) nicht explizit erwaehnt.


Log in to reply