1
00:00:00,000 --> 00:00:00,994

2
00:00:00,994 --> 00:00:11,431
>> [MUSIC PLAYING]

3
00:00:11,431 --> 00:00:12,500
>> ROB BOWDEN: Hi.

4
00:00:12,500 --> 00:00:13,230
I'm Rob.

5
00:00:13,230 --> 00:00:15,080
And let's get Greedy.

6
00:00:15,080 --> 00:00:18,560
>> So the first thing we need to do
is ask the user exactly how

7
00:00:18,560 --> 00:00:20,500
much change is owed.

8
00:00:20,500 --> 00:00:23,310
So here, we see we have
a do/while loop.

9
00:00:23,310 --> 00:00:26,650
And we're setting dollars
equal to GetFloat.

10
00:00:26,650 --> 00:00:27,890
What is GetFloat?

11
00:00:27,890 --> 00:00:30,700
It's one of the functions in the
CS50 library that gets a

12
00:00:30,700 --> 00:00:32,450
float from the user.

13
00:00:32,450 --> 00:00:35,200
Remember, in order to use that function,
we need to hash include

14
00:00:35,200 --> 00:00:37,790
CS50.h at the top.

15
00:00:37,790 --> 00:00:42,310
>> So once we have that value from the
user, we also need to be sure that

16
00:00:42,310 --> 00:00:43,560
it's a valid value.

17
00:00:43,560 --> 00:00:46,050
We can't owe negative money.

18
00:00:46,050 --> 00:00:48,460
And so that's the purpose
of this do/while loop.

19
00:00:48,460 --> 00:00:52,420
We continue looping while dollars
is less than zero.

20
00:00:52,420 --> 00:00:56,960
And a do/while loop is the right thing
to use here, since we need to ask the

21
00:00:56,960 --> 00:01:00,290
user at least once for how
much money is owed.

22
00:01:00,290 --> 00:01:05,040
>> So once we have that number of dollars,
we see here we have int cents

23
00:01:05,040 --> 00:01:08,630
equals round dollars times
CENTS_PER_DOLLAR.

24
00:01:08,630 --> 00:01:10,740
At the top, we see that
CENTS_PER_DOLLAR is

25
00:01:10,740 --> 00:01:13,750
sensibly defined as 100.

26
00:01:13,750 --> 00:01:16,270
So what is this line doing?

27
00:01:16,270 --> 00:01:21,200
>> Well, if you remember, floating point
values aren't quite precise.

28
00:01:21,200 --> 00:01:25,470
Unlike integers, we can't represent
floating point values exactly.

29
00:01:25,470 --> 00:01:28,660
There's always some sort
of imprecision.

30
00:01:28,660 --> 00:01:32,840
So we prefer to work with just integers
throughout this problem.

31
00:01:32,840 --> 00:01:42,690
And here, if the user entered $3.42,
we're converting that to 342 cents and

32
00:01:42,690 --> 00:01:45,900
rounding, just get rid of
any of that imprecision.

33
00:01:45,900 --> 00:01:49,940
>> So once we have the number of cents in
an integer, we can continue with the

34
00:01:49,940 --> 00:01:51,730
rest of the program.

35
00:01:51,730 --> 00:01:55,910
We see here that we're declaring integer
coins which we're only to use

36
00:01:55,910 --> 00:01:59,560
to keep track of the total
number of coins.

37
00:01:59,560 --> 00:02:01,590
Here, we have our first while loop.

38
00:02:01,590 --> 00:02:06,780
>> We see while cents is greater than or
equal to quarter, which above, is hash

39
00:02:06,780 --> 00:02:14,680
defined as 25, while that is true, we
want to increment our number of coins

40
00:02:14,680 --> 00:02:18,350
and decrement cents by quarter.

41
00:02:18,350 --> 00:02:22,810
Remember that this syntax
is equivalent to cents

42
00:02:22,810 --> 00:02:26,020
equals cents minus quarter.

43
00:02:26,020 --> 00:02:28,170
Those are the same.

44
00:02:28,170 --> 00:02:31,850
>> So what is this while loop doing?

45
00:02:31,850 --> 00:02:39,260
The idea here is that, if I know $3.42
is owed, I can continue giving

46
00:02:39,260 --> 00:02:42,670
quarters until I can't give
quarters any more.

47
00:02:42,670 --> 00:02:47,720
I can't give quarters any more,
once I've given $3.25.

48
00:02:47,720 --> 00:02:53,300
>> So then, once that's the case, we'll
break out of this while loop.

49
00:02:53,300 --> 00:02:57,650
Cents will be left at 17 cents.

50
00:02:57,650 --> 00:03:01,910
And we'll continue down to the next
while loop where we say, while cents

51
00:03:01,910 --> 00:03:04,270
is greater than or equal to dime.

