this program is supposed to be greedy algorithms that meant to count the number of coins to make the change owed = 0 , the output is always less by 1

Question

#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 cents;
    do
    {
       cents = get_int("Change owe: ");
    }
    while (cents < 1);
    return cents;
}
int calculate_quarters(int cents)
{
    int quarters = 0;
    while(cents > 25)
    {
    cents = (cents - 25 );
    quarters++;
    }

    return quarters;
}

int calculate_dimes(int cents)
{
    // TODO
    int dimes = 0;
    while(cents > 10)
    {
        cents =(cents - 10);
        dimes++;
    }
    return dimes;
}

int calculate_nickels(int cents)
{
    // TODO
    int nickels = 0;
    while( cents > 5)
    {
        cents = (cents - 5);
        nickels++;
    }
    return nickels;
}

int calculate_pennies(int cents)
{
    // TODO
    int pennies = 0;
    while(cents > 1)
    {
        cents = (cents - 1);
        pennies++;
    }

    return pennies;
}

Answer 1

When there's a consistent off-by-one error, it's usually a good indication of a logic error in a counting algorithm. In this case, it's a logic error that's repeated in all of the coin functions.

Let's look at the while loop for quarters. (The same applies to all the coin denominations.)

while(cents > 25)

What happens when cents is exactly 25? It should execute the loop one more time to count the last quarter, but it doesn't. Why? Simply because it used ">" when it should use ">=". The result of this logic means that what should be the smallest coin counted will have one less coin counted than it is supposed to have, and the next smaller coin(s) will get counted when they shouldn't. For example, if cents = 50, it should count 2 quarters. Instead, it'll count 1 quarter, 2 dimes, no nickels, and 4 pennies. Oh, it'll also tend to undercount pennies by 1 for any amount, if pennies are counted.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)