1
00:00:00,000 --> 00:00:00,710

2
00:00:00,710 --> 00:00:02,900
>> Mari kita serakah.

3
00:00:02,900 --> 00:00:06,810
Dalam serakah, tugas kita adalah untuk bermain
peran kasir serakah.

4
00:00:06,810 --> 00:00:09,750
Pengguna akan memberitahu kita bagaimana
banyak perubahan yang kita berutang kepada mereka,

5
00:00:09,750 --> 00:00:13,520
dan kemudian tugas kita adalah untuk menghitung
jumlah minimum koin

6
00:00:13,520 --> 00:00:17,240
yang bisa kita gunakan untuk membuat
bahwa jumlah perubahan.

7
00:00:17,240 --> 00:00:19,560
>> Mari kita mulai dengan sebuah contoh.

8
00:00:19,560 --> 00:00:23,170
Mengatakan pengguna membutuhkan $ 0,32 kembali.

9
00:00:23,170 --> 00:00:28,960
Kita bisa melakukan hal ini dengan memberikan
mereka 32 sen, satu sen setiap.

10
00:00:28,960 --> 00:00:35,180
Atau saya juga bisa menggunakan lima coins-- oleh
memberi mereka tiga dime, $ 0,10 masing-masing,

11
00:00:35,180 --> 00:00:38,060
dan dua sen, $ 0.02 setiap.

12
00:00:38,060 --> 00:00:42,580
Tapi bisa kita gunakan bahkan
koin lebih sedikit untuk membuat itu?

13
00:00:42,580 --> 00:00:45,100
>> Seluruh taktik di greedy--
menjadi cashier-- serakah

14
00:00:45,100 --> 00:00:47,600
adalah dengan menggunakan koin terbesar mungkin.

15
00:00:47,600 --> 00:00:50,670
Jadi setiap kali kita memiliki
perempat kita akan menggunakannya.

16
00:00:50,670 --> 00:00:54,100
Dan kemudian sekali mereka habis,
kita akan menggunakan dime, $ 0,10 masing-masing.

17
00:00:54,100 --> 00:00:58,840
Kemudian sen, 5 sen masing-masing, dan
kemudian ke sen, setiap satu sen.

18
00:00:58,840 --> 00:01:01,792
Dengan menggunakan koin terbesar
mungkin setiap kali kita bisa,

19
00:01:01,792 --> 00:01:07,350
kami memastikan bahwa kami menggunakan jumlah paling sedikit
koin mungkin untuk membuat perubahan.

20
00:01:07,350 --> 00:01:09,180
>> Jadi mari kita berjalan melalui.

21
00:01:09,180 --> 00:01:11,660
kebutuhan pengguna $ 0,32.

22
00:01:11,660 --> 00:01:14,200
Jadi kita bertanya kepada diri sendiri,
dapat kita gunakan seperempat?

23
00:01:14,200 --> 00:01:15,560
Nah, ya kita bisa.

24
00:01:15,560 --> 00:01:19,720
Jadi sekarang kita hanya mengenal mereka
$ 0,07, dan kami menggunakan satu koin.

25
00:01:19,720 --> 00:01:20,970
>> Dapatkah kita menggunakan seperempat?

26
00:01:20,970 --> 00:01:21,890
Yah, tidak ada.

27
00:01:21,890 --> 00:01:27,570
$ 0,07 kurang dari $ 0,25, jadi kami melanjutkan
untuk koin terbesar berikutnya yang tersedia.

28
00:01:27,570 --> 00:01:30,690
Dimes adalah $ 0,10, dan
lagi, kita tidak bisa menggunakan dime.

29
00:01:30,690 --> 00:01:35,480
Karena dime yang bernilai $ 0,10, yang
lebih dari jumlah perubahan berutang.

30
00:01:35,480 --> 00:01:36,790
>> Kami pergi ke sen.

31
00:01:36,790 --> 00:01:40,890
Dan, ya memang, $ 0,05 kurang dari
$ 0.10-- sehingga kita dapat menggunakan nikel.

