BRIAN: In Cash, your task is going to be to write a program that
takes the role of a cashier figuring out how many coins to give to a customer
to make a certain amount of change.
In the US, we have four main coin denominations.
We have pennies, which are worth $0.01.
Nickels, worth $0.05, dimes, worth $0.10, and quarters, worth $0.25.
So let's consider, for example, how you might make change for $0.30.
You could, for example, use 30 pennies, which would require 30 coins.
But there are other ways to make as well.
For example, we could use three dimes, each worth $0.10,
and use a total of three coins there.
Or alternatively, we could use a quarter, worth $0.25, and a nickel,
worth $0.05.
In this case, only using two coins.
Your task in this problem is going to be,
given some amount of change, what is the fewest number of coins
you could use to provide that change to the customer?
How are we going to do that?
Well, we're going to do it using a greedy algorithm.
Which in this case means that at every step of the algorithm,
we're going to use the largest value coin possible.
If we're able to use a quarter to give us change, we'll use a quarter.
If we're not able to use a quarter, then we'll consider dimes.
If we're able to use a dime we'll use that, so on and so forth.
What does that actually look like in practice?
Well, let's take another example.
Let's try and make change for $0.61, for example.
In order to do that, the greedy algorithm
says that we should start by using the highest value coin we possibly can,
which in this case is a quarter.
So if we use a quarter, we've now used one coin.
And how much change is still owed?
Well, we started out by owning $0.61, and now we've given the customer $0.25,
so there's $0.36 in change that's still owed.
What coin do we use next?
Well again, the greedy algorithm says we should
use the largest value coin we possibly can, which in this case
is $0.25, another quarter.
We've now used two coins, and we now owe $0.11 to the customer.
What next?
Well, we can't use quarters anymore.
The change owed is $0.11, which is less than $0.25, the value of a quarter.
So we'll instead need to look to the next coin, a dime.
And we can use a dime in this case.
Using one dime, that brings our total coin count up to three cents.
And now there's only cent of change that we still owe.
A dime is not going to work for that and neither will a nickel.
So with the remaining change, we're going to use one penny in order
to make that amount of change.
And so the fewest number of coins we can use to make $0.61 worth of change
is four.
And this is what your program is going to do.
When you compile and run your program, you should run your program as ./cash,
and your program should prompt the user to type in how much change is owed
in dollars.
So if the user types in 0.61, for example, representing $0.61,
then your program should output four because we can use four coins in order
to make $0.61 of change.
What is your program then need to do?
So you should first prompt the user for some amount of change in dollars.
And then, using the largest coins you possibly can,
keep track of how many coins you've used until you've made change for the amount
that the user provided as input.
And then finally, you should print out that number of coins to the screen
so that the user can see it.
Let's take a closer look at how you might do each of these individual steps
starting with prompting the user for input.
So to prompt the user for input, we're going
to ask the user to type in some number of dollars.
So it might be 0.61, for example, to represent $0.61.
To do this, get int isn't going to work, because get int
asks for an integer number and a number like 0.61 isn't an integer.
We'll instead want to use a function like get
float, which gets a floating point number that might have a decimal in it,
for example.
But you'll also want to check to make sure that the user only types
in non-negative inputs.
If the user types in a negative amount, like -$1, for example,
you should re-prompt the user to type in another dollar value until they give
you a non-negative value.
How might you go about doing that?
Well, you can consider using a do while loop.
A loop that repeats some block of code, at least
once, but might continue to repeat it if some particular condition is true.
So think about what block of code you might want to repeat
and under what condition you would want to re-prompt the user to type
in some input again, and fill in those blanks
to figure out how you might use a do while loop
to prompt the user for input.
The next step is that the user is typing in their input in dollars,
but ultimately, most of our logic here has to do with cents.
So what you might want to do is convert the number of dollars
the user typed in to cents.
Of course there are 100 cents in a bucket.
So if you take the dollar value and multiply it by 100
you'll get some number of cents.
You'll also want to be sure round the number of cents to the nearest penny
to make sure that your number of cents is in fact an integer.
There's a function called round, declared in math.h,
that o can take advantage of, that takes a floating point number
and rounds it to the nearest integer.
And this will help to handle issues of floating point imprecision as well.
So once you've converted some number of dollars into some number of cents,
the next step is to figure out how many coins you would need in order
to make that amount of change.
How are you going to do that?
Well, you'll want to keep track of a couple of things.
You'll want to keep track of how much change you still owe to the customer,
and you'll also want to keep track of how many coins
you've used so far as you go through this greedy algorithm.
We're first trying to use quarters, and then trying to use dimes,
and then trying to use nickels, and then finally using some pennies.
How might you go about actually implementing this algorithm?
Well, one approach might be to consider loops.
Ask yourself, while we can continue to use quarters,
go ahead and add a quarter to the coins that we're
using in order to make change.
And once we can't do that anymore, while we can still use dimes--
in other words, we have more than $0.10 of change still remaining to give,
go ahead and use a dime.
And you can repeat this process for nickels and pennies as well.
But there are also other approaches you can use to solve this problem as well.
For example, you might consider how much change
would be left over after you've used up as many quarters as you can,
for example.
And if you can come up with some way to encode that idea,
then that might help you to figure out how many coins you need in order
to make change for this particular customer.
So there's a number of possible ways you can go about implementing this.
So think about what makes the most sense to you and try writing some code
in order to be able to do that.
Once you've calculated the number of coins that's required,
the next step, and the last step, is just printing the result out
to the screen so the user can see it.
If we knew in advance exactly how many coins it was going to take, printing it
would be as easy as just saying, printf and then four, for example,
if we knew that it would take four coins.
Of course, it might not be four coins it's likely
going to be some different value.
And so what we can do here instead is use a placeholder
we can use the percent I placeholder to mean we're going
to plug in some integer value here.
What integer value are we going to plug in?
It might be in a variable called coins, or a variable
called something else, that you'll provide as an additional argument
to printf.
Here we're basically saying, substitute in for percent I in this string,
the value of the variable coins.
And that will print out the variable coins to the screen.
Once you do that, you should be able to compile and run your program.
Running your program by running ./cash, then typing in some amount of money
in dollars, and then seeing how many coins it would take to make that amount
of change.
My name is Brian, and this was Cash.