Harvard CS50 Problem Set 1: greedy change-making algorithm

Question

The goal of this code is to take dollar or cents input from the user and give out minimum number of coins needed to pay that between quarters, dimes, nickels and pennies. If this code can be shortened, how would one do it?

#include <stdio.h>
#include <cs50.h>
#include <ctype.h>
#include <math.h>
int main(void)
{
float b;
do
 {
 printf("please give balance owing: ");
 b = GetFloat();
 }
while (b<0);
int v;
int q = 25;
int d = 10;
int n = 5;
int p = 1;
int count=0;
b=b*100;
int c=round(b);
int balance = c;
printf("%i\n", balance);
//printf("%.2f\n", round(c));
while(balance>=q) 
 {
 v=balance/q;
 count=count+v;
 balance=balance-(q*v);
 }
while(balance>=d) 
 {
 v=balance/d;
 count=count+v;
 balance=balance-(d*v);
 }
while(balance>=n) 
 {
 v=balance/n;
 count=count+v;
 balance=balance-(n*v);
 }
while(balance>=p) 
 {
 v=balance/p;
 count=count+v;
 balance=balance-(p*v);
 }
printf("the number of coins needed is: %i\n", count);
printf("balance after coins paid: %i\n", balance);
}

• user3629249: there is also the $.50, 1ドル.00, 20ドル.00 and perhaps some other coin denominations that I skipped. I would not discount these other coin denominations (although most of them are rarely seen outside of places like Reno NV. and Los Vegas NV.
• Bob Jarvis - Слава Україні: @user3629249 - it's "Las" Vegas. You're probably confusing it with its sister city, Lost Wages.

Answer 1

The first thing that sticks out to me is indentation. But I'm going to recommend some other changes, so I'll address indentation last.

Let's give our variables some better, more descriptive names, and let's declare our constants as constants. And since we're taking in a floating point number for input from the user, we need to compare that with other floating point numbers. Or we need to use it as an integer.

int const kVALUE_QUARTER = 25;
int const kVALUE_DIME = 10;
int const kVALUE_NICKEL = 5;
int const kVALUE_PENNY = 1;
float userInput = -1.0;
int balance = 0;
int coinCount = 0;
do {
 printf("please give balance owing: ");
 userInput = GetFloat();
} while (userInput < 0);
balance = (int)(userInput * 100.0);

Now, we can eliminate all of our loops using the modulo operator (%) and integer division.

// number of quarters:
coinCount += balance / kVALUE_QUARTER;
balance %= kVALUE_QUARTER;
// number of dimes:
coinCount += balance / kVALUE_DIME;
balance %= kVALUE_DIME;
// number of nickels:
coinCount += balance / kVALUE_NICKEL;
balance %= kVALUE_NICKEL;
// number of pennies:
coinCount += balance / kVALUE_PENNY;
balance %= kVALUE_PENNY;

Now let's put it all together and take a look at our indentation:

#include <stdio.h>
#include <cs50.h>
#include <ctype.h>
#include <math.h>
int main(void) {
 int const kVALUE_QUARTER = 25;
 int const kVALUE_DIME = 10;
 int const kVALUE_NICKEL = 5;
 int const kVALUE_PENNY = 1;
 float userInput = -1.0;
 int balance = 0;
 int coinCount = 0;
 do {
 printf("please give balance owing: ");
 userInput = GetFloat();
 } while (userInput < 0);
 balance = (int)(userInput * 100.0);
 // number of quarters:
 coinCount += balance / kVALUE_QUARTER;
 balance %= kVALUE_QUARTER;
 // number of dimes:
 coinCount += balance / kVALUE_DIME;
 balance %= kVALUE_DIME;
 // number of nickels:
 coinCount += balance / kVALUE_NICKEL;
 balance %= kVALUE_NICKEL;
 // number of pennies:
 coinCount += balance / kVALUE_PENNY;
 balance %= kVALUE_PENNY;
 printf("the number of coins needed is: %i\n", count);
 printf("balance after coins paid: %i\n", balance);
}

• 200_success: const int VALUE_QUARTER = 25; would be more idiomatic. The Hungarian k is pointless.
• nhgrif: @200_success is probably correct. I'm not a C-programmer. We tend to always use the k prefix in Objective-C.

Answer 2

I felt like adding another answer because this block in my other answer is quite repetitive:

// number of quarters:
coinCount += balance / kVALUE_QUARTER;
balance %= kVALUE_QUARTER;

And we can abstract this a little bit.

Let's write a function.

int coinsInBalance(int * balance, int coinValue) {
 int coinCount = balance / coinValue;
 balance %= coinValue;
 return coinCount;
}

Now, we can replace our repeated blocks with the following:

coinCount += coinsInBalance(&balance, kVALUE_QUARTER);
coinCount += coinsInBalance(&balance, kVALUE_DIME);
coinCount += coinsInBalance(&balance, kVALUE_NICKEL);
coinCount += coinsInBalance(&balance, kVALUE_PENNY);

• user2763557: cool. its good to see how a function would work in this situation in advance. I haven't started that lecture yet, so will definitely revisit this.

Answer 3

Why make this more complicated than it has to be?

#include <stdio.h>
void change(int cents)
 {
 int q, d, n, p;
 q = cents / 25;
 d = (cents - (q * 25)) / 10;
 n = ((cents - (q * 25) - (d * 10)) / 5);
 p = cents - (q * 25) - (d * 10) - (n * 5);
 printf("cents : %d --> quarters %d dimes %d nickels %d pennies %d\n",
 cents, q, d, n, p);
 }
int main(int argc, char **argv)
 {
 char str[1000];
 int cents;
 while(1)
 {
 fgets(str, 1000, stdin);
 cents = atoi(str);
 change(cents);
 }
 }

It's possible to eliminate all the temp variable declarations and just compute the values as we go:

void change(int cents)
 {
 printf("cents : %d --> quarters %d dimes %d nickels %d pennies %d\n",
 cents,
 (cents / 25),
 (cents - ((cents / 25) * 25)) / 10,
 ((cents - ((cents / 25) * 25) - ((((cents - ((cents / 25) * 25)) / 10) * 10))) / 5),
 cents - (((cents / 25) * 25) +
 (((cents - ((cents / 25) * 25)) / 10) * 10) + 
 (((cents - ((cents / 25) * 25) - ((((cents - ((cents / 25) * 25)) / 10) * 10))) / 5) * 5)));
 }

but this way lies madness. :-)

Share and enjoy.

• RubberDuck: "This way madness lies", so why suggest it then? You've effectively obfuscated the code and that does not make for a good answer here.
• Sam Watkins: The 1st chunk of code is good, the 2nd is "madness" as you say, a joke - just get rid of it so you can get some upvotes.
• Bob Jarvis - Слава Україні: "Why suggest it?" - to provide an example of what happens when good practices are ignored. Sometimes the negative example is useful to who why we do The Right Thing. And in my experience a touch of humor helps the lesson go down. YMMV.