32
00:01:40,890 --> 00:01:46,104
Jadi sekarang kita hanya berutang pengguna $ 0,02,
dan kami sudah sejauh menggunakan dua koin.

33
00:01:46,104 --> 00:01:47,270
Kita tidak bisa menggunakan nikel lain.

34
00:01:47,270 --> 00:01:51,140
Jadi kita lanjutkan untuk koin terakhir di
kita miliki, yang merupakan uang.

35
00:01:51,140 --> 00:01:52,270
>> Dan dapat kita gunakan sen?

36
00:01:52,270 --> 00:01:59,060
Nah, yes-- dan kami akhirnya menggunakan dua
uang untuk total empat koin.

37
00:01:59,060 --> 00:02:01,430
>> Setelah Anda selesai,
Program akan terlihat seperti ini.

38
00:02:01,430 --> 00:02:03,710
Setelah pengguna menjalankan
Program serakah, mereka akan

39
00:02:03,710 --> 00:02:07,270
diminta untuk memberikan jumlah
perubahan dalam dolar yang mereka berutang.

40
00:02:07,270 --> 00:02:11,140
Dan maka program akan menampilkan Anda
jumlah minimum koin

41
00:02:11,140 --> 00:02:14,740
bahwa kasir serakah akan menggunakan
untuk membuat jumlah perubahan.

42
00:02:14,740 --> 00:02:18,160
>> Jadi sekarang mari kita istirahat ini
ke dalam sub-tugas kami.

43
00:02:18,160 --> 00:02:21,410
Pertama kita akan meminta kami
pengguna untuk jumlah perubahan.

44
00:02:21,410 --> 00:02:25,630
Dan, karena dengan input pengguna, kita ingin
memastikan bahwa kami memvalidasi input yang

45
00:02:25,630 --> 00:02:29,360
dan memastikan bahwa kita dapat menggunakan
masukan untuk sisa program kami.

46
00:02:29,360 --> 00:02:32,480
Kemudian kita akan selalu
menggunakan titik terbesar mungkin

47
00:02:32,480 --> 00:02:35,240
dan melacak koin yang digunakan.

48
00:02:35,240 --> 00:02:39,080
Dan akhirnya, mencetak final
jumlah koin yang kita gunakan.

49
00:02:39,080 --> 00:02:40,970
>> Jadi mari kita bicara tentang mendorong.

50
00:02:40,970 --> 00:02:43,550
Jumlah tersebut harus membuat sen,
dan ini adalah dalam dolar.

51
00:02:43,550 --> 00:02:48,440
Dan jadi untuk dolar, kita akan
menggunakan jenis variabel float.

52
00:02:48,440 --> 00:02:52,390
Sekarang setiap kali Anda meminta pengguna untuk input,
Anda ingin memastikan bahwa itu valid.

53
00:02:52,390 --> 00:02:56,640
Dan jadi di sini kita ingin mengambil keuntungan
dari do-while loop membangun.

54
00:02:56,640 --> 00:03:00,320
>> Sebuah loop do-while akan mengeksekusi
tubuh loop setidaknya sekali.

55
00:03:00,320 --> 00:03:01,650
Jadi ini sangat berguna.

56
00:03:01,650 --> 00:03:05,510
Kita tahu bahwa kita perlu untuk meminta
pengguna setidaknya sekali untuk pelampung.

57
00:03:05,510 --> 00:03:07,100
Sekarang jika yang mengapung berlaku.

58
00:03:07,100 --> 00:03:07,710
Itu hebat.

59
00:03:07,710 --> 00:03:08,460
Kami melanjutkan.

60
00:03:08,460 --> 00:03:11,910
Tapi jika tidak, loop akan memastikan
bahwa kita mendapatkan pelampung yang tepat

61
00:03:11,910 --> 00:03:16,810
dengan mengulangi terus menerus sampai
pengguna memberi kita nilai yang valid.

62
00:03:16,810 --> 00:03:18,760
>> Sekarang untuk do-while
kondisi loop, kita perlu

63
00:03:18,760 --> 00:03:22,000
untuk mempertimbangkan apa artinya
untuk memiliki mengambang yang tidak valid.

