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