 Aufgabe zum Thema "Algorithmen" |
Dragon_Fighter
unregistriert
 |
|
| 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 14:38 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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:32 |
|
|
Dragon_Fighter
unregistriert
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?G1=\left\{M1,M2,M3\right\}) und ![[latex]G2=\left\{M4,M5,M6\right\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?G2=\left\{M4,M5,M6\right\}) .
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 16:57 |
|
|
Dragon_Fighter
unregistriert
|
|
Edit:
Beim allerletzten Sonst soll es x=9 heißen.
|
|
|
10.04.2013 17:00 |
|
|
Dragon_Fighter
unregistriert
|
|
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 17:15 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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:16 |
|
|
Airblader
Doppel-As
Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München
|
|
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. 
__________________
The best thing about a boolean is that even if you're wrong, you're only off by a bit.
|
|
|
10.04.2013 19:57 |
|
|
|
