>> Mari kita serakah.
Dalam serakah, tugas kita adalah untuk bermain peran kasir serakah.
Pengguna akan memberitahu kita bagaimana banyak perubahan yang kita berutang kepada mereka,
dan kemudian tugas kita adalah untuk menghitung jumlah minimum koin
yang bisa kita gunakan untuk membuat bahwa jumlah perubahan.
>> Mari kita mulai dengan sebuah contoh.
Mengatakan pengguna membutuhkan $ 0,32 kembali.
Kita bisa melakukan hal ini dengan memberikan mereka 32 sen, satu sen setiap.
Atau saya juga bisa menggunakan lima coins-- oleh memberi mereka tiga dime, $ 0,10 masing-masing,
dan dua sen, $ 0.02 setiap.
Tapi bisa kita gunakan bahkan koin lebih sedikit untuk membuat itu?
>> Seluruh taktik di greedy-- menjadi cashier-- serakah
adalah dengan menggunakan koin terbesar mungkin.
Jadi setiap kali kita memiliki perempat kita akan menggunakannya.
Dan kemudian sekali mereka habis, kita akan menggunakan dime, $ 0,10 masing-masing.
Kemudian sen, 5 sen masing-masing, dan kemudian ke sen, setiap satu sen.
Dengan menggunakan koin terbesar mungkin setiap kali kita bisa,
kami memastikan bahwa kami menggunakan jumlah paling sedikit koin mungkin untuk membuat perubahan.
>> Jadi mari kita berjalan melalui.
kebutuhan pengguna $ 0,32.
Jadi kita bertanya kepada diri sendiri, dapat kita gunakan seperempat?
Nah, ya kita bisa.
Jadi sekarang kita hanya mengenal mereka $ 0,07, dan kami menggunakan satu koin.
>> Dapatkah kita menggunakan seperempat?
Yah, tidak ada.
$ 0,07 kurang dari $ 0,25, jadi kami melanjutkan untuk koin terbesar berikutnya yang tersedia.
Dimes adalah $ 0,10, dan lagi, kita tidak bisa menggunakan dime.
Karena dime yang bernilai $ 0,10, yang lebih dari jumlah perubahan berutang.
>> Kami pergi ke sen.
Dan, ya memang, $ 0,05 kurang dari $ 0.10-- sehingga kita dapat menggunakan nikel.
Jadi sekarang kita hanya berutang pengguna $ 0,02, dan kami sudah sejauh menggunakan dua koin.
Kita tidak bisa menggunakan nikel lain.
Jadi kita lanjutkan untuk koin terakhir di kita miliki, yang merupakan uang.
>> Dan dapat kita gunakan sen?
Nah, yes-- dan kami akhirnya menggunakan dua uang untuk total empat koin.
>> Setelah Anda selesai, Program akan terlihat seperti ini.
Setelah pengguna menjalankan Program serakah, mereka akan
diminta untuk memberikan jumlah perubahan dalam dolar yang mereka berutang.
Dan maka program akan menampilkan Anda jumlah minimum koin
bahwa kasir serakah akan menggunakan untuk membuat jumlah perubahan.
>> Jadi sekarang mari kita istirahat ini ke dalam sub-tugas kami.
Pertama kita akan meminta kami pengguna untuk jumlah perubahan.
Dan, karena dengan input pengguna, kita ingin memastikan bahwa kami memvalidasi input yang
dan memastikan bahwa kita dapat menggunakan masukan untuk sisa program kami.
Kemudian kita akan selalu menggunakan titik terbesar mungkin
dan melacak koin yang digunakan.
Dan akhirnya, mencetak final jumlah koin yang kita gunakan.
>> Jadi mari kita bicara tentang mendorong.
Jumlah tersebut harus membuat sen, dan ini adalah dalam dolar.
Dan jadi untuk dolar, kita akan menggunakan jenis variabel float.
Sekarang setiap kali Anda meminta pengguna untuk input, Anda ingin memastikan bahwa itu valid.
Dan jadi di sini kita ingin mengambil keuntungan dari do-while loop membangun.
>> Sebuah loop do-while akan mengeksekusi tubuh loop setidaknya sekali.
Jadi ini sangat berguna.
Kita tahu bahwa kita perlu untuk meminta pengguna setidaknya sekali untuk pelampung.
Sekarang jika yang mengapung berlaku.
Itu hebat.
Kami melanjutkan.
Tapi jika tidak, loop akan memastikan bahwa kita mendapatkan pelampung yang tepat
dengan mengulangi terus menerus sampai pengguna memberi kita nilai yang valid.
>> Sekarang untuk do-while kondisi loop, kita perlu
untuk mempertimbangkan apa artinya untuk memiliki mengambang yang tidak valid.
Jadi untuk konteks masalah ini, mungkin
masuk akal hanya untuk menerima nilai-nilai positif.
>> Jadi bergerak on-- kita sudah memperoleh nilai dalam dolar dari pengguna.
Tapi kita sedang berhadapan dengan koin, yang seluruhnya dalam sen.
$ 1 adalah setara dengan 100 sen.
Jadi hal yang baik untuk dilakukan adalah untuk mengkonversi nilai-nilai tersebut menjadi sen.
>> Sekarang ketika mengkonversi dari pelampung ke integer, sehingga dolar untuk sen,
kami ingin memastikan bahwa kami berhati-hati tentang floating-point ketidaktepatan.
Jadi itu berarti itu-- mengatakan dolar saya value-- mengambang saya
value-- adalah bahkan $ 2, masih Mungkin ada beberapa nomor liar di sana.
Jadi kami ingin memastikan bahwa tidak hanya kita kalikan dengan 100 untuk mendapatkan sen,
tapi kami juga melengkapi itu.
>> Jadi sekarang kita memiliki jumlah perubahan berutang kepada pengguna.
Kami awalnya diperoleh dalam dolar, dan sekarang kita sudah dikonversi ke sen.
Jadi sekarang kita bisa melanjutkan dengan hati algoritma serakah, yang selalu
menggunakan koin terbesar mungkin.
Sementara kita melakukan ini, itu penting bahwa kami juga
melacak berapa banyak koin yang akan kembali ke pengguna
serta sisanya mengubah berutang kepada pengguna.
>> Program ini akan terlihat sesuatu seperti ini.
Setelah Anda mendapatkan jumlah dolar dan mengkonversi bahwa untuk sen,
maka Anda akan masuk ke lingkaran.
Sementara perempat dapat used-- yang mengatakan
sedangkan jumlah perubahan berutang kepada pengguna lebih besar dari atau sama dengan $ 0,25,
Anda akan menggunakan seperempat.
>> Sekarang apa yang menggunakan seperempat memerlukan?
Nah, satu-- Anda akan meningkatkan koin menghitung dikembalikan ke pengguna.
Dan kedua Anda akan menurunkan arus jumlah perubahan berutang kembali ke pengguna
sebesar $ 0,25.
>> Setelah mengulangi bahwa sampai perempat tidak bisa lagi digunakan,
melanjutkan ke terbesar berikutnya coin-- dalam hal ini dime, $ 0.10.
Jadi Anda akan memasukkan loop yang sampai Anda tidak dapat lagi menggunakan dime.
Kemudian dilanjutkan ke yang berikutnya koin terbesar, receh.
Setelah sen tidak bisa lagi digunakan, menggunakan jumlah yang tersisa di uang.
Dan akhirnya, mencetak Jumlah koin yang digunakan.
>> Cara lain yang dapat Anda mendekati masalah serakah
adalah dengan menggunakan pendekatan modulo.
Modulo adalah operator yang mengembalikan sisanya
dari pembagian antara dua nomor.
Mengatakan saya punya 50 mod 5.
Nah, 5 adalah faktor dari 50, sehingga sisanya akan 0.
50 mod 10-- baik, 10 juga merupakan faktor 50, sehingga sisanya juga 0.
50 mod 50-- baik, sejumlah mod itu sendiri tidak akan memiliki sisa apapun.
>> Bagaimana 50 mod 49?
Nah, 49 hanya masuk ke 50 kali.
Jadi sisanya akan menjadi 1.
53 mod 50 akan memberikan sisa 3.
>> Jadi bagaimana kita bisa menggunakan modulo dan mungkin beberapa divisi
untuk mengimplementasikan algoritma serakah kita?
Yah, kita masih ingin tetap setia pada jantung serakah algorithm-- yang
adalah menggunakan koin terbesar mungkin.
>> Jadi mari kita bertanya pada diri sendiri apakah kita bisa menggunakan perempat kembali $ 0,32 menjadi pengguna.
Nah, 32 mod 25 memberikan kami sisa $ 0,07.
Jadi yang memberitahu kita bahwa kita pasti dapat menggunakan seperempat dengan $ 0,07 tersisa.
>> Bisakah kita kemudian menggunakan dime apapun?
Nah, TIDAK-- karena $ 0,07 mod $ 0,10 memberi kita sisa 7.
10 tidak masuk ke 7 sama sekali.
>> Kemudian bisa kita gunakan receh?
Nah $ 0,07 mod 5 sen memberi kita dua yang tersisa.
Dan terakhir, dapat kita gunakan uang apapun?
2 mod 1 memberi kita 0, yang pada akhirnya apa yang
kita inginkan karena itulah berarti bahwa kita sudah kembali
untuk pengguna semua perubahan berutang.
>> Jadi sekarang Anda memiliki dua kemungkinan cara melaksanakan algorithm-- serakah
satu dengan loop dan satu dengan Kombinasi modulo dan pembagian.
Jadi akhirnya, kita hanya perlu mencetak jumlah akhir koin.
>> Jika saya ingin memberitahu Anda bahwa saya telah 3 hewan peliharaan dan nilai ini hardcoded,
maka saya hanya bisa menggunakan sederhana pernyataan print test.
Tetapi nilai kita sebenarnya disimpan dalam variabel.
Jadi bagaimana Anda mencetak nilai-nilai yang disimpan dalam variabel?
>> Untuk ini kita ambil keuntungan dari penampung.
Mengatakan saya sudah menyatakan integer n diinisialisasi.
Kemudian nanti jika saya ingin mencetak bahwa nilai, maka saya akan menulis string.
Dan bukannya nilai yang saya akan menggunakan tempat bagi yang integer--% i.
Kemudian setelah string, saya memiliki koma, diikuti oleh variabel
yang saya ingin mencetak.
Dan kemudian, ketika mencetak, itu akan mencetak nilai n.
>> Saya juga bisa menggunakan placeholder untuk pelampung, misalnya.
Jika saya ingin memberitahu Anda bagaimana banyak uang yang saya miliki di saku saya,
maka saya bisa mengatakan bahwa saya memiliki% f dolar.
Dan nanti pada saat mencetak, maka n akan mengambil tempat yang tempat dudukan.
Saya juga bisa, misalnya, menggunakan beberapa placeholder untuk beberapa variabel.
Jadi selama saya daftar mereka dalam rangka, maka saya
dapat memberitahu Anda berapa banyak anjing dan kucing yang saya miliki.
>> Sekarang kita tahu bagaimana mendorong pengguna untuk jumlah perubahan,
memastikan bahwa masukan yang valid, dan kemudian kita
memiliki dua kemungkinan cara menerapkan algoritma rakus selalu menggunakan
koin terbesar mungkin.
Karena kita sudah terus melacak berapa banyak koin yang kita gunakan,
kita kemudian bisa mencetak nilai bahwa pada akhirnya, memberitahu pengguna berapa banyak koin mereka
mendapatkan kembali.
>> Nama saya adalah Amayla, dan ini CS50.