64
00:03:22,000 --> 00:03:24,220
Jadi untuk konteks
masalah ini, mungkin

65
00:03:24,220 --> 00:03:27,450
masuk akal hanya untuk
menerima nilai-nilai positif.

66
00:03:27,450 --> 00:03:32,010
>> Jadi bergerak on-- kita sudah memperoleh
nilai dalam dolar dari pengguna.

67
00:03:32,010 --> 00:03:35,380
Tapi kita sedang berhadapan dengan koin,
yang seluruhnya dalam sen.

68
00:03:35,380 --> 00:03:38,660
$ 1 adalah setara dengan 100 sen.

69
00:03:38,660 --> 00:03:43,670
Jadi hal yang baik untuk dilakukan adalah untuk
mengkonversi nilai-nilai tersebut menjadi sen.

70
00:03:43,670 --> 00:03:48,380
>> Sekarang ketika mengkonversi dari pelampung
ke integer, sehingga dolar untuk sen,

71
00:03:48,380 --> 00:03:52,230
kami ingin memastikan bahwa kami berhati-hati
tentang floating-point ketidaktepatan.

72
00:03:52,230 --> 00:03:55,260
Jadi itu berarti itu-- mengatakan
dolar saya value-- mengambang saya

73
00:03:55,260 --> 00:04:00,260
value-- adalah bahkan $ 2, masih
Mungkin ada beberapa nomor liar di sana.

74
00:04:00,260 --> 00:04:04,590
Jadi kami ingin memastikan bahwa tidak hanya
kita kalikan dengan 100 untuk mendapatkan sen,

75
00:04:04,590 --> 00:04:06,480
tapi kami juga melengkapi itu.

76
00:04:06,480 --> 00:04:09,210
>> Jadi sekarang kita memiliki jumlah
perubahan berutang kepada pengguna.

77
00:04:09,210 --> 00:04:13,430
Kami awalnya diperoleh dalam dolar,
dan sekarang kita sudah dikonversi ke sen.

78
00:04:13,430 --> 00:04:17,029
Jadi sekarang kita bisa melanjutkan dengan hati
algoritma serakah, yang selalu

79
00:04:17,029 --> 00:04:19,220
menggunakan koin terbesar mungkin.

80
00:04:19,220 --> 00:04:21,930
Sementara kita melakukan ini,
itu penting bahwa kami juga

81
00:04:21,930 --> 00:04:25,360
melacak berapa banyak koin yang
akan kembali ke pengguna

82
00:04:25,360 --> 00:04:28,630
serta sisanya
mengubah berutang kepada pengguna.

83
00:04:28,630 --> 00:04:31,130
>> Program ini akan terlihat
sesuatu seperti ini.

84
00:04:31,130 --> 00:04:34,190
Setelah Anda mendapatkan jumlah
dolar dan mengkonversi bahwa untuk sen,

85
00:04:34,190 --> 00:04:35,790
maka Anda akan masuk ke lingkaran.

86
00:04:35,790 --> 00:04:38,400
Sementara perempat dapat
used-- yang mengatakan

87
00:04:38,400 --> 00:04:43,660
sedangkan jumlah perubahan berutang kepada
pengguna lebih besar dari atau sama dengan $ 0,25,

88
00:04:43,660 --> 00:04:45,040
Anda akan menggunakan seperempat.

89
00:04:45,040 --> 00:04:47,000
>> Sekarang apa yang menggunakan seperempat memerlukan?

90
00:04:47,000 --> 00:04:51,280
Nah, satu-- Anda akan meningkatkan koin
menghitung dikembalikan ke pengguna.

91
00:04:51,280 --> 00:04:55,890
Dan kedua Anda akan menurunkan arus
jumlah perubahan berutang kembali ke pengguna

92
00:04:55,890 --> 00:04:57,520
sebesar $ 0,25.

93
00:04:57,520 --> 00:05:00,680
>> Setelah mengulangi bahwa sampai
perempat tidak bisa lagi digunakan,

