Gesucht: Algorithmus für Münzwechsler

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!

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.