Hallo, ich stehe gerade vor folgendem Problem: Es geht um die Programmierung eines Münzwechslers, genauer gesagt um die Ausgabe eines Betrages x in möglichst wenigen Münzen. Eigentlich nicht sonderlich schwer, man beginnt einfach bei den größten Münzen und geht dann nach unten. Im Netz findet man unter dem Stichwort "Greedy-Algorithmus" auch diverse Beispiele. Der Algorithmus geht aber immer davon aus, dass immer genug Münzen da sind, in der Realität könnte aber beispielsweise die 1-Cent-Münze gerade fehlen und schon bekomme ich bei einem Auszahlungsbetrag von 0,06€ Probleme (Greedy zieht eine 5-Cent-Münze ab, danach ist Schluss, auf die drei 2-Cent-Münzen kommt der Algorithmus nicht). Hat jemand einen intelligenten Ansatz, dieses Problem zu lösen? Ein entsprechendes Stichwort reicht auch schon für die Suche. Das ganze muss aber auf einem 8bitter realisiert werden, daher wäre mir ein nicht rekursiver Ansatz (oder zumindest begrenzt auf wenige Iterationen) am liebsten. Danke schonmal! Christoph
Ich habe mir zwar den Algorithmus nicht angeguckt, aber ich würde einfach mal sagen - leider rekursiv formuliert: function Ausgabe(Betrag) Wenn Betrag=0 => Fertig Suche größte Münze aus den vorhandenen, die <=Betrag ist Zahle Münze aus Ausgabe(Betrag-Münze) Dann musst du nur aufpassen, immer die richtige Anzahl der Münzen im Kopf zu haben
Dieser Algorithmus berücksichtigt aber nicht fehlende Münzen...
Naja. Dieses Problem ist zumindest simulierbar. Schreib mal eine Simulation. Wenn nichts mehr geht : Den Zufallsgenerator laufen lassen, und wenn's aufgeht ist gut, sonst nochmals probieren.
Setze das Restgeld erst einmal aus den kleinst möglichen Münzen zusammen. Dann Versuche mehrere kleine Münzen durch die größte Münze zu ersetzten, wenn das nicht mehr geht durch die nächst kleinere usw. Dann hast Du auf jeden fall eine Lösung!
Such mal nach dem Begriff Matroid bzw. Matroid-Eigenschaft. Dann findest du etliche Ansätze bzw. Algos zum Thema.
Marcus B. schrieb:
> Suche größte Münze aus den vorhandenen
Also alle existierenden Münzen durch gehen
Bedingungn Münze <= Betrag && Münze.Anzahl>0
----------------
Gerade habe ich gecheckt, was du meinst...
Naja da muss dann bevor das Geld wirklich ausgespuckt wird einfach in
einem Array mitgezählt werden, wie oft welche Münze raus soll. Und wenn
es nicht auf geht- weil Du das Münzarray abgelaufen hast, aber keine
passende Münze da hast, dann Error werfen
Julian Baugatz schrieb: > Dann hast Du auf jeden fall eine Lösung! Es sei denn, das Wechselgeld reicht überhaupt nicht aus um den Betrag zusammenzusetzen. Aber dann hat man sowieso ein grundsätzliches Problem und muss sich was überlegen. Aber ansonsten: Die Lösung gefällt mir. Mir wär nur Backtracking eingefallen: Wenn die Entnahme einer 5Cent Münze zu keiner Lösung führt, dann leg sie zurück und mach ohne sie mit der nächst kleineren Münzsorte weiter. Backtracking wird aber aber am einfachsten mit einer Rekursion gelöst, die du ja nicht wolltest. Man könnte das ja kombinieren: erst Greedy und wenn das zu einem Problem führt von der anderen Seite loslegen. Denn eines ist auch unbestritten Greedy ist schön einfach. Obwohl: Es gibt wohl nichts, was an einem Getränkeautomaten zeitkritisch wäre :-) Lästig sind nur die Heuristiken, wie man gewisse Münzkombinationen durch größere Münzen ersetzen kann.
Karl Heinz Buchegger schrieb: > Es sei denn, das Wechselgeld reicht überhaupt nicht aus um den Betrag > zusammenzusetzen. Aber dann hat man sowieso ein grundsätzliches Problem > und muss sich was überlegen. Klar, das ist aber im Prinzip das einfachste, ab in den Fehlermodus. > Aber ansonsten: Die Lösung gefällt mir. Mir wär nur Backtracking > eingefallen: Wenn die Entnahme einer 5Cent Münze zu keiner Lösung führt, > dann leg sie zurück und mach ohne sie mit der nächst kleineren Münzsorte > weiter. Backtracking wird aber aber am einfachsten mit einer Rekursion > gelöst, die du ja nicht wolltest. Das mit dem Backtracking wäre eigentlich auch mein Favorit. Ich brauche das auch nur bei der 2/5 Cent Münze - alle anderen Münzen ergeben sich immer aus diesen. Sprich es macht keinen Sinn, noch eine 10 Cent-Münze wieder zurückzulegen, da dies ein Vielfaches von 2 ist und so weiter. Rekursion ist grundsätzlich ok, ich möchte nur genau sagen können, wieviel Speicher ich beispielsweise im Worst-Case brauche, aber mit dem obigen Ansatz wäre es maximal ein Schritt zurück, das ist ok. > Man könnte das ja kombinieren: erst Greedy und wenn das zu einem Problem > führt von der anderen Seite loslegen. Denn eines ist auch unbestritten > Greedy ist schön einfach. Obwohl: Es gibt wohl nichts, was an einem > Getränkeautomaten zeitkritisch wäre :-) Lästig sind nur die Heuristiken, > wie man gewisse Münzkombinationen durch größere Münzen ersetzen kann. Ich teste mal den oberen Ansatz, eigentlich müsste das passen (auch für andere Währungen, da die Stückelung eigentlich immer gleich ist bei den Münzen (nur beispielsweise die 25 Cent-Münze der USA fällt etwas aus dem Rahmen. Kann ich ja froh sein, dass man irgendwann mal die 1/3 Taler abgeschafft hat... ;-)
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.