Язык Си: сколько монет дает кассир

Изучая жадные алгоритмы (Greedy Algorithms) на языке программирования C в CS50 (Гарвард), давайте решим задачу про монеты (Cash.c). Допустим, что вам нужно дать сдачу покупателю в магазине и вы хотите свести к минимуму количество монет, которые вы выдаете каждому покупателю.  Если вы кассир, то у вас в кассе есть монеты (25 центов), десять центов (10 центов), пять центов (5 центов) и пенни (1 цент). Как решить, какие монеты и в каком количестве передать покупателю?

Представьте себе «жадного» кассира, который хочет получить как можно больший кусок от этой проблемы с каждой монетой, которую он достает из ящика. Представим, что вы должны покупателю 42 цента, то самая большая первая монета, которую можно взять, — это 25 центов. Этот выбор сократит сумму, которую нужно отдать, до 17 центов, поскольку 42 — 25 = 17. Получается, что при помощи более мелких монет нам нужно будет решить уже более мелкую задачу. Этот подход от наибольшего к наименьшему даст наименьшее возможное количество монет в сдаче.

Решение (Игроглаз):

#include <stdio.h>

int get_cents(void);
int calculate_quarters(int cents);
int calculate_dimes(int cents);
int calculate_nickels(int cents);
int calculate_pennies(int cents);

int main(void)
{
    // Ask how many cents the customer is owed
    int cents = get_cents();

    // Calculate the number of quarters to give the customer
    int quarters = calculate_quarters(cents);
    cents = cents - quarters * 25;

    // Calculate the number of dimes to give the customer
    int dimes = calculate_dimes(cents);
    cents = cents - dimes * 10;

    // Calculate the number of nickels to give the customer
    int nickels = calculate_nickels(cents);
    cents = cents - nickels * 5;

    // Calculate the number of pennies to give the customer
    int pennies = calculate_pennies(cents);
    cents = cents - pennies * 1;

    // Sum coins
    int coins = quarters + dimes + nickels + pennies;

    // Print total number of coins to give the customer
    printf("%i\n", coins);

    getchar();
    getchar();
    return 0;
}

int get_cents(void)
{
    int cents = 0;

    do
    {
        printf("How much change I should give you in cents?\n");
        scanf("%d", &cents);
        while (getchar() != '\n') ; // clear buffer
    }
    while (cents < 1);

    return cents;
}

int calculate_quarters(int cents)
{
    int quarters = 0;

    while (cents > 24)
    {
        quarters++;
        cents = cents - 25;
    }

    return quarters;
}

int calculate_dimes(int cents)
{
    int dimes = 0;

    while (cents > 9)
    {
        dimes++;
        cents = cents - 10;
    }

    return dimes;
}

int calculate_nickels(int cents)
{
    int nickels = 0;

    while (cents > 4)
    {
        nickels++;
        cents = cents - 5;
    }

    return nickels;
}

int calculate_pennies(int cents)
{
    int pennies = 0;

    while (cents > 0)
    {
        pennies++;
        cents = cents - 1;
    }

    return pennies;
}

Решение (Штукенция):

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

int get_cents(void);
int calculate_quarters(int cents);
int calculate_dimes(int cents);
int calculate_nickels(int cents);
int calculate_pennies(int cents);

int main(void)
{
    // Ask how many cents the customer is owed
    int cents = get_cents();

    // Calculate the number of quarters to give the customer
    int quarters = calculate_quarters(cents);
    cents = cents - quarters * 25;

    // Calculate the number of dimes to give the customer
    int dimes = calculate_dimes(cents);
    cents = cents - dimes * 10;

    // Calculate the number of nickels to give the customer
    int nickels = calculate_nickels(cents);
    cents = cents - nickels * 5;

    // Calculate the number of pennies to give the customer
    int pennies = calculate_pennies(cents);
    cents = cents - pennies * 1;

    // Sum coins
    int coins = quarters + dimes + nickels + pennies;

    // Print total number of coins to give the customer
    printf("%i\n", coins);
}

int get_cents(void)
{
    int n;
    do
    {
        n = get_int("Type number of cents\n");
    }
    while (n < 0);
    printf("Your number of cents is:%i\n",n);
    return n;
}

int calculate_quarters(int cents)
{
    int quarters;
    if(cents>=25)
    {
        quarters = cents / 25;
    }
    else
    {
        quarters = 0;
    }

    return quarters;
}

int calculate_dimes(int cents)
{
    int dimes;
    if(cents>=10)
    {
        dimes = cents / 10;
    }
    else
    {
        dimes = 0;
    }

    return dimes;
}

int calculate_nickels(int cents)
{
    int nickels;
    if(cents>=5)
    {
        nickels = cents / 5;
    }
    else
    {
        nickels = 0;
    }

    return nickels;
}

int calculate_pennies(int cents)
{
{
    int pennies;
    if(cents>=1)
    {
        pennies = cents;
    }
    else
    {
        pennies = 0;
    }

    return pennies;
}
}

Если введем в программу 41 цент, то ответ получится 4 (при помощи четырех монет можно выдать сдачу):

И после проверки багов программы выглядит так:

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

int get_cents(void);
int calculate_quarters(int cents);
int calculate_dimes(int cents);
int calculate_nickels(int cents);
int calculate_pennies(int cents);

int main(void)
{
    // Ask how many cents the customer is owed
    int cents = get_cents();

    // Calculate the number of quarters to give the customer
    int quarters = calculate_quarters(cents);
    cents = cents - quarters * 25;

    // Calculate the number of dimes to give the customer
    int dimes = calculate_dimes(cents);
    cents = cents - dimes * 10;

    // Calculate the number of nickels to give the customer
    int nickels = calculate_nickels(cents);
    cents = cents - nickels * 5;

    // Calculate the number of pennies to give the customer
    int pennies = calculate_pennies(cents);
    cents = cents - pennies * 1;

    // Sum coins
    int coins = quarters + dimes + nickels + pennies;

    // Print total number of coins to give the customer
    printf("%i\n", coins);
}

// Get input from user
int get_cents(void)
{
    int n;
    do
    {
        n = get_int("Type number of cents\n");
    }
    while (n < 0);
    printf("Your number of cents is:%i\n", n);
    return n;
}

// Check amount of quarters
int calculate_quarters(int cents)
{
    int quarters;
    if (cents >= 25)
    {
        quarters = cents / 25;
    }
    else
    {
        quarters = 0;
    }

    return quarters;
}

// Check amount of dimes
int calculate_dimes(int cents)
{
    int dimes;
    if (cents >= 10)
    {
        dimes = cents / 10;
    }
    else
    {
        dimes = 0;
    }
    return dimes;
}

// Check amount of nickels
int calculate_nickels(int cents)
{
    int nickels;
    if (cents >= 5)
    {
        nickels = cents / 5;
    }
    else
    {
        nickels = 0;
    }
    return nickels;
}

// Check amount of pennies
int calculate_pennies(int cents)
{
    int pennies;
    if (cents >= 1)
    {
        pennies = cents;
    }
    else
    {
        pennies = 0;
    }
    return pennies;
}