Mealy Automaten skizzieren?
Hallo! ich müsste für einen Algorithmus einen Automaten skizzieren. Den pseudocode habe ich bereits, aber nur um das ganze logisch zu veranschaulichen, muss dieser automat Wechselgeld für einen betrag zwischen 0 und 100Cent zurückgeben.
Es stehen jeweils genügend Münzen im Wert von 1,2,5,10, 50 cent und 1 Euro zur Verfügung. Ziel ist es mit so wenigen Münzen wie möglich auszukommen.
Ich habe zwei versionen vom automaten skizziert, bin mir aber nicht sicher, ob ich überhaupt auf der richtigen Fährte bin oder was nicht passt!
2 Antworten
Das 2. sieht schon gut aus, ich weiss nur nicht, was du da alles rechnest....
Wenn A der zurückzugebende Wert ist, würde ich da ähnlich wie bei dir unten einen Startzustand und einen Zustand pro Münzausgabe und einen Endzustand bauen.
Startzustand: mit A>=100 zu 1€ Zustand, mit A<100 und A>=50 zu 50c, etc. (bei den kleinenen Münzen jeweils beide Grenzen angeben, so dass der Zustandsübergang eindeutig ist, damit nicht bei A>=100 alle möglich sind, sondern nur der 1€), mit A==0 zum Endzustand
Vom Münzzustand einfach wieder zurück zum Startzustand mit A := A - Münzwert und Ausgabe einer entsprechenden Münze des Wertes.
Man könnte jetzt zusätzliche Übergänge zu den "Folgemünzen" bauen, da müsste man aber bei 1€ wieder alle Bedinungen checken, da man ja ggf. 20c "überpringen" muss, wenn es ursprünglich 1,15 war. Da immer über den Startzustand zu gehen, ist die einfachere Methode und spart einen Haufen Zustandsübergänge.
Das der dann eben den Euro oder die 20c entsprechend ausspuckt oder einen passenden Zähler für die Anzahl der ausgegeben 1€ oder 20ct Münzen um 1 erhöht.
danke! also würde ich da eine weitere linie brauchen, welche mit ausgabe verbunden wird und dort steht dann immer +(Münzenwert), sowie beim ersten bild in etwa?
Das hängt ein bisschen von der Notation des Automaten ab, das muss kein Extra Zustand, das kann er entweder direkt in den "Münzzuständen" machen oder als action beim Betreten oder Verlassen des Zustandes.
Größer / gleich 100 macht schon mal nicht so viel Sinn, weil er max 1 € zurückgibt. Sei R das Restgeld. Wenn R = 100, dann Rückgabe 1 €, Endzustand.
Wenn >= 50 und <100, dann Ausgabe 50 (Reduktion von R um 50) und zurück zum Start.
Wenn >= 10 und <59, wie oben, so auch die übrigen.
Wenn = 0, gehe zum Endzustand.
Es geht also immer zurück zum Start, lediglich 1 € und 0 sind die Endzustände. Man könnte statt 1€ Endzustand auch Rückkehr zum Start machen, dann hat man nur einen Endzustand.
Das ist jetzt ein Greedy-Algo, viel mehr können solche Automaten auch nicht. Müsste aber das Ziel erreichen, dass so wenig Münzen wie möglich, da jeweils die größten Münzbeträge herausgegeben.
Vielen lieben Dank!
aber was meinen Sie mit "Ausgabe einer entsprechenden Münze des Wertes." genau? Wie soll das aussehen in etwa?