Entwickler-Ecke
Ankündigungen - AGS 2012 - Lösung zu GS3 (Zaubertrank)
Narses - Sa 22.12.12 02:32
Titel: AGS 2012 - Lösung zu GS3 (Zaubertrank)
Moin!
Die Lösung ist:
frische Misteln, getrockneter 4blättriger Klee, natürliches Steinöl =
70 Taler
Wie kommt man da drauf? :?!?: Gehen wir zunächst mal den
Tipps [
http://www.entwickler-ecke.de/topic_AGS+2012++Tipps+zu+GS3+Zaubertrank_110806.html] nach: :lupe:
| Zitat: |
- Um kreativ zu werden, spielt der Wichtel zwischendurch eine französische Kugelsportart.
- Die Wichtel spielen gerne eine bestimmte Variante des Spiels "Pillard", das wiederum mit unserem Billard verwandt ist. |
Das sollte einen auf "Bool" (unsern alten
Kumpel George [
http://de.wikipedia.org/wiki/George_Boole] :lol:) bringen, und letztlich darauf, dass es sich bei den Rezepten um
Bool´sche Funktionen [
http://de.wikipedia.org/wiki/Boolesche_Funktion] handelt. Die "Naturform" einer Zutat ist eine nichtinvertierte, die "weiterverarbeitete Form" ist eine invertierte bool´sche Variable. Die Rezepte sind also und-verknüpfte Folgen bool´scher Variablen. Da jedes Rezept "wirksam" ist und man sich einen aussuchen kann, müssen die Terme 1 ergeben und ver-oder-t sein. :idea:
| Zitat: |
| - Der Wichtel arbeitet in der Technik-Abteilung und beschäftigt sich viel mit CPLDs. |
Googlen nach
CPLD liefert gleich als ersten Eintrag den
WP-Artikel dazu [
http://de.wikipedia.org/wiki/Complex_Programmable_Logic_Device], und da steht beim Aufbau der kleinen Krabbeltierchen:
| Zitat: |
CPLDs bestehen im Wesentlichen aus folgenden Elementen:
- programmierbare AND/OR-Matrix |
Und das wiederum ist praktisch eine Hardware-
DNF [
http://de.wikipedia.org/wiki/Disjunktive_Normalform]. :idea: (falls man das oben noch nicht kapiert hatte)
Nach intensivem Studium der Aufgabe :suspect: sollte klar sein, dass es darum geht, den "billigsten"
Primimplikanten [
http://de.wikipedia.org/wiki/Primimplikant] dieser DNF zu finden. :think:
Für den algorithmischen Lösungsansatz war dann der letzte Tipp da:
| Zitat: |
| Weil dem Wichtel die Mitgliedschaft im YMCA nicht so richtig gefallen wollte, hat er einfach die QMCV gegründet. |
Klar, Google ist dein Freund, QMCV liefert früher oder später den
Quine-McCluskey-WP-Artikel [
http://de.wikipedia.org/wiki/QMCV]. Jetzt kann man das natürlich mal schnell selbst implementieren :lol: oder aber man nimmt die
fertige Webversion [
http://logik.phl.univie.ac.at/~chris/gateway/formular-zentral.html], die ganz unten verlinkt ist... :roll: :P
Um den Weboptimierer benutzen zu können, übersetzen wir mal eben die Rezepte in eine dafür passende Form (Variablen sind in Preislistenreihenfolge, &=und, v=oder, ~=nicht):
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| B&~E&~G v
A&~B&C&~D&H v
~B&~C&~D&~G v
A&B&~E&G&~H v
A&B&~E&~G v
~A&~D&G&H v
A&~B&D&H v
B&~D&H v
C&D&~G&H v
E&G&~H v
A&D&~H v
B&~G&~H |
Alternativ die Wertetabelle:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| -1--00-
1010--1
-000-0-
11--010
11--00-
0--0-11
10-1--1
-1-0--1
--11-01
----110
1--1--0
-1---00 |
Der Webservice liefert uns dann folgende Ausgabe, die ich der Kürze halber mal direkt mit Preisen versehen habe:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| 0--0-11 : 105
--10-11 : 100
--11-01 : 100
101---1 : 93
-1--00- : 83
----110 : 79
-1--1-0 : 79
-1-0--1 : 79
--00-0- : 78
11----0 : 77
10-1--- : 70 |
Das Nachschlagen der Zutaten in der letzten Zeile sei dem aufmerksamen Leser dann noch als Hausaufgabe überlassen. :les: ;)
Wenn man sich ein bischen Zeit lässt, damit man beim Übersetzen der Rezepte keinen Flüchtigkeitsfehler macht, dann kann man das doch locker in 10 Minuten einklimpern, oder? :nixweiss: Jaja, ich bin ja schon weg... ;)
Viel Erfolg beim letzten Rätsel! :zustimm:
cu
Narses
Oliver Marx - Sa 22.12.12 03:12
Hi,
wenn man allerdings das Verfahren des iteraten Konsensus benutzt, muss man nicht den Umweg über die Minterme machen (falls man selbst ein Tool geschrieben hat) und ist daher effizienter. Da ich Quine-McCluskey und iterativer Konsensus meinen Studierenden beibringe, hatte ich bei dieser Aufgabe schon ein fertiges Tool glücklicherweise zur Hand.
Des Weiteren liefert die von euch verlinkte Webseite, wenn ich richtig gesehen habe, eine minimale SOP und nicht die Primimplikanten (PI). Daher kann es bei einer ungünstigen Konstellation der Kosten dazu führen, dass man den kostengünstigsten PI übersieht. Daher sollte man alle (bei dieser Aufgabe glaube ich 34) PIs berechnen und alle PIs miteinander vergleichen.
In diesem Fall ging es zum Glück gut.
Viele Grüße
Oliver
Tilman - Sa 22.12.12 04:15
Verdammt, hatte die Zeile mit den 20 Talern Grundpreis übersehen :o
Daher nur 10 eingegeben :oops:
jfheins - Sa 22.12.12 08:34
Tja, da war ich wol mit dem Holzhammer zu Gange 8)
Einfach mal alle Rezepte maximal erweitern (ergibt dann 128 Stück) und dann iterativ: 1. Versuchen jedes gegen jedes andere zu kürzen 2. Doppelte Rezepte löschen.
Ergibt dann am Ende die gleichen wirksamen Rezepte mit je 3 Zutaten pro Rezept, aus denen dann das billigste genommen werden kann.
Und schon wieder was über Boolesche Funktionen gelernt :)
Die Tatsache dass man "die Lösung diesmal auch auf mit Zettel und Stift lösen kann", ließ mich darauf schließen dass es noch einen anderen Algorithmus geben müsste. Aber nachdem ich schon die Lösung hatte, war die Motivation den zu finden gering ^^
Xion - Sa 22.12.12 10:15
 jfheins hat folgendes geschrieben  : |
| Einfach mal alle Rezepte maximal erweitern (ergibt dann 128 Stück) |
Also bei mir waren es 459. (Nach der Reduktion sogar 706) (siehe Anhang).
Prinzipiell muss ich sagen, das Rätsel ist mir leicht gefallen. Liegt wohl daran, dass wir in der Uni ständig Probleme solcher Art lösen ;) (meistens sind sie schwieriger). Informatik-Studium ist schon ne coole Sache :mrgreen:
PS: endlich hab ich auch mal ein Rätsel richtig gelöst :zustimm:
Oliver Marx - Sa 22.12.12 12:07
Hi,
| jfheins hat folgendes geschrieben : |
Tja, da war ich wol mit dem Holzhammer zu Gange 8)
Einfach mal alle Rezepte maximal erweitern und dann iterativ:
1. Versuchen jedes gegen jedes andere zu kürzen
2. Doppelte Rezepte löschen.
|
wieso Holzhammer? Das ist doch das vorgeschlagene Verfahren von Quine-McCluskey.
Viele Grüße
Oliver
Flamefire - Sa 22.12.12 15:31
Hab dazu auch jedes Rezept in ne Liste eingefügt und wenn möglich mit allem erweitert und gekürzt. Dann minimale Kosten gesucht und fertig.
Das mit den Boolschen Variablen hab ich dann tatsächlich erst nach dem letzten Tipp kapiert. Aber dann Kopf->Wand das nicht eher gesehen zu haben ;)
Im Anhang mein Programm dazu. Mal in C++ weil ich das üben muss ;)
jfheins - Sa 22.12.12 22:59
| Oliver Marx hat folgendes geschrieben : |
wieso Holzhammer? Das ist doch das vorgeschlagene Verfahren von Quine-McCluskey.
Viele Grüße
Oliver |
Holzhammer weil ich die rezepte einfach mal auf "alles" erweitere. Die formale Beschreibung habe ich zwar nicht komplett durchdrungen, aber wenn ich das selbst implementiert habe weiß ich zumindest wie es funktioniert ^^
Anbei auch mein Programm. Die 128 Rezepte müssten schon ziemlich genau hinkommen. Beim reduzieren werden es aber erstmal mehr Rezepte.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!