Algorithmus für Trinkspiel < Sonstiges < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 07:42 Di 03.07.2012 | | Autor: | jacco |
| Aufgabe | | Keine Aufgabenstellung, da ich mir die Aufgabe selbst gestellt habe. |
Ab und zu spiele ich mit einem Freund beim Bierchentrinken ein Würfelspiel und nun haben wir uns gefragt ob es wohl einen effizienten Algorithmus gibts um dies zu Lösen. Das Spiel ist schnell erklärt. Es wird eine Zahl festgelegt und dann mit vier Würfeln gewürfelt nun wird versucht die vier Zahlen mit den Grundrechenarten so zu verrechnen, dass die festgelegte Zahl herauskommt. Jede der vier Zahlen darf nur ein Mal benutzt werden, es dürfen jedoch entstehende Zwischenergebnisse benutzt werden. Das ganze entspricht also dem Rechnen ohne Operatorpräzedenz. Hier mal ein Beispiel für die Zahl 14 und die Würfelaugen 4 5 3 3.
4*5-(3+3)=14
oder
4*3+(5-3)=14
Ich habe ausgerechnet, dass es 83140 Möglichkeiten gibt aus 4 Würfeln ohne Operatorpräzedenz eine Zahl zu Bilden. Die Frage ist nun wie komme ich am effizientesten zu der Gesuchten? 
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:13 Di 03.07.2012 | | Autor: | wieschoo |
sehr gut!
Das nehme ich direkt in meine Liste für praxisnahe Aufgaben auf. Nicht immer nur Vektorräume.
|
|
|
| |
|
Allgemein würde ich schon immer sagen: Brüche vermeiden. So etwas wie [mm] \frac{1}{3} oder\frac{1}{7} [/mm] wird einem kaum weiterhelfen.
Ich denke, dann ist wohl probieren keine schlechte Wahl ;)
Ich würde auch meinen, wenn man die 3 errechnen soll, ist es nicht gerade von Vorteil, wenn man 3 mal die 6 multipliziert.
Ich würde immer möglichst von der zu bestimmenden Zahl ausgehen.
Also, wie in deinem Bsp.: Die Zahl 14. Welche Zahl kann ich addieren, damit eine Zahl herauskommt, die man durch die anderen Würfel erhalten kann. Quasi die Sache von hinten aufrollen.
Viel Spaß beim Spielen ;)
|
|
|
| |
|
Wenn ich das Spiel modelliere, dann ist die Eingabemenge [mm]x_1,x_2,x_3,x_4,y\in \IN[/mm] mit [mm]x_i\in \{0,1,2,\ldots,9\}[/mm].
Gesucht ist [mm]\square_i\in\{+,-,\cdot,\mid\}[/mm] mit [mm]x_1 \;\square_1\; x_2 \;\square_2\; x_3 \;\square_3\; x_4=y[/mm].
Der einfachste Algorithmus ist rekursiv die Möglichkeiten durchzutesten.
Aus [mm](x_1,x_2,x_3,x_4)[/mm] kann man kleinere Instanzen basteln
[mm](x_1,x_2,(x_3,x_4))[/mm] --> [mm]x_1 \;\square\; x_2 \;\square\; (x_3,x_4)[/mm]
[mm](x_1,x_3,(x_2,x_4))[/mm] --> ...
[mm](x_2,x_3,(x_1,x_4))[/mm] --> ...
[mm](x_1,x_4,(x_2,x_3))[/mm]
[mm](x_2,x_4,(x_1,x_3))[/mm]
....
Diese Paare [mm](a,b)[/mm] können nun wie folgt Ergebnisse c liefer:
a+b,a-b,b-a,a/b,b/a,a*b
und man muss nur noch [mm](x_i,x_j,c)[/mm] lösen.
Wie kommt man dann auf 83140 Möglichkeiten?
Bei mir sind es nur [mm]6\binom{4}{2} \cdot 6\binom{3}{2} \cdot 6\binom{2}{2}=3888[/mm] Fälle, die getestet werden müssen.
(Habe ich bzw. wo habe ich da einen Denkfehler?)
Eventuell kann man bestimmt Konstellationen noch ausschließen. Ist z.B. das Ergebnis gerade und die gewürfelten Zahlen sind es nicht, so muss es mindestens eine Addition oder Subtraktion geben.
Ich denke auch, dass man das unbewusst rückwärts macht.
Am Beispiel von 14 und den Zahlen 1,7,2,5
Probiert man Rückwärts (schlecht formalisiert)
[mm]14=(7,7)=(7,(2,5))=((1,7),(2,5))[/mm]
so erhält man
[mm]1\cdot 7 + (2+5)[/mm]
.
Ich glaube kaum, dass es wesentlich effektiver geht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:26 So 29.07.2012 | | Autor: | wieschoo |
Ich glaube es ist besser, wenn der vorherige Beitrag eine Frage wär.
Edit: Wäre auch interessant zu wissen ob es "Lücken" gibt, d.h. Zahlen die sich nicht kombinieren lassen und klein genug wären.
Oder welche Zahlen sich durch die meisten Kombinationen darstellen lassen, ohne Kombinationen doppelt zu zählen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:55 Mo 13.08.2012 | | Autor: | Marcel |
Hallo,
> Ich glaube es ist besser, wenn der vorherige Beitrag eine
> Frage wär.
Wunsch erfüllt 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:21 Di 14.08.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:05 So 29.07.2012 | | Autor: | ms2008de |
Hallo,
Ich würde wenn die gesuchte Zahl eine positive Ganze Zahl sein soll und einem die Lösung nicht sofort ins Auge springt mal so vorgehen: Ich addiere einfach alle 4 gewürfelten Zahlen und erhalte dann eine Zahl e. Ist nun dieses e kleiner als die gesuchte Zahl, so muss offensichtlich irgendwo eine Multiplikation stattfinden, wobei beide Faktoren nicht 1 sein dürfen. Ist e größer als die gesuchte Zahl, so muss entweder irgendwo eine Subtraktion, Division oder Multiplikation mit 1 (falls möglich) ausgeführt werden. So kann man (wenn überhaupt möglich) recht schnell auf die gesuchte Zahl kommen mittels Grundrechenarten, bzw. sich immer weiter annähern.
Viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:20 Fr 03.08.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
