Hola!

Neulich habe ich in der Berufsschule folgende Aufgabe bekommen:

Ein Wechselautomat nimmt beliebige Geldscheine entgegen. Er kann 2 Euro, 1 Euro und 50 Cent Muenzen ausgeben. Schreibe ein Programm, dass _alle_ Ausgabemoeglichkeiten berechnet.

Wir haben mit dem Programm noch nicht angefangen, aber da Algorithmik sowieso nicht meine Staerke ist, wollte ich nachfragen wie man das am geschicktesten loesen kann.

Ich hab mich mal (mit Perl und C) an dem Problem versucht und bin immer nur auf Algos gekommen, die nur Teile des Problems loesen.

Wie wuerdet ihr hier vorgehen?

Alle möglichen Kombinationen?

Ich kenne diese Aufgabe so ähnlich. Das Programm soll die mögliche Ausgabe von z. B. 50,00 EUR ausgeben. Sprich man fängt mit dem größten Schein an und wird dann immer kleiner. Bis man bei dem richtigen Betrag ist.

Frank

Alle möglichen Kombinationen?

Ja, alle moeglichen Kombinationen. Wenn man nur eine bestimmte Moeglichkeit berechnen muesste, dann waere das fuer mich auch kein Problem.

Der "Brute Force"-Ansatz:

Drei verschachtelte Schleife, eine für jeden Münzwert, jeweils von 0 bis (Gesamtwert/Münzwert). In der innersten Schleife den Wert der Münzen ermitteln. Wenn er passt, die Kombination ausgeben.

Arbeite dich von den großen zu den kleinen Münzen mit einer Division durch den Wert der jeweiligen Münze und einem Modulo mit dem Rest (also den Quotienten)