For loop in a greedy algorithm isn't breaking, is asking for input infinitely

Question

I'm creating a greedy loop that finds the smallest amount of coins to be used to give back a value for CS50's pset1, and I can't decipher why my while loop is running infinitely.

I've tinkered with it and can't get it to escape.

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

// declare variable change_owed, num_coins, and input globally
float change_owed;
float input;
int num_coins;

int main(void)
{
    // makes sure the input is non-negative
    do
    {
        input = get_float("Amount paid\n");
    }
    while(change_owed <=0);
    input = round(input);

    // begin checking 
    while(input > 0)
    {
        if(input - .25 > 0) // quarters
        {
            num_coins++; // number of coins used, to be printed later, is incremented
            input = input - .25; // coin is subtracted from total
        }
        else if (input - .10 > 0) // dimes
        {
            num_coins++;
            input = input - .10;
        }   
        else if (input - .05 > 0) // nickels
        {
            num_coins++;
            input = input - .05;
        } 
        else if (input - .01 > 0) // pennies
        {
            num_coins++;
            input = input - .01;
        } 
    }
    printf("%i", num_coins);
}

Hi John, by not using >= what happens if you put in exactly a quarter (25 cents)? Once you hit 0.01 cents on input, 0.01-0.01 will never > 0. — Sean Brookins, May 16 '19 at 03:23
Floating point should never be used for currency calculations. It's entirely possible that `input - .01` is not greater than zero, even though `input` *is* greater than 0. All due to rounding errors. Of course, you also have the problem that Sean mentioned. — user3386109, May 16 '19 at 03:25
I actually realized he doesn't declare the value of change_owed. As soon as I put a value for that variable it works because he's using <= on the while loop that's above the while loop we focused on. — Sean Brookins, May 16 '19 at 03:28
Yes, the `do/while loop` also has a problem. So that brings the total number of bugs to 3, and counting. — user3386109, May 16 '19 at 03:33
Bug 4: `input = round(input)` forces `input` to be a whole number. So an input like `1.25` is rounded down to `1.00`. — user3386109, May 16 '19 at 03:41
Sean and 338, thanks for the help! I realize this a super newb question. I updated with your fixes, and encountered another issue that I'm really not sure how I missed. I was using ```else/if``` originally, which didn't make any sense. I deleted the else, but now it never prints anything but does exit the loop. — John Allison, May 16 '19 at 03:45
@JohnAllison Well, I propose that we're done here. 1201 found the bug that stopped the program from getting past the first loop. I would accept that answer, and then start a new question with the updated code. — user3386109, May 16 '19 at 03:53
It's probably also a good idea to read this thread: [Is floating point math broken](https://stackoverflow.com/questions/588004/is-floating-point-math-broken). — user3386109, May 16 '19 at 03:55

score 3 · Answer 1 · answered May 16 '19 at 03:26

The condition for your first do/while loop is change_owed <= 0, but there is nothing within the loop body that would change that value. Since it is a global that is initialized to 0, and is not changed before the loop enters, it will always have a value of 0 when the while condition is checked. This causes the loop to never terminate.

chux - Reinstate Monica · Accepted Answer · 2019-05-16T05:20:56.690

Issues

while(change_owed <=0); is an infinite loop as change_owed is always 0. Certainly should be while(input <=0);

input = round(input); makes little sense. round() does not round to the nearest 0.01, but to the nearest whole number.

Code's result results will always be quarters.

2nd loop is also a potential infinite loop.

Consider what happens when input > 0 and input - .01 > 0 is false -- > infinite loop. This can commonly come up once the input = round(input); is fixed.

while(input > 0)
{
    if(input - .25 > 0) // quarters
    { ... }
    else if (input - .10 > 0) // dimes
    { ... }
    else if (input - .05 > 0) // nickels
    { ... }
    else if (input - .01 > 0) // pennies
    { ... }
}

BTW,

Certainly if(input - .25 > 0) should be if(input - .25 >= 0) (or better if(input >= 0.25f). Use >= rather than >.

Larger picture. Use whole numbers.

int main(void) {
  //float change_owed;
  float input;
  long long num_coins = 0;
  do {
    input = get_float("Amount paid\n");
  } while (input <= 0);
  long long input_cents = llround(input * 100.0);

  // begin checking
  while (input_cents > 0) {
    if (input_cents >= 25) {
      num_coins++;
      input_cents -= 25;
    } else if (input_cents >= 10) {
      num_coins++;
      input_cents -= 10;
    } else if (input >= 5) {
      num_coins++;
      input_cents -= 5;
    } else if (input >= 1) {
      num_coins++;
      input_cents -= 1;
    }
  }
  printf("%lld\n", num_coins);
}

Additional efficiencies possible rather than simply num_coins++;

  if (input_cents > 0) {
    num_coins += input_cents/25;
    input_cents %= 25;
    num_coins += input_cents/10;
    input_cents %= 10;
    num_coins += input_cents/5;
    input_cents %= 5;
    num_coins += input_cents;
  }

For loop in a greedy algorithm isn't breaking, is asking for input infinitely

2 Answers2