Why does my 2022 CS50 Cash greedy algorithm output a different number of coins then calculating manu-CodePudding

I'm taking a CS50x without prior knowledge of coding and am kind of stuck on the 2nd Week problem set 1. This is a greedy algorithm problem, in which the program calculates the number of coins to be given to pay back the change. The code passes CS50 automatic check, but it has issues on self-check.

Example: If I input 5 change on prompt, it is supposed to give me 2 coins - one nickel and one penny (5 1), but the code instead outputs 4 coins. If I input 160 change on prompt (same as cs50 check tool uses), it is supposed to give me 7 coins - six quarters and one dime ( 6 1). Instead, this code gives me 9 coins.

I'm scratching my head because if I use the calculator and go manually through the do while loops, it makes sense to output what it is supposed to be output, but, apparently, the program works differently.

Any ideas?

#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)
{
    //Ask for how much change is owed
    int cents = 0;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents <= 0);
    return cents;
}

int calculate_quarters(int cents)
{
    //Continue to check for how many quarters fit into input amout of change
    int quarters = 0;
    do
    {
        cents = cents - 25;
        quarters  ;
    }
    while (cents >= 25);
    return quarters;
}

int calculate_dimes(int cents)
{
    //Continue to check for how many cents fit into input amout of change after subtracting quarters
    int dimes = 0;
    do
    {
        cents = cents - 10;
        dimes  ;
    }
    while (cents >= 10);
    return dimes;
}

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

int calculate_pennies(int cents)
{
    int pennies = 0;
    do
    {
        cents = cents - 1;
        pennies  ;
    }
    while (cents >= 1);
    return pennies;
}

CodePudding user response：

You use do / while loops to compute the number of coins of each kind, hence you always count at least one coin of each kind, which is incorrect. For example if you have 2 cents to distribute, you will get 1 quarter and cents will become -3, then 1 dime and cents becomes -13, etc. resulting in 4 coins where 2 are needed.

This problem could have been diagnosed using a debugger or simply by adding a printf("quarters=%d, cents=%d\n", quarters, cents); statement before calling calculate_dimes(cents).

You should use while loops instead. More generally, you should avoid do / while loops. They are rarely the right tool.

Here is a modified version:

#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() {
    // 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("%d\n", coins);
    return 0;
}

int get_cents(void) {
    //Ask for how much change is owed
    for (;;) {
        int cents = get_int("Change owed: ");
        if (cents > 0)
            return cents;
        printf("number must be positive\n");
    }
}

int calculate_quarters(int cents) {
    //Continue to check for how many quarters fit into input amout of change
    int quarters = 0;
    while (cents >= 25) {
        cents = cents - 25;
        quarters  ;
    }
    return quarters;
}

int calculate_dimes(int cents) {
    //Continue to check for how many cents fit into input amout of change after subtracting quarters
    int dimes = 0;
    while (cents >= 10) {
        cents = cents - 10;
        dimes  ;
    }
    return dimes;
}

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

int calculate_pennies(int cents) {
    return cents;
}

Note however that there is a much simpler method using integer division and remainder:

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

int get_cents(void);

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

    // Calculate the number of quarters to give the customer
    int quarters = cents / 25;
    cents = cents % 25;

    // Calculate the number of dimes to give the customer
    int dimes = cents / 10;
    cents = cents % 10;

    // Calculate the number of nickels to give the customer
    int nickels = cents / 5;
    cents = cents % 5;

    // Calculate the number of pennies to give the customer
    int pennies = cents;

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

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

int get_cents(void) {
    //Ask for how much change is owed
    for (;;) {
        int cents = get_int("Change owed: ");
        if (cents > 0)
            return cents;
        printf("number must be positive\n");
    }
}

The above function is a good compromise... below is an alternative with all the operations combined as a single expression. You can study it for information as an example of smaller being more difficult to understand while producing code very similar to the previous version.

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

    // Compute the number of coins
    int coins = cents / 25   cents % 25 / 10   cents % 25 % 10 / 5   cents % 5;

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

CodePudding user response：

Your calculate_* functions all have a bug. What if the supplied cents starts out lower than the value you test for in your do { ... } while(cents >= value);? The functions would return 1. That is, they will always return 1 too much. They should all be rewritten as while(cents >= value) { ... }

int calc(int cents, int val) {
    int result = 0;
    while(cents >= val) {
          result;
        cents -= val;
    }
    return result;
}

int calculate_quarters(int cents) {
    return calc(cents, 25);
}

int calculate_dimes(int cents) {
    return calc(cents, 10);
}

int calculate_nickels(int cents) {
    return calc(cents, 5);
}

int calculate_pennies(int cents) {
    return calc(cents, 1);
}