>> [MUSIC PLAYING]
>> ZAMYLA CHAN: Now let's tackle Greedy.
Say you're a cashier, and you need to give your customer a
certain amount of change.
Well, if you were a greedy cashier, you'd want to keep all
the coins to yourself.
So you'd give the customer their change using as few coins as possible.
>> Your task for this p-set is to implement Greedy, a program that
calculates the minimum number of coins used to make any
given amount of change.
Before diving into the programming concepts and C syntax for Greedy,
let's first talk through the Greedy program, and see if we
can identify an algorithm.
Remember that an algorithm is just a set of
instructions for solving problems.
An algorithm for Greedy would just be a set of logical rules and steps that
we can follow.
And they will always yield the minimum number of coins needed.
>> The first thing you'd need to know is how much change
is owed to the customer.
For this example, let's say $0.32.
There are many ways to get back $0.32.
You could use, for instance, 32 pennies.
Or if, you were a bit greedier in choosing your coins, you could use
five coins instead of 32 by giving the customer three dimes--
$0.10 each-- and two pennies-- $0.01 each.
>> But can we do better than five coins?
Can we be even greedier?
Quite possibly.
>> Let's continue walking through the Greedy program, and see.
If your end goal is to use a few coins as possible, then it would be most
prudent to use the largest possible coins.
You'd rather give one quarter back-- $0.25 each--
than five nickels--
$0.05 each.
So perhaps our governing rule for Greedy can be to always use the
largest coin possible.
Out of quarters, dimes, nickels, and pennies, our
largest coin is the quarter.
So we'll try to use them first.
>> Back to our $0.32.
Can we use a quarter to give the customer $0.32?
Yes.
That would leave us with $0.07 left.
>> Can we use another quarter?
No, because 25 is greater than seven.
We don't want to give the customer any more than we owe them.
>> All right.
Now that we've exhausted our quarters, let's move on to the next largest
coin, the dime.
Can we use a dime to give the customer their $0.07 back?
No, since 10 is greater than seven.
>> So then the next largest coin accessible to us is the nickel.
Can we use a nickel?
Yes.
And then we'd have $0.02 left over.
>> We can't use a nickel to return $0.02.
So we moved the last coin at our disposal-- the penny.
And after using two pennies, we'd be left with zero cents, which means that
we've successfully paid back the user their change owed
using only four coins--
one quarter, one nickel, and two pennies.
>> You can run the staff solution to see if our governing rule and process gave
us the right answer.
For most problem sets, you'll be able to run the staff solution to see how
your own program should work.
And specific instructions will be in the problem sets specs.
>> Once we run the staff solution, it prompts us for how much change is owed
note that it asks for the amount in dollars.
We input $0.32, 0.32.
It tells us that four coins are owed, consistent with our answer.
Fantastic.
>> So now let's start looking at the implementation
of the Greedy algorithm.
We know a couple things.
One, that we'll need to prompt the user for an amount of change.
>> Two, that we'll want to follow our governing rule to always use the
largest coin possible.
And three, that we need to keep track of how many coins we use.
Because lastly, we need to print the number of coins that we.
>> First, prompting the user for an amount of change.
Whenever you deal with user input, make sure that you think of all of the
requirements of the input, and only accept input that meets those
requirements.
In this case, we want to deal with a monetary value in dollars.
>> The GetFloat and GetInt functions ensure that the input is numeric.
But the user is able to input negative numeric values.
So remember to only use non-negative inputs, which includes all negative
numbers and zero.
>> In this case, the input should be a float.
In other words, a decimal number.
Because the problem set spec requires you to ask for input in dollars.
>> But in C, floating point values can't be represented accurately.
Because there are a finite number of bits with which to
represent infinite values.
Take the number 0.1.
If I were to ask you to write 0.1 by hand to the hundredth decimal place,
you would write a 1, followed by 99 zeroes.
We'd expect that our computer would print the exact same thing
if we asked it to.
>> So let's see what it does.
I'll review printing values towards the end of this walk through.
For now, see here that f% is a placeholder for a floating point.
But we specify beforehand that we want 100 decimals displayed, and then a new
line for nicer formatting.
>> After the string, we choose 0.1 as the float that we want to print out.
And the result, a one, followed by some zeros, but then a
whole bunch of numbers.
Certainly not as expected.
>> Floating point imprecision can introduce rounding errors into your
calculations that you will definitely want to avoid.
If you want to see more examples, you can download imprecision.ce from the
walk through code, which is a simple program that asks float and prints it
back to the hundredth decimal place.
Of course, if you want to show more or less decimal places
you can change yourself.
>> As you'll see, though the difference between the two is small, when you get
to multiplying and adding floats, that discrepancy can eventually add up.
Back to Greedy.
We'll want to avoid rounding errors by dealing with whole numbers.
So after we get valid input from the user, let's convert this
dollar value to cents.
>> Mentally, we do this by multiplying the dollar value by 100.
But remember, because of floating point imprecision, we want to make
sure that we're using the right value.
Multiplying by 100 will essentially move the decimal place two spaces to
the right, chopping off or truncating anything afterwards.
>> If you play around with some more examples, you'll see that you won't
always got the right number if you use this method of truncating.
For instance, 12.59 printed to 100 decimal places, that gives you
12.5899, et cetera.
You'd get 12.58 if you truncated, not 12.59, like you need.
>> Instead, it's best to round the number first.
Luckily, C comes with the function called Round.
It's in the math library.
>> If You want to know how to use Round, then you can bring up the manual or
man page for that function.
You do this by typing man, short for manual, and then the function that you
want to look up.
So typing man round into the terminal command line will bring up the manual.
>> It might be a little hard to decipher, but eventually you'll
get the hang of it.
Man pages show you what the function does, and then some
possible uses of it.
I'll leave you to explore the man page for Round.
But know that you can use it to round the value during your conversion from
dollars to cents.
>> Round will give you back a number of data type double.
And you can convert or cast it to an int afterwards.
Great.
By now we've prompted the user for a monetary amount, and
converted it into cents.
Now we can implement an algorithm that always uses the
biggest coins available.
>> Keep in mind that there are multiple ways to implement Greedy, just like
there are multiple ways to approach every computer science problem.
Finding the most elegant way, that's the fun part.
Throughout these p-sets, if your program doesn't exactly match my
explanation in the walkthroughs, that's OK.
But just make sure that it passes check 50, satisfies all the
requirements form the specifications, and that you consider whether your
approach has good design.
>> In other words, how efficient is it?
For example, did you type repetitive code lines, instead of using a loop?
Writing code with better design will come experience as you progress
through the course.
>> For this walk through, I'll go over two methods that can be used to
complete Greedy.
The first method is a method using loops and subtraction.
Earlier, when we talked through the Greedy process, we continuously
checked whether we could use a quarter, and used a quarter until the
value remaining was less than $0.25.
>> This translates well to a while loop structure.
While we can still use a quarter, use one.
That while loop should execute as long as the remaining value is greater than
or equal to a quarter's cent value.
That means that you'll also want to keep track of the remaining cash
value, and update it every time that you use a coin.
>> Also remember that at the end, your output is the number of coins used.
So another thing to keep track of is the number of coins that you use.
You can keep track of these using well-named variables.
And within the body of your loop would be an update to those variables.
Once the loop for quarter finishes, you can use a similar one for dimes,
and so on and so forth, until you've returned all of the cash.
>> I've written some pseudo-code here to help you visualize just how the
process we discussed might translate to C. As you see here, I'm still using
English words.
It isn't C yet.
But I've started to indent things.
I've put conditions inside my parentheses.
It's starting to look a little bit like programming code.
>> Pseudo-code is a great way to get yourself started.
Visualize your code before you look up syntax.
Because often the hardest part about a problem is really understanding what
exactly you need to do.
Once you write that down, then it's a lot easier to look up the functions
and syntax specific to your line of pseudo-code
>> Keep in mind that this might not be identical to the kind of skeleton of
your code that you write.
There are always optimizations to be made.
And especially in my pseudo-code here, see if you can spot it.
>> But essentially the process and the way of thinking
is just as we discussed.
The first line tells us to obtain a certain amount in dollars.
And the second tells us to convert it to cents.
>> And then, while quarters can be used, we want to increase the coin count and
decrease the cash amount.
Same goes for dimes, nickels, and pennies.
And finally, we tell the user how many coins we used.
>> Great.
So that concludes the loop method.
Now let's talk about the modular method, which is more like division.
>> We're all familiar with the plus, minus, multiply, and divide operators
available to us.
C has all four of those, but also has the modulo operator, represented by a
percent sign.
Modulo is really neat.
It gives you the remainder from dividing two numbers.
>> Remember the long division message when you divide, say, 74 by three?
Starting with the tens place, you would know that 3 goes into seven
twice to make a six with remainder one.
You'd write two at the top, and then subtract 6 from seven, carrying over
the remainder of 14 to repeat the process.
>> Three goes into 14 four times to make 12, with remainder two.
And two doesn't carry over anymore.
So two would be left at the bottom as the remainder.
>> And that's what modulo gives, you that number at the bottom.
So 74 modulo three would give you two.
And 10 modulo two, well that would give you zero.
Because there isn't any remainder when you divide 10 by two.
>> Six modulo five, well five goes into six once.
And then it has one left over.
So six modulo five is one.
>> Then if you have seven modulo nine, you'd get seven.
Because nine is bigger than seven.
So it doesn't divide it all into seven, leaving seven as your answer.
>> If you think about modulo a little more, remember that it gives you the
remainder after you divide something.
Think about how you might be able to use it in Greedy.
Let's say the user asks for $400.11.
What's a way to figure out how many quarters you need without having to
count each one?
>> Once you figure out how many quarters you can use to make $400.11, how much
change remains?
Perhaps a combination here between modulo and division would come in
handy to give you a cool, elegant approach to the Greedy problem.
But remember that the governing rule still applies.
Always use the largest coin possible.
>> Once you've done the calculation of how many coins to use, the last step
is to print out the number of coins that you calculated.
So far, we've been using the printf function solely for strings.
But when you want to print out an In, or just any type of data that's stored
in a variable, you have to indicate that using a placeholder.
>> Here I've included just some tips on how to print out values.
If you have an integer, you would write your string using %d as a
placeholder.
After the closing quotation mark, enter a comma.
And then put in the integer that will take the place of %d when printed out.
>> So after displaying the number of coins used, you're
finished with Greedy.
Make sure to check all corner cases, tidy up your style a bit, and you're
all set to submit.
At the end of this problem set, you'll be more familiar with the CS50
appliance, the terminal, and loop structures and variables in C.
>> You're well on your way.
The learning curve can seem tough.
So take it step by step.
Make sure you write out pseudo-code before diving too deep
into unfamiliar syntax.
>> Make a to do list, and break up the assignment into smaller, more
manageable tasks.
Explore all of the CS50 resources.
In addition to lecture, rewatch this walk through.
>> Pay close attention to section.
Check out the shorts.
Read your classmates' questions on Discuss, and post your own.
>> Best of luck with the p-set.
And thanks for watching.
This was Greedy.
>> [MUSIC PLAYING]