52
00:03:04,270 --> 00:03:07,420
>> And now we're doing the same exact
thing we did in the quarter case,

53
00:03:07,420 --> 00:03:09,010
except with dimes.

54
00:03:09,010 --> 00:03:15,050
So with $0.17, we'll loop until we can
no longer give a dime, which is

55
00:03:15,050 --> 00:03:16,680
exactly once.

56
00:03:16,680 --> 00:03:20,470
And then we'll be left with 7 cents.

57
00:03:20,470 --> 00:03:24,730
>> Then we'll continue on to nickels, which
will loop until we can't give

58
00:03:24,730 --> 00:03:29,420
any more nickels, which will
leave us with two cents.

59
00:03:29,420 --> 00:03:34,400
And then, down at the bottom, we have
pennies, which will loop and will

60
00:03:34,400 --> 00:03:37,140
finally leave us with zero cents.

61
00:03:37,140 --> 00:03:41,670
Then at the end, we just need to
print out our number of coins.

62
00:03:41,670 --> 00:03:44,980
>> So this program is perfectly correct.

63
00:03:44,980 --> 00:03:47,310
But we can actually do a bit better.

64
00:03:47,310 --> 00:03:52,660
Now if I say that I owe you $10,000,
you shouldn't need to go here's one

65
00:03:52,660 --> 00:03:55,310
quarter, two quarters, three quarters.

66
00:03:55,310 --> 00:03:59,450
You should know immediately that
I owe you 40,000 quarters.

67
00:03:59,450 --> 00:04:04,070
>> Now let's look at a program that
handles it a bit better.

68
00:04:04,070 --> 00:04:07,190
In this version of things, we still need
to ask the user for the amount of

69
00:04:07,190 --> 00:04:10,930
change that they want in exactly
the same way we did before.

70
00:04:10,930 --> 00:04:14,110
We need to round it exactly
the way we did before.

71
00:04:14,110 --> 00:04:17,910
And we still have our coins integer
declared exactly the same as before.

72
00:04:17,910 --> 00:04:21,399
>> So here's where things
get a bit different.

73
00:04:21,399 --> 00:04:24,640
We're doing coins plus equals
cents divided by quarter

74
00:04:24,640 --> 00:04:27,140
where quarter is 25.

75
00:04:27,140 --> 00:04:31,790
What this is saying is, take as many
quarters as can go into cents and add

76
00:04:31,790 --> 00:04:33,030
that to coins.

77
00:04:33,030 --> 00:04:40,100
>> So if cents is 142, 142 divided
by 25 gives us 5.

78
00:04:40,100 --> 00:04:43,950
Remember that integer division
automatically truncates.

79
00:04:43,950 --> 00:04:46,870
So we're doing coins plus equals 5.

80
00:04:46,870 --> 00:04:51,850
>> Immediately after this, we're saying
cents equal cents mod quarter.

81
00:04:51,850 --> 00:04:57,150
Remember that the mod operator gives
us the remainder after division.

82
00:04:57,150 --> 00:05:05,840
So 142 mod quarter, that will give
is 142 minus 125, which is 17.

83
00:05:05,840 --> 00:05:10,470
That's the remainder after
doing 142 divided by 25.

84
00:05:10,470 --> 00:05:13,040
>> So now cents is equal to 17.

85
00:05:13,040 --> 00:05:16,080
And we do the same exact
thing for dimes.

86
00:05:16,080 --> 00:05:18,620
17 divided by 10 will give us 1.

87
00:05:18,620 --> 00:05:20,150
And we add that to coins.

88
00:05:20,150 --> 00:05:25,380
And then we update cents to
be 17 mod 10, which is 7.

89
00:05:25,380 --> 00:05:27,200
>> And then the same for nickels.

90
00:05:27,200 --> 00:05:29,180
7 divided by 5 is 1.

91
00:05:29,180 --> 00:05:30,880
Add that to coins.

92
00:05:30,880 --> 00:05:34,600
And then 7 mod 5 is 2.

93
00:05:34,600 --> 00:05:35,910
And that's our cents.

94
00:05:35,910 --> 00:05:39,065
>> And then, for pennies, there's no real
point in dividing or modding, since,

95
00:05:39,065 --> 00:05:42,170
if we have $0.2 left over, we can
just immediately add that to

96
00:05:42,170 --> 00:05:43,590
our number of coins.

97
00:05:43,590 --> 00:05:48,210
And finally, we need to print out our
number of coins and, optionally,

98
00:05:48,210 --> 00:05:52,100
return 0 at the end of our program
to signify everything worked.

99
00:05:52,100 --> 00:05:53,120
>> My name is Rob.

100
00:05:53,120 --> 00:05:54,020
And this was Greedy.

101
00:05:54,020 --> 00:05:57,620
>> [MUSIC PLAYING]

102
00:05:57,620 --> 00:06:01,515