MoonOwl22 - 8 months ago 40

C Question

I am trying to figure out what the minimum number of coins required to pay back change is by using a "greedy algorithm". The program I have written below is working as expected if the user enters a multiple of only one of the constant integers. However, when it comes to to dealing with more than one coin, the program just pauses forever.

I think that the problem is in my CountGreed function's

`while`

I know this is trivial and there is repetition in the loop through the conditional statements which then brings me to the stated question. Multiples of 0.25, 0.10, 0.05 and 0.01 are working well if entered by the user. For example, 1.00, 1.25, 0.20 but not 0.30, 1.13, 0.26, etc.

`#include "cs50.h" // Contains declaration for GetFloat()`

#include <stdio.h>

#include <math.h>

float PromptChange(void); // Returns customer change in dollars

int ConvertToCents(float); // Returns a conversion from dollars to cents

int CountGreed(int); // Returns the minimum number of coins for which change can be made

int main (void)

{

float Dollars = PromptChange();

int Cents = ConvertToCents(Dollars);

int CoinCount = CountGreed(Cents);

printf("The minimum number of coins required to give back change is %i.\n", CoinCount);

return 0;

}

float PromptChange(void)

{

float Dollars;

do {

printf ("Owed change: $");

Dollars = GetFloat ();

} while (Dollars < 0);

return Dollars;

}

int ConvertToCents(float Dollars)

{

float Cents = Dollars * 100;

int IntCents = (int)roundf(Cents);

return IntCents;

}

int CountGreed(int IntCents)

{

const int Quarter = 25, Dime = 10, Nickel = 5, Penny = 1;

int SubCoinCount = 0;

int CoinCount = 0;

int Remainder = 0;

while (IntCents) {

if (IntCents >= Quarter) {

SubCoinCount = IntCents / Quarter;

CoinCount += SubCoinCount;

Remainder += IntCents % Quarter;

IntCents = Remainder;

} else if (IntCents < Quarter && IntCents >= Dime) {

SubCoinCount = IntCents / Dime;

CoinCount += SubCoinCount;

Remainder += IntCents % Dime;

IntCents = Remainder;

} else if (IntCents < Dime && IntCents >= Nickel) {

SubCoinCount = IntCents / Nickel;

CoinCount += SubCoinCount;

Remainder += IntCents % Nickel;

IntCents = Remainder;

} else if (IntCents < Nickel && IntCents >= Penny) {

SubCoinCount = IntCents / Nickel;

CoinCount += SubCoinCount;

Remainder += IntCents % Dime;

IntCents = Remainder;

}

}

return CoinCount;

}

I pasted the whole main.c file so that the flow of my entire program can be seen clearly though the problem is with the loop. I have tried this on multiple compilers just to make sure that it is my fault.

Answer

This:

```
else if (IntCents < Nickel && IntCents >= Penny) {
SubCoinCount = IntCents / Nickel;
CoinCount += SubCoinCount;
Remainder += IntCents % Dime;
IntCents = Remainder;
}
```

should be this:

```
else if (IntCents < Nickel && IntCents >= Penny) {
SubCoinCount = IntCents / Penny; // <--- Change to Penny, or just remove
CoinCount += SubCoinCount;
Remainder += IntCents % Penny; // <--- Change to Penny
IntCents = Remainder;
}
```

Your four `if`

cases are identical except for the denomination of the coin, which means they're crying out to be put into a separate function. Doing that is a great way to avoid making errors like this in one or some of your cases, because you're only writing it once.

I also suspect:

```
Remainder += IntCents % Dime;
```

should be:

```
Remainder = IntCents % Dime;
```

otherwise `Remainder`

will increase endlessly, and `IntCents`

will never get to zero. `Remainder`

actually becomes unnecessary, in this case, and you can assign the result directly to `IntCents`

.

But there's a simpler way of doing this entirely. Here's a suggested alternative, for your perusal:

```
#include <stdio.h>
// This cries out to be its own function
int coin_count(int cents, int denomination, int * remainder)
{
*remainder = cents % denomination;
return cents / denomination;
}
// Better way
int CountGreed(int IntCents)
{
static const int Quarter = 25, Dime = 10, Nickel = 5, Penny = 1;
int CoinCount = 0;
while ( IntCents > 0 ) {
if ( IntCents >= Quarter ) {
CoinCount += coin_count(IntCents, Quarter, &IntCents);
} else if ( IntCents >= Dime ) {
CoinCount += coin_count(IntCents, Dime, &IntCents);
} else if ( IntCents >= Nickel ) {
CoinCount += coin_count(IntCents, Nickel, &IntCents);
} else if ( IntCents >= Penny ) {
CoinCount += coin_count(IntCents, Penny, &IntCents);
}
}
return CoinCount;
}
// Even better way
int CountGreed2(int IntCents)
{
static const int coins[4] = {25, 10, 5, 1};
int CoinCount = 0;
for ( int i = 0; i < 4; ++i ) {
if ( IntCents >= coins[i] ) {
CoinCount += coin_count(IntCents, coins[i], &IntCents);
}
}
return CoinCount;
}
int main(void) {
printf("Coins for $1.25 (should be 5): (%d)\n", CountGreed(125));
printf("Coins for $1.00 (should be 4): (%d)\n", CountGreed(100));
printf("Coins for $0.96 (should be 6): (%d)\n", CountGreed(96));
printf("Coins for $1.25 (should be 5): (%d)\n", CountGreed2(125));
printf("Coins for $1.00 (should be 4): (%d)\n", CountGreed2(100));
printf("Coins for $0.96 (should be 6): (%d)\n", CountGreed2(96));
return 0;
}
```

which outputs:

```
paul@local:~/Documents/src/sandbox$ ./coins
Coins for $1.25 (should be 5): (5)
Coins for $1.00 (should be 4): (4)
Coins for $0.96 (should be 6): (6)
Coins for $1.25 (should be 5): (5)
Coins for $1.00 (should be 4): (4)
Coins for $0.96 (should be 6): (6)
paul@local:~/Documents/src/sandbox$
```

The need for a separate function in `CountGreed2()`

is less obvious, since you're only writing it once anyway, but tastes vary.