94
00:05:00,680 --> 00:05:04,630
melanjutkan ke terbesar berikutnya
coin-- dalam hal ini dime, $ 0.10.

95
00:05:04,630 --> 00:05:07,750
Jadi Anda akan memasukkan loop yang sampai
Anda tidak dapat lagi menggunakan dime.

96
00:05:07,750 --> 00:05:10,720
Kemudian dilanjutkan ke yang berikutnya
koin terbesar, receh.

97
00:05:10,720 --> 00:05:14,810
Setelah sen tidak bisa lagi digunakan,
menggunakan jumlah yang tersisa di uang.

98
00:05:14,810 --> 00:05:17,800
Dan akhirnya, mencetak
Jumlah koin yang digunakan.

99
00:05:17,800 --> 00:05:20,350
>> Cara lain yang dapat Anda
mendekati masalah serakah

100
00:05:20,350 --> 00:05:22,950
adalah dengan menggunakan pendekatan modulo.

101
00:05:22,950 --> 00:05:25,690
Modulo adalah operator
yang mengembalikan sisanya

102
00:05:25,690 --> 00:05:27,680
dari pembagian antara dua nomor.

103
00:05:27,680 --> 00:05:30,270
Mengatakan saya punya 50 mod 5.

104
00:05:30,270 --> 00:05:34,070
Nah, 5 adalah faktor dari 50,
sehingga sisanya akan 0.

105
00:05:34,070 --> 00:05:39,230
50 mod 10-- baik, 10 juga merupakan faktor
50, sehingga sisanya juga 0.

106
00:05:39,230 --> 00:05:43,660
50 mod 50-- baik, sejumlah mod itu sendiri
tidak akan memiliki sisa apapun.

107
00:05:43,660 --> 00:05:45,510
>> Bagaimana 50 mod 49?

108
00:05:45,510 --> 00:05:47,910
Nah, 49 hanya masuk ke 50 kali.

109
00:05:47,910 --> 00:05:50,290
Jadi sisanya akan menjadi 1.

110
00:05:50,290 --> 00:05:55,180
53 mod 50 akan
memberikan sisa 3.

111
00:05:55,180 --> 00:05:59,120
>> Jadi bagaimana kita bisa menggunakan modulo
dan mungkin beberapa divisi

112
00:05:59,120 --> 00:06:01,690
untuk mengimplementasikan algoritma serakah kita?

113
00:06:01,690 --> 00:06:05,550
Yah, kita masih ingin tetap setia pada
jantung serakah algorithm-- yang

114
00:06:05,550 --> 00:06:07,910
adalah menggunakan koin terbesar mungkin.

115
00:06:07,910 --> 00:06:14,570
>> Jadi mari kita bertanya pada diri sendiri apakah kita bisa menggunakan
perempat kembali $ 0,32 menjadi pengguna.

116
00:06:14,570 --> 00:06:20,070
Nah, 32 mod 25 memberikan
kami sisa $ 0,07.

117
00:06:20,070 --> 00:06:24,500
Jadi yang memberitahu kita bahwa kita pasti dapat
menggunakan seperempat dengan $ 0,07 tersisa.

118
00:06:24,500 --> 00:06:26,180
>> Bisakah kita kemudian menggunakan dime apapun?

119
00:06:26,180 --> 00:06:32,740
Nah, TIDAK-- karena $ 0,07 mod
$ 0,10 memberi kita sisa 7.

120
00:06:32,740 --> 00:06:34,960
10 tidak masuk ke 7 sama sekali.

121
00:06:34,960 --> 00:06:36,390
>> Kemudian bisa kita gunakan receh?

122
00:06:36,390 --> 00:06:40,490
Nah $ 0,07 mod 5 sen
memberi kita dua yang tersisa.

123
00:06:40,490 --> 00:06:42,930
Dan terakhir, dapat kita gunakan uang apapun?

124
00:06:42,930 --> 00:06:45,930
2 mod 1 memberi kita 0,
yang pada akhirnya apa yang

125
00:06:45,930 --> 00:06:48,160
kita inginkan karena itulah
berarti bahwa kita sudah kembali

