CS50’s 1st Problem Set – Greedy Algorithms

woman paying with credit card
Photo by Andrea Piacquadio on Pexels.com

In order to solve the second exercise of the 1st problem set, “Cash”, I had to work with greedy algorithms. To put it simply, greedy algorithms help you make optimal choices to use minimum resources for reaching a goal.

In the “cash” scenario, we are cashiers that need to give back change to customers with a minimum amount of coins. The program should first prompt the user for input (in this case, how much change is owed), and configure some functions in c to determine the minimum amount of coins that could be used to give back the change. Due to the inherent imprecision of floating-point values, we were advised to convert dollars to cents (from a float to an int) to avoid possible errors. The coins we would be working with were American quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢).

As I learnt in the previous exercise, I wrote some pseudocode first to figure out the steps:

  1. Prompt user for change owed. Accept only positive values.
  2. Convert dollar to cents, that is, float to int (multiply them by 100).
  3. Declare variables for dollars (float), cents (int) and coins (int)
  4. Loop one: If input >= 25 or multiple -> then give x quarter coins and move to next loop. Otherwise, move to next loop directly.
  5. Loop two: If input >= 10 or 2×10 -> then give x dime coins and move to next loop. Otherwise, move to next loop directly.
  6. Loop three: If input >= 5 -> then give x nickle coins and move to the next loop. Otherwise, move to next lop directly.
  7. If prompted value <5 -> number of coins = number of pennies.
  8. Sum up the results of all loops and print out the number of coins to the screen.
  9. Set new line

First, I included the libraries:

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

Then, I declared the variables (having them at the top is not the best practice, but since the exercise was short and they would be visible, I decided to declare all of them before prompting the user for input)

// declare variables
float dollars;
int cents;
int coins = 0;

Next, I prompted the user for change owed, set a condition for repeating the loop until the input is a positive value, and rounded dollars to cents:

// Prompt user for change owed
do
{
dollars = get_float("How much change is owed?:");
}
// repeat until input is positive
while (dollars < 0);
//round dollars to cents
cents = round(dollars * 100);

Finally, I defined the loops for counting the coins and printed out the result

// loop to get minimum number of coins
while (cents >= 25)
{
cents = cents - 25;
coins++;
}
while (cents >= 10)
{
cents = cents - 10;
coins++;
}
while (cents >= 5)
{
cents = cents - 5;
coins++;
}
while (cents >= 1)
{
cents--;
coins++;
}
//number of coins
printf("%d\n", coins);
}

This is the result:

Screen Shot 2020-05-19 at 20.22.38

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s