CS50 Pset1 Greedy, change algorithm

Question

The purpose of the code is to calculate the least amount of coins needed to produce correct amount of change given a dollar or cent user input. I'm just starting out and appreciate any pointers in how this code could/should be optimized.

The code works but I feel there is some redundancy with all those "while" loops. Using modulo math was another suggestion in order to solve the problem but I felt more comfortable using this solution for now.

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

int main (void)
{

// Variables//
float change;
int num = 0;
int quarter = 25;
int dime = 10;
int nickel = 5;
int penny = 1;


// Input of change//
do 
{
    printf("How much change is owed?  ");
    change = get_float();
}
while (change <= 0);

printf("%.2f\n",change);

// conversion from dollars to cents (need to look over use of rounding)

int cents = (change * 100);

//Coin count//

while ( cents >= quarter)
{
cents -= quarter;
num++;
}

while (cents >= dime)
{
cents -= dime;
num++;
}

while (cents >= nickel)
{
cents -= nickel;
num++;
}

while (cents >= penny)
{
cents -=penny;
num++;
}

printf("%d\n", num);
}

Answer 1

Be careful with that algorithm.

It looks pretty intuitive, but it would not work for some other coin values.

For example, if we need to deal 20 cents using coins of 17, 10 and 1, this greedy approach would give (17, 1, 1, 1) - 4 coins, whereas (10, 10) is just 2 coins.

Figuring out the difference - when your algorithm works and when it does not - would be an interesting exercise in itself.

Wasteful loops

while ( cents >= quarter) {
  cents -= quarter;
  num++;
}

You can replace it with something like:

num += cents / quarter;
cents = cents % quarter;

Note that if you put coin values in array, this can be done in a loop.

Generally, your code would spend most of its time waiting for user to type the number and will give answer immediately, there's little point in optimisation.

You should adopt some code style though, your indentation is inconsistent. Indentation makes code structure more immediately apparent. I don't think it's a problem for you now, but it would be a problem for you on bigger assignments and it would be a problem for other people who would have to read (and grade) your code. Take a look at one of these if your course does not have one.