126
00:06:48,160 --> 00:06:50,160
untuk pengguna semua perubahan berutang.

127
00:06:50,160 --> 00:06:54,320
>> Jadi sekarang Anda memiliki dua kemungkinan cara
melaksanakan algorithm-- serakah

128
00:06:54,320 --> 00:06:59,230
satu dengan loop dan satu dengan
Kombinasi modulo dan pembagian.

129
00:06:59,230 --> 00:07:03,010
Jadi akhirnya, kita hanya perlu
mencetak jumlah akhir koin.

130
00:07:03,010 --> 00:07:06,520
>> Jika saya ingin memberitahu Anda bahwa saya telah
3 hewan peliharaan dan nilai ini hardcoded,

131
00:07:06,520 --> 00:07:09,240
maka saya hanya bisa menggunakan
sederhana pernyataan print test.

132
00:07:09,240 --> 00:07:12,320
Tetapi nilai kita sebenarnya
disimpan dalam variabel.

133
00:07:12,320 --> 00:07:15,260
Jadi bagaimana Anda mencetak
nilai-nilai yang disimpan dalam variabel?

134
00:07:15,260 --> 00:07:17,880
>> Untuk ini kita ambil
keuntungan dari penampung.

135
00:07:17,880 --> 00:07:21,540
Mengatakan saya sudah menyatakan
integer n diinisialisasi.

136
00:07:21,540 --> 00:07:25,170
Kemudian nanti jika saya ingin mencetak bahwa
nilai, maka saya akan menulis string.

137
00:07:25,170 --> 00:07:30,500
Dan bukannya nilai yang saya akan menggunakan
tempat bagi yang integer--% i.

138
00:07:30,500 --> 00:07:33,800
Kemudian setelah string, saya memiliki
koma, diikuti oleh variabel

139
00:07:33,800 --> 00:07:34,950
yang saya ingin mencetak.

140
00:07:34,950 --> 00:07:38,550
Dan kemudian, ketika mencetak,
itu akan mencetak nilai n.

141
00:07:38,550 --> 00:07:41,570
>> Saya juga bisa menggunakan placeholder
untuk pelampung, misalnya.

142
00:07:41,570 --> 00:07:44,000
Jika saya ingin memberitahu Anda bagaimana
banyak uang yang saya miliki di saku saya,

143
00:07:44,000 --> 00:07:46,820
maka saya bisa mengatakan bahwa saya memiliki% f dolar.

144
00:07:46,820 --> 00:07:51,330
Dan nanti pada saat mencetak, maka n akan
mengambil tempat yang tempat dudukan.

145
00:07:51,330 --> 00:07:55,530
Saya juga bisa, misalnya, menggunakan beberapa
placeholder untuk beberapa variabel.

146
00:07:55,530 --> 00:07:57,590
Jadi selama saya daftar
mereka dalam rangka, maka saya

147
00:07:57,590 --> 00:08:00,390
dapat memberitahu Anda berapa banyak
anjing dan kucing yang saya miliki.

148
00:08:00,390 --> 00:08:03,710
>> Sekarang kita tahu bagaimana mendorong
pengguna untuk jumlah perubahan,

149
00:08:03,710 --> 00:08:06,130
memastikan bahwa masukan yang
valid, dan kemudian kita

150
00:08:06,130 --> 00:08:10,370
memiliki dua kemungkinan cara menerapkan
algoritma rakus selalu menggunakan

151
00:08:10,370 --> 00:08:12,090
koin terbesar mungkin.

152
00:08:12,090 --> 00:08:15,050
Karena kita sudah terus melacak
berapa banyak koin yang kita gunakan,

153
00:08:15,050 --> 00:08:19,210
kita kemudian bisa mencetak nilai bahwa pada akhirnya,
memberitahu pengguna berapa banyak koin mereka

154
00:08:19,210 --> 00:08:20,240
mendapatkan kembali.

155
00:08:20,240 --> 00:08:24,240
>> Nama saya adalah Amayla, dan ini CS50.

156
00:08:24,240 --> 00:08:25,915