I'm writing a greedy algorithm (that has already caused me many headaches) that outputs the smallest number of coins that can be used for some monetary value, and I finally got code I was happy with, or so I thought. When inputting the value .41
, I'm returned 4 coins
which is correct - however, the input .01
returns 2 coins
and I have no idea why.
// declare variable change_owed, num_coins, and input globally
float change_owed = 0;
float dollars;
int cents;
int num_coins;
int main(void)
{
// makes sure the input is non-negative
do
{
dollars = get_float("Change owed:\n");
cents = round(dollars * 100);
}
while(cents <= 0);
// begin checking
while(cents - 25 >= 0) // quarters
{
num_coins++; // number of coins used, to be printed later, is incremented
cents = cents - 25; // coin is subtracted from total
}
while(cents - 10 >= 0) // dimes
{
num_coins++;
cents = cents >= 10;
}
while(cents - 5 >= 0) // nickels
{
num_coins++;
cents = cents - 5;
}
while(cents >= 0) // pennies
{
num_coins++;
cents = cents - 1;
}
printf("%i coins\n", num_coins);
}
As far as I can see you haven't initialized num_coins
int num_coins = 0;
Is there any reason why you are using while loops? integer arithmetic will do the same easier. Since cents is an int, dividing it by another int will return just the integer part (effectively rounded down).
num_coins = cents / 25; // returns the integer part, count of quarters
// This is an alternative to initialization
cents %= 25; // modulus operator returns the remainder
num_coins = num_coins + cents / 10; // count of dimes
cents %= 10;
num_coins = num_coins + cents / 5; // count of nickles
cents %= 5;
num_coins += cents; // cents must equal number of pennies required.
OK, I haven't tested the above code, so there may be some errors, but you get the idea.