1
00:00:00,000 --> 00:00:01,530


2
00:00:01,530 --> 00:00:04,380
ZAMYLA CHAN: Let's get greedy again.

3
00:00:04,380 --> 00:00:07,770
Today, we're going to recreate the
greedy problem that we did in C,

4
00:00:07,770 --> 00:00:10,110
but this time in Python.

5
00:00:10,110 --> 00:00:11,760
Now, the to-do's haven't changed.

6
00:00:11,760 --> 00:00:14,520
We want to prompt the user
for an amount of change,

7
00:00:14,520 --> 00:00:17,280
always using the largest
coin possible, keeping

8
00:00:17,280 --> 00:00:21,180
track of how many coins were used, and
then printing that final number out.

9
00:00:21,180 --> 00:00:24,570
So how do we prompt the user for the
amount of change that they're owed?

10
00:00:24,570 --> 00:00:29,100
Well, in C, we had to get float
function found in the CS50 library.

11
00:00:29,100 --> 00:00:34,200
So in order to use that function, we
had to hashtag include the CS50 library.

12
00:00:34,200 --> 00:00:38,910
Now, in Python, CS50 also provides
you with the get float function found

13
00:00:38,910 --> 00:00:40,140
in the CS50 module.

14
00:00:40,140 --> 00:00:45,190
So instead of hashtag including
it, you'll have to import it.

15
00:00:45,190 --> 00:00:45,690
OK.

16
00:00:45,690 --> 00:00:48,180
So now, how do we validate the input?

17
00:00:48,180 --> 00:00:52,080
Well, typically, we might use
a do while loop in C. Now,

18
00:00:52,080 --> 00:00:55,890
Python doesn't have an
equivalent for the do while loop.

19
00:00:55,890 --> 00:00:59,020
It does, however, have
an equivalent while loop.

20
00:00:59,020 --> 00:01:04,920
So how do we use the while loop
and make it into a do while loop?

21
00:01:04,920 --> 00:01:06,390
Here's how.

22
00:01:06,390 --> 00:01:10,000
See how my condition for
the while loop is true.

23
00:01:10,000 --> 00:01:13,110
So that means that that
will execute at least once.

24
00:01:13,110 --> 00:01:16,590
So that's where I'm going to prompt
the user for the amount of change.

25
00:01:16,590 --> 00:01:20,644
And then if they've met my
condition and if it's valid,

26
00:01:20,644 --> 00:01:22,560
then I'll just break out
of that loop and then

27
00:01:22,560 --> 00:01:24,630
I'll continue with the
rest of my program.

28
00:01:24,630 --> 00:01:28,590
But if they gave me invalid input then,
I'll just go back to the top of my loop

29
00:01:28,590 --> 00:01:31,240
and prompt them again.

30
00:01:31,240 --> 00:01:34,650
So the next thing once we have
their input, which is in dollars,

31
00:01:34,650 --> 00:01:40,830
is to convert that into cents,
where $1 is equivalent to 100 cents.

32
00:01:40,830 --> 00:01:43,410
Before, we had the round
function available in C,

33
00:01:43,410 --> 00:01:45,960
which we also have in Python.

34
00:01:45,960 --> 00:01:47,940
Now that we have the
value in cents, let's

35
00:01:47,940 --> 00:01:52,770
proceed with our greedy algorithm,
always using the largest coin possible,

36
00:01:52,770 --> 00:01:56,160
keeping track of how many
coins must be returned,

37
00:01:56,160 --> 00:01:59,040
and the total amount that remains.

38
00:01:59,040 --> 00:02:01,740
Now, some of you may have
implemented this problem

39
00:02:01,740 --> 00:02:04,050
using a combination of while loops.

40
00:02:04,050 --> 00:02:05,880
And that's perfectly acceptable.

41
00:02:05,880 --> 00:02:08,220
But there's also an
alternative way to use

42
00:02:08,220 --> 00:02:11,020
a combination of modulo and division.

43
00:02:11,020 --> 00:02:13,500
So if you did it the
while loops way, then I

44
00:02:13,500 --> 00:02:17,080
challenge you to try
this out with modulo.

45
00:02:17,080 --> 00:02:19,680
Modulo, as you remember,
returns the remainder

46
00:02:19,680 --> 00:02:22,140
of a division between two numbers.

47
00:02:22,140 --> 00:02:25,710
Then in Python, if you
want to divide integers,

48
00:02:25,710 --> 00:02:30,180
then you can use the double
slash and then for float division

49
00:02:30,180 --> 00:02:32,730
use the single slash.

50
00:02:32,730 --> 00:02:35,970
So finally, you need to print
the final number of coins.

51
00:02:35,970 --> 00:02:38,640
In C, we would have to
call printf, passing

52
00:02:38,640 --> 00:02:43,470
in a placeholder for that variable
indicating what type it was and then

53
00:02:43,470 --> 00:02:45,370
include the variable afterwards.

54
00:02:45,370 --> 00:02:49,230
But in Python if I have a variable
called coins, then all I have to do

55
00:02:49,230 --> 00:02:52,530
is call the printf
statement and pass in coins.

56
00:02:52,530 --> 00:02:55,080
So there you have your greedy program.

57
00:02:55,080 --> 00:02:59,300
My name is Zamyla and this was greedy.

58
00:02:59,300 --> 00:03:01,370