Wechselgeld

Es gibt Euro-Münzen mit den Werten von 1, 2, 5, 10, 20 und 50 Cent sowie für 1 und 2 Euro. Wie viele verschiedene Möglichkeiten gibt es, zum Beispiel 20 Cent oder einen beliebigen anderen Betrag zu wechseln? Die Antwort liefern die folgenden beiden Funktionen.

(defproc change-with-coins (amount coins)
  (cond
    ((null? coins)
      nil)
    ((zero? amount)
      (list nil))
    (t
      (append
        (change-with-coins amount (rest coins))
        (let
          ((biggest-coin (first coins)))
          (if
            (< amount biggest-coin)
            nil
            (map-with
              (curry (cons biggest-coin _))
              (change-with-coins (- amount biggest-coin)
                                 coins))))))))

Die Funktion change-with-coins zählt alle Möglichkeiten auf, in denen der Betrag amount mit den Münzwerten in der Liste coins ausgedrückt werden kann. Die Funktion verwendet eine Fallunterscheidung:

I. Wenn keine Münzwerte zur Verfügung stehen (null? coins), dann gibt es keine Möglichkeit.

II. Wenn der zu wechselnde Wert Null ist (equal? amount 0), dann gibt es eine triviale Möglichkeit: keine Münze.

III. Ansonsten gibt es zwei Arten von Möglichkeiten: welche ohne die größte Münze aus der Liste (change-with-coins amount (rest coins)) und, falls der zu wechselnde Wert größer oder gleich (also nicht kleiner) der größten Münze ist, welche, bei denen diese verwendet wird.

Die Funktion change ruft die Funktion change-with-coins mit den möglichen Euro-Münzen auf:

(defproc change (amount)
  (change-with-coins
    amount
    (list 200 100 50 20 10 5 2 1)))

Für einen Betrag von 20 Cents ergeben sich 41 Möglichkeiten:

((1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1)
(2 2 2 2 2 1 1 1 1 1 1 1 1 1 1)
(2 2 2 2 2 2 1 1 1 1 1 1 1 1)
(2 2 2 2 2 2 2 1 1 1 1 1 1)
(2 2 2 2 2 2 2 2 1 1 1 1)
(2 2 2 2 2 2 2 2 2 1 1)
(2 2 2 2 2 2 2 2 2 2)
(5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(5 2 1 1 1 1 1 1 1 1 1 1 1 1 1)
(5 2 2 1 1 1 1 1 1 1 1 1 1 1)
(5 2 2 2 1 1 1 1 1 1 1 1 1)
(5 2 2 2 2 1 1 1 1 1 1 1)
(5 2 2 2 2 2 1 1 1 1 1)
(5 2 2 2 2 2 2 1 1 1)
(5 2 2 2 2 2 2 2 1)
(5 5 1 1 1 1 1 1 1 1 1 1)
(5 5 2 1 1 1 1 1 1 1 1)
(5 5 2 2 1 1 1 1 1 1)
(5 5 2 2 2 1 1 1 1)
(5 5 2 2 2 2 1 1)
(5 5 2 2 2 2 2)
(5 5 5 1 1 1 1 1)
(5 5 5 2 1 1 1)
(5 5 5 2 2 1)
(5 5 5 5)
(10 1 1 1 1 1 1 1 1 1 1)
(10 2 1 1 1 1 1 1 1 1)
(10 2 2 1 1 1 1 1 1)
(10 2 2 2 1 1 1 1)
(10 2 2 2 2 1 1)
(10 2 2 2 2 2)
(10 5 1 1 1 1 1)
(10 5 2 1 1 1)
(10 5 2 2 1)
(10 5 5)
(10 10)
(20))

Die unten verlinkte Datei enthält die Funktionen und kann mit dem Programm Calc ausgeführt werden.


change.sheet.xml