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:

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