Bargeld

Aufgabe

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!).

Wir wollen zu diesem Zweck ein Programm schreiben, das die minimal benötigte Anzahl an Münzen ausgibt, um den gewünschten Betrag an Wechselgeld in Cents zu erhalten, wie im Folgenden gezeigt:

Change owed: 25
1

Aber lassen Sie den Benutzer selbst Zahlen größer oder gleich 0 (d.h. den Betrag des Wechselgeldes) eingeben, so dass das Programm für jeden Betrag funktioniert:

Change owed: 70
4

Wenn die Eingabe des Benutzers nicht größer oder gleich 0 ist (oder wenn seine Eingabe überhaupt kein int ist!), fordern Sie den Benutzer immer wieder auf, eine passende Eingabe zu tätigen.

Implementieren Sie das Programm in C in einer Datei namens cash.c in einem Ordner namens cash.

Demo

Gierige Algorithmen

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¢), Dime (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!

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.

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

int main(void)
{

}

#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
}

#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);
}

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

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;
}

#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;
}

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 0 eingeben, gibt Ihr Programm dann 0 aus? (Sollte es nicht tun, sondern Sie erneut fragen.)
• 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:

check50 -l cs50/problems/2024/x/cash

Style

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

style50 cash.c