While studying Greedy Algorithms at CS50 (Harvard), let’s solve the problem about coins (Cash.c). Let’s say you need to give change to a customer in a store and you want to minimize the number of coins you give out to each customer. If you are a cashier, then you have coins (25 cents), ten cents (10 cents), five cents (5 cents) and a penny (1 cent) in the cash register. How to decide which coins and how much to transfer to the buyer?
Imagine a “greedy” cashier who wants to get as big a chunk out of this problem as possible with every coin he takes out of the drawer. Suppose you owe the customer 42 cents, then the largest first coin you can take is 25 cents. This choice will reduce the amount to be given away to 17 cents, since 42 – 25 = 17. It turns out that with the help of smaller coins we will need to solve a smaller problem. This approach from largest to smallest will give the smallest possible number of coins in change.
Solution (Igroglaz):
#include <stdio.h>
int get_cents(void);
int calculate_quarters(int cents);
int calculate_dimes(int cents);
int calculate_nickels(int cents);
int calculate_pennies(int cents);
int main(void)
{
// Ask how many cents the customer is owed
int cents = get_cents();
// Calculate the number of quarters to give the customer
int quarters = calculate_quarters(cents);
cents = cents - quarters * 25;
// Calculate the number of dimes to give the customer
int dimes = calculate_dimes(cents);
cents = cents - dimes * 10;
// Calculate the number of nickels to give the customer
int nickels = calculate_nickels(cents);
cents = cents - nickels * 5;
// Calculate the number of pennies to give the customer
int pennies = calculate_pennies(cents);
cents = cents - pennies * 1;
// Sum coins
int coins = quarters + dimes + nickels + pennies;
// Print total number of coins to give the customer
printf("%i\n", coins);
getchar();
getchar();
return 0;
}
int get_cents(void)
{
int cents = 0;
do
{
printf("How much change I should give you in cents?\n");
scanf("%d", ¢s);
while (getchar() != '\n') ; // clear buffer
}
while (cents < 1);
return cents;
}
int calculate_quarters(int cents)
{
int quarters = 0;
while (cents > 24)
{
quarters++;
cents = cents - 25;
}
return quarters;
}
int calculate_dimes(int cents)
{
int dimes = 0;
while (cents > 9)
{
dimes++;
cents = cents - 10;
}
return dimes;
}
int calculate_nickels(int cents)
{
int nickels = 0;
while (cents > 4)
{
nickels++;
cents = cents - 5;
}
return nickels;
}
int calculate_pennies(int cents)
{
int pennies = 0;
while (cents > 0)
{
pennies++;
cents = cents - 1;
}
return pennies;
}
Solution (Shtukensia):
#include <cs50.h>
#include <stdio.h>
int get_cents(void);
int calculate_quarters(int cents);
int calculate_dimes(int cents);
int calculate_nickels(int cents);
int calculate_pennies(int cents);
int main(void)
{
// Ask how many cents the customer is owed
int cents = get_cents();
// Calculate the number of quarters to give the customer
int quarters = calculate_quarters(cents);
cents = cents - quarters * 25;
// Calculate the number of dimes to give the customer
int dimes = calculate_dimes(cents);
cents = cents - dimes * 10;
// Calculate the number of nickels to give the customer
int nickels = calculate_nickels(cents);
cents = cents - nickels * 5;
// Calculate the number of pennies to give the customer
int pennies = calculate_pennies(cents);
cents = cents - pennies * 1;
// Sum coins
int coins = quarters + dimes + nickels + pennies;
// Print total number of coins to give the customer
printf("%i\n", coins);
}
int get_cents(void)
{
int n;
do
{
n = get_int("Type number of cents\n");
}
while (n < 0);
printf("Your number of cents is:%i\n",n);
return n;
}
int calculate_quarters(int cents)
{
int quarters;
if(cents>=25)
{
quarters = cents / 25;
}
else
{
quarters = 0;
}
return quarters;
}
int calculate_dimes(int cents)
{
int dimes;
if(cents>=10)
{
dimes = cents / 10;
}
else
{
dimes = 0;
}
return dimes;
}
int calculate_nickels(int cents)
{
int nickels;
if(cents>=5)
{
nickels = cents / 5;
}
else
{
nickels = 0;
}
return nickels;
}
int calculate_pennies(int cents)
{
{
int pennies;
if(cents>=1)
{
pennies = cents;
}
else
{
pennies = 0;
}
return pennies;
}
}
If we enter 41 cents into the program, then the answer will be 4 (with the help of four coins you can give change):
And after checking bugs my code looks like:
#include <cs50.h>
#include <stdio.h>
int get_cents(void);
int calculate_quarters(int cents);
int calculate_dimes(int cents);
int calculate_nickels(int cents);
int calculate_pennies(int cents);
int main(void)
{
// Ask how many cents the customer is owed
int cents = get_cents();
// Calculate the number of quarters to give the customer
int quarters = calculate_quarters(cents);
cents = cents - quarters * 25;
// Calculate the number of dimes to give the customer
int dimes = calculate_dimes(cents);
cents = cents - dimes * 10;
// Calculate the number of nickels to give the customer
int nickels = calculate_nickels(cents);
cents = cents - nickels * 5;
// Calculate the number of pennies to give the customer
int pennies = calculate_pennies(cents);
cents = cents - pennies * 1;
// Sum coins
int coins = quarters + dimes + nickels + pennies;
// Print total number of coins to give the customer
printf("%i\n", coins);
}
// Get input from user
int get_cents(void)
{
int n;
do
{
n = get_int("Type number of cents\n");
}
while (n < 0);
printf("Your number of cents is:%i\n", n);
return n;
}
// Check amount of quarters
int calculate_quarters(int cents)
{
int quarters;
if (cents >= 25)
{
quarters = cents / 25;
}
else
{
quarters = 0;
}
return quarters;
}
// Check amount of dimes
int calculate_dimes(int cents)
{
int dimes;
if (cents >= 10)
{
dimes = cents / 10;
}
else
{
dimes = 0;
}
return dimes;
}
// Check amount of nickels
int calculate_nickels(int cents)
{
int nickels;
if (cents >= 5)
{
nickels = cents / 5;
}
else
{
nickels = 0;
}
return nickels;
}
// Check amount of pennies
int calculate_pennies(int cents)
{
int pennies;
if (cents >= 1)
{
pennies = cents;
}
else
{
pennies = 0;
}
return pennies;
}