Hallo,
Wie kann ich einen Betrag von z.B. 1,19€ mit genau 50 Münzen bezahlen,
es sollen nur 1, 2 und 5 Cent-Stücke verwendet werden.
ich machs gleich etwas allgemeiner: Ein Betrag von a Cent soll mit n Münzen bezahlt werden.
Mit den Variablen e, z und f für die Anzahlen der Ein-, Zwei- bzw. Fünf-Cent-Münzen lässt sich das Problem dann so formalisieren:
1e + 2z + 5f = a
e + z + f = n
mit der Zusatzbedingung, dass e, z und f ganzzahlig-positiv sein müssen.
Das ist ein lineares Gleichungssystem mit zwei Gleichungen für drei Variablen. Genau eine Variable ist also frei wählbar. Beim Durchprobieren aller drei Wahlmöglichkeiten bekommst Du als Lösungen:
\left(\begin{array}{cc}
z \ f
\end{array}\right)
\left(\begin{array}{cc}
\frac{1}{3} (5n - a - 4e) \ \frac{1}{3} (a - 2n + e)
\end{array}\right)
\quad
\textnormal{mit $e$ als freier Variable}
\left(\begin{array}{cc}
e \ f
\end{array}\right)
\left(\begin{array}{cc}
\frac{1}{4} (5n - a - 3z) \ \frac{1}{4} (a - n - z)
\end{array}\right)
\quad
\textnormal{mit $z$ als freier Variable}
\left(\begin{array}{cc}
e \ z
\end{array}\right)
\left(\begin{array}{cc}
3f + 2n - a \ a - n - 4f
\end{array}\right)
\quad
\textnormal{mit $f$ als freier Variable}
Wie Du erkennst zeichnet die Wahl von f als freier Variablen ein besonderes, sehr willkommenes Feature aus: Wenn f ganzzahlig ist, dann sind automatisch auch e und z ganzzahlig.
Damit kannst Du schon die Lösung angeben:
–––––––––––––––––––––––––––––––––––––––––––––––––
Nimm eine „nicht zu niedrige und nicht zu hohe“ (das wird noch zu präzisieren sein) aber ansonsten beliebige Anzahl (f) Fünf-Cent-Münzen und dazu
z = a - n - 4f Zwei-Cent-Münzen und
e = 3f + 2n - a Ein-Cent-Münzen.
–––––––––––––––––––––––––––––––––––––––––––––––––
Nun muss noch berücksichtigt werden, dass weder f noch z noch e negativ werden dürfen. z bleibt positiv für f ≤ (a – n)/4 und e bleibt positiv für f ≥ (a – 2n)/3. Der zulässige Bereich für f ist somit
\textnormal{ceil}\left(\frac{a - 2n}{3}\right) \le f \le \textnormal{floor}\left(\frac{a - n}{4}\right)
(ceil = Aufrundung auf nächstgrößere Ganzzahl, floor = Abrundung auf nächstkleinere Ganzzahl.) Falls die untere f-Grenze größer ist als die obere f-Grenze, existiert keine Lösung (es ist z. B. unmöglich, einen Betrag von 20 Cent mit 50 Münzen zu bezahlen).
Für Dein Problem (a = 119, n = 50) ergibt sich: Nimm zwischen (je einschließlich) 7 und 17 Fünf-Cent-Münzen und dazu 69 – 4f Zwei-Cent-Münzen und 3f – 19 Ein-Cent-Münzen. Die Probe zu machen, ob dies die Gleichungen 1e + 2z + 5f = 119 und e + z + f = 50 erfüllt, überlasse ich Dir.
Gruß
Martin
