# Bargeld

Quelle: https://dev.inf.zone/exercises/02/cash/

![US Münzen](https://dev.inf.zone/exercises/02/cash/coins.jpg)

## Aufgabe

**Auf einen Blick**

- **Was:** Ein Programm, das ausgibt, wie viele Münzen man mindestens braucht, um einen Betrag als Wechselgeld herauszugeben.
- **Datei:** `cash.c` in einem Ordner `cash`.
- **Eingabe:** das Wechselgeld in Cent (`Change owed: 70`). Bei einer negativen Zahl oder einer Eingabe, die gar keine Zahl ist, fragt das Programm erneut.
- **Ausgabe:** die kleinste Anzahl Münzen, hier `4`. Es gibt Münzen zu 25, 10, 5 und 1 Cent (US-Währung).

### So findet man die kleinste Anzahl Münzen

1. Die größte Münze nehmen, die noch in den Restbetrag passt.
2. Ihren Wert vom Restbetrag abziehen.
3. Das wiederholen, bis der Restbetrag 0 ist. Die Zahl der genommenen Münzen ist das Ergebnis.

**Beispiel** mit 41 Cent:

| Restbetrag | größte passende Münze | neuer Restbetrag |
| ---------- | --------------------- | ---------------- |
| 41         | 25                    | 16               |
| 16         | 10                    | 6                |
| 6          | 5                     | 1                |
| 1          | 1                     | 0                |

Das sind 4 Münzen. Bei US- und Euro-Münzen liefert dieses Verfahren immer die kleinstmögliche Anzahl. Warum es „gieriger Algorithmus“ heißt, steht am Ende der Seite unter „Zum Weiterlesen“.

## Demo

[Terminal-Aufzeichnung ansehen](https://asciinema.org/a/p6PlFqQgSWNWn4ggpIIaBOvIq)

## Ordner und Datei anlegen

Wie bei [Mario](https://dev.inf.zone/exercises/02/mario/#ordner-und-datei-anlegen), nur mit dem Namen `cash`:

```bash
cd
mkdir cash
cd cash
code cash.c
```

## Hilfestellung

Klicken Sie auf die folgenden Tipps, um einige Ratschläge zu erhalten. Versuchen Sie aber zunächst, selbst so weit wie möglich zu kommen.

**Beginnen Sie mit Code, der kompilierbar ist**

Auch wenn dieses Programm noch nichts tut, sollte es zumindest mit `make` kompiliert werden können!

```c
#include <cs50.h>
#include <stdio.h>

int main(void)
{

}
```

Denken Sie daran, dass Sie jetzt `cs50.h` und `stdio.h` eingebunden haben, zwei „Header-Dateien“, die Ihnen Zugang zu Funktionen geben, die Ihnen bei der Lösung dieses Problems helfen könnten.

**Versuchen Sie das Problem in Pseudocode zu beschreiben**

Wenn Sie unsicher sind, wie Sie das eigentliche Problem lösen können, unterteilen Sie es in kleinere Probleme, die Sie wahrscheinlich einfacher lösen können. Das Problem dieser Aufgabe besteht eigentlich nur aus einer Handvoll kleinerer Probleme:

1. Den Benutzer nach dem geschuldeten Wechselgeld in Cent fragen.
2. Berechnen, wie viele _Vierteldollar_ der Kunde bekommt. Ihren Wert von den Cents abziehen.
3. Berechnen, wie viele _Dimes_ der Kunde bekommt. Ihren Wert von den verbleibenden Cents abziehen.
4. Berechnen, wie viele _Nickel_ der Kunde bekommt. Ihren Wert von den verbleibenden Cents abziehen.
5. Berechnen, wie viele _Pfennige_ der Kunde bekommt. Ihren Wert von den verbleibenden Cents abziehen.
6. Die Anzahl der Vierteldollar, Dimes, Nickel und Pfennige addieren.
7. Diese Summe ausgeben.

Das ist der gierige Algorithmus, den Sie zur Lösung des Problems verwenden können. Fügen Sie diese kleineren Probleme nun in Form von Pseudocode als Kommentare ein, um sie dann nacheinander bearbeiten zu können:

```c
#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Prompt the user for change owed, in cents

    // Calculate how many quarters you should give customer
    // Subtract the value of those quarters from cents

    // Calculate how many dimes you should give customer
    // Subtract the value of those dimes from remaining cents

    // Calculate how many nickels you should give customer
    // Subtract the value of those nickels from remaining cents

    // Calculate how many pennies you should give customer
    // Subtract the value of those pennies from remaining cents

    // Sum the number of quarters, dimes, nickels, and pennies used
    // Print that sum
}
```

> [!WARNING]
> Der letzte Tipp zeigt Ihnen Schritt für Schritt den Großteil einer möglichen Lösung. Idealerweise schauen Sie sich diesen erst an, nachdem Sie die Aufgabe bearbeitet haben - oder zumindest ernsthaft versucht haben, die Aufgabe zu bearbeiten.

**Wandeln Sie den Pseudocode in Code um**

Überlegen Sie zunächst, wie Sie den Benutzer nach der Höhe der geschuldeten Cent-Beträge fragen können. Erinnern Sie sich daran, dass eine `do while`-Schleife hilfreich ist, wenn Sie etwas mindestens einmal und möglicherweise immer wieder tun wollen, wie in folgendem Beispiel:

```c
#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Prompt the user for change owed, in cents
    int cents;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents < 0);
}
```

Es ist ratsam, das Programm zu diesem Zeitpunkt bereits einmal mit `make` zu kompilieren. Ist Ihr Programm kompilierbar, testen Sie, ob es Sie erneut auffordert, einen Betrag einzugeben, wenn Sie weniger als 0 Cent eingeben (oder eine Eingabe wie „Katze“ machen).

Überlegen Sie nun, wie Sie berechnen können, wie viele Vierteldollar Sie dem Kunden geben sollten. Da wir einen gierigen Algorithmus verwenden, lautet die Frage: "Was ist die _größte_ Anzahl von Vierteldollar, die man dem Kunden geben kann?". Sie _könnten_ eine Lösung für dieses Problem in Ihre `main`-Funktion schreiben. Aber vielleicht ist es übersichtlicher, eine neue Funktion zu definieren: eine mit dem Namen `calculate_quarters`. Auf diese Weise können Sie sich besser auf die Logik zur Berechnung der Vierteldollar konzentrieren. Später können Sie diese Funktion in Ihre größere Lösung integrieren.

```c
int calculate_quarters(int cents)
{
    // Calculate how many quarters you should give customer
}
```

Die Funktion nimmt als Eingabe einen `int` entgegen, auf den innerhalb der Funktion über den Variablennamen `cents` zugegriffen werden kann. Und wegen des `int` vor dem Funktionsnamen sollte sie auch einen `int` zurückgeben. Das heißt, die Rückgabe (der `return`-Wert) dieser Funktion ist eine ganze Zahl: die Anzahl der Vierteldollar, die in `cents` passen. Im Code der Vorlesung [1. C](https://dev.inf.zone/lectures/1-c/) gibt es – wie Sie sich vielleicht erinnern können – mehrere Beispielprogramme, die zeigen, wie Funktionen einen Wert zurückgeben können. Schauen Sie sich diese noch einmal an, wenn Sie jetzt neugierig geworden sind oder es besser verstehen wollen.

Betrachten wir nun diese Möglichkeit einer Implementierung von `calculate_quarters`, bei der wir die Anzahl der Vierteldollar so lange erhöhen, bis wir keine Cents mehr haben, die wir in Vierteldollar umrechnen können:

```c
int calculate_quarters(int cents)
{
    // Calculate how many quarters you should give customer
    int quarters = 0;
    while (cents >= 25)
    {
        quarters++;
        cents = cents - 25;
    }
    return quarters;
}
```

Zugegeben, es gibt mindestens einen einfacheren Weg, um das Problem `calculate_quarters` zu lösen. Aber wir überlassen es Ihnen, diesen zu finden!

Wenn `calculate_quarters` wie vorgesehen funktioniert, können Sie diese Funktion in Ihr Programm integrieren. Achten Sie darauf, die "Signatur" der Funktion (d.h. `int calculate_quarters(int cents)`) oberhalb Ihrer `main`-Funktion zu "deklarieren", so dass Sie `calculate_quarters` in `main` verwenden können, während Sie die Funktion unterhalb von `main` definieren.

```c
#include <cs50.h>
#include <stdio.h>

int calculate_quarters(int cents);

int main(void)
{
    // Prompt the user for change owed, in cents
    int cents;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents < 0);

    // Calculate how many quarters you should give customer
    int quarters = calculate_quarters(cents);

    // Subtract the value of those quarters from cents
    cents = cents - (quarters * 25);
}

int calculate_quarters(int cents)
{
    // Calculate how many quarters you should give customer
    int quarters = 0;
    while (cents >= 25)
    {
        quarters++;
        cents = cents - 25;
    }
    return quarters;
}
```

Ein paar Probleme sind damit gelöst, aber es bleiben immer noch ein paar übrig! Erkennen Sie ein Muster, das Sie wiederverwenden können?

## Testen

Für dieses Programm sollten Sie Ihren Code manuell testen. Das ist eine gute Übung:

-   Wenn Sie `1` eingeben, fragt Ihr Programm Sie dann erneut? (Sollte es nicht tun.)
-   Wenn Sie `-1` eingeben, fragt Ihr Programm Sie dann erneut? (Sollte es.)
-   Wenn Sie `0` eingeben, gibt Ihr Programm dann `0` aus? (Sollte es.)
-   Wenn Sie `1` eingeben, gibt Ihr Programm dann `1` (d. h. einen Pfennig) aus?
-   Wenn Sie `4` eingeben, gibt Ihr Programm dann `4` aus (d. h. vier Pfennige)?
-   Wenn Sie `5` eingeben, gibt Ihr Programm dann `1` aus (d. h. einen Nickel)?
-   Wenn Sie `24` eingeben, gibt Ihr Programm dann `6` aus (d. h. zwei Dimen und vier Pfennige)?
-   Wenn Sie `25` eingeben, gibt Ihr Programm dann `1` aus (d. h. einen Vierteldollar)?
-   Wenn Sie `26` eingeben, gibt Ihr Programm dann `2` aus (d. h. einen Vierteldollar und einen Pfennig)?
-   Wenn Sie `99` eingeben, gibt Ihr Programm dann `9` aus (d. h. drei Vierteldollar, zwei Dimen und vier Pfennige)?

### Korrektheit

Führen Sie in Ihrem Terminal den folgenden Befehl aus, um die Korrektheit Ihrer Arbeit zu überprüfen:

```bash
check50 -l inf-zone/exercises/2026/cash
```

### Style

Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit `style50` zu analysieren:

```bash
style50 cash.c
```

## Abgeben

Geben Sie im Ordner `cash` ab:

```bash
inf upload cash
```

Danach sehen Sie, welche Tests Ihr Programm besteht und ob die Übung für die Bonuspunkte zählt. Wie Sie `inf` installieren und sich anmelden, steht unter [Abgeben mit `inf`](https://dev.inf.zone/faq/uebung-solutions/#inf-installieren).

## Zum Weiterlesen: Gierige Algorithmen

Für die Lösung der Aufgabe nicht nötig.

Angenommen, Sie arbeiten in einem Geschäft und ein Kunde gibt Ihnen `1,00 $ (100 Cent)` für Süßigkeiten, die `0,50 $ (50 Cent)` kosten. Sie müssen dem Kunden das "Wechselgeld" auszahlen, also den Betrag, der nach dem Bezahlen der Süßigkeiten übrig bleibt. Wenn Sie Wechselgeld herausgeben, möchten Sie in der Regel die Anzahl der Münzen, die Sie pro Kunde herausgeben, so gering wie möglich halten, damit Ihnen nicht die Münzen ausgehen (oder Sie den Kunden verärgern!).

Glücklicherweise hat die Informatik dem Kassenpersonal auf der ganzen Welt Methoden zur Minimierung der benötigten Münzen bereitgestellt: gierige Algorithmen.

Nach Angaben des National Institute of Standards and Technology (NIST) ist ein gieriger Algorithmus ein Algorithmus, der bei der Suche nach einer Antwort immer die beste unmittelbare oder lokale Lösung wählt. Gierige Algorithmen finden bei einigen Optimierungsproblemen die insgesamt oder global optimale Lösung, können aber bei einigen Instanzen anderer Probleme Lösungen ausgeben, die nicht optimal sind.

Was bedeutet das alles? Nehmen wir an, ein Kassierer muss einem Kunden Wechselgeld geben und in der Kasse des Kassierers befinden sich Vierteldollar (25¢), Dimes (10¢), Nickel (5¢) und Pfennigmünzen (1¢). Das zu lösende Problem besteht darin, zu entscheiden, welche Münzen und wie viele davon dem Kunden auszuhändigen sind. Stellen Sie sich einen "gierigen" Kassierer als jemanden vor, der mit jeder Münze, die er aus der Kasse nimmt, einen möglichst großen Anteil von diesem Problem beseitigen will. Wenn einem Kunden beispielsweise 41¢ geschuldet werden, beträgt der größte erste (d.h. der beste sofortige oder lokale) Anteil, der verwendet werden kann, 25¢. Dieser Anteil ist insofern "am besten", als er uns schneller als jede andere Münze näher an 0¢ bringt. Beachten Sie, dass ein Anteil dieser Größe das 41¢-Problem auf ein 16¢-Problem reduzieren würde, da 41 − 25 = 16. Das heißt, der Rest ist ein ähnliches, aber kleineres Problem. Natürlich wäre ein weiterer Anteil von 25 Cent zu groß (vorausgesetzt, der Kassierer möchte kein Geld verlieren), und so würde unser gieriger Kassierer zu einem Anteil von 10 Cent übergehen, womit er oder sie ein verbleibendes Problem von 6 Cent hätte. An diesem Punkt verlangt die "Gier" des Algorithmus nach einem 5¢-Stück, gefolgt von einem 1¢-Stück, womit das Problem gelöst ist. Der Kunde erhält einen Vierteldollar, einen Dime, einen Nickel und einen Pfennig: insgesamt vier Münzen.

Es zeigt sich, dass dieser gierige Ansatz (d. h. Algorithmus) nicht nur lokal optimal ist, sondern auch global für die amerikanische Währung (und auch für die der Europäischen Union). Das heißt, solange ein Kassierer genug von jeder Münze hat, wird dieser Ansatz von der größten zur kleinsten Münze die geringstmögliche Anzahl an Münzen ergeben. Wie viele Münzen sind also nötig, wenn ein Kunde 97¢ Wechselgeld bekommen soll? Nun, Ihr Programm wird uns das hoffentlich bald beantworten können!