[MUSIC PLAYING] 

ZAMYLA CHAN: Sekarang mari kita menangani Greedy. Katakanlah Anda seorang kasir, dan Anda perlu memberikan pelanggan Anda sejumlah perubahan. Nah, jika Anda adalah seorang kasir serakah, Anda ingin menyimpan semua koin untuk diri sendiri. Jadi, Anda akan memberikan pelanggan perubahan mereka menggunakan sebagai beberapa koin mungkin. 

Tugas Anda untuk ini p-set adalah untuk mengimplementasikan Greedy, sebuah program yang menghitung jumlah minimum koin yang digunakan untuk membuat mengingat jumlah perubahan. Sebelum menyelam ke dalam pemrograman konsep dan sintaks C Greedy, mari kita bicara pertama melalui Greedy Program, dan melihat apakah kita dapat mengidentifikasi algoritma. Ingat bahwa algoritma hanya satu set instruksi untuk memecahkan masalah. Sebuah algoritma untuk Greedy hanya akan menjadi seperangkat aturan logis dan langkah-langkah yang kita dapat mengikuti. Dan mereka akan selalu menghasilkan minimum jumlah koin yang dibutuhkan. 

Hal pertama yang Anda akan perlu untuk tahu adalah berapa banyak perubahan berutang kepada pelanggan. Untuk contoh ini, katakanlah $ 0,32. Ada banyak cara untuk mendapatkan kembali $ 0,32. Anda bisa menggunakan, misalnya, 32 sen. Atau jika Anda sedikit rakus di memilih koin Anda, Anda bisa menggunakan lima koin bukan 32 dengan memberikan pelanggan tiga dime - $ 0,10 masing-masing - dan dua sen - $ 0,01 masing-masing. 

Tapi kita bisa berbuat lebih baik dari lima koin? Bisakah kita menjadi lebih rakus? Sangat mungkin. 

Mari kita terus berjalan melalui program Greedy, dan melihat. Jika tujuan akhir Anda adalah dengan menggunakan beberapa koin mungkin, maka akan sangat bijaksana untuk menggunakan terbesar mungkin koin. Anda lebih suka memberikan seperempat kembali - $ 0,25 masing-masing - dari lima sen - $ 0,05 masing-masing. Jadi mungkin aturan yang mengatur kami untuk Greedy dapat untuk selalu menggunakan koin mungkin terbesar. Keluar dari tempat, dime, sen, dan uang, kami koin terbesar adalah kuartal. Jadi kita akan mencoba untuk menggunakan mereka terlebih dahulu. 

Kembali ke kami $ 0,32. Dapatkah kita menggunakan seperempat untuk memberikan pelanggan $ 0,32? Ya. Itu akan meninggalkan kita dengan $ 0,07 kiri. 

Dapatkah kita menggunakan seperempat lain? Tidak, karena 25 lebih besar dari tujuh. Kami tidak ingin memberikan pelanggan lebih dari yang kita berutang kepada mereka. 

Baik. Sekarang kita telah kehabisan tempat kami, mari kita beralih ke terbesar berikutnya koin, sepeser pun. Dapatkah kita menggunakan sepeser pun untuk memberikan pelanggan mereka $ 0,07 kembali? Tidak, karena 10 lebih besar dari tujuh. 

Jadi koin terbesar berikutnya diakses kami adalah nikel. Dapatkah kita menggunakan nikel? Ya. Dan kemudian kita akan memiliki $ 0,02 tersisa. 

Kita tidak bisa menggunakan nikel untuk kembali $ 0,02. Jadi kami pindah koin terakhir di kita miliki - sen. Dan setelah menggunakan dua sen, kita akan kiri dengan nol sen, yang berarti bahwa kita telah berhasil membayar kembali pengguna perubahan mereka berutang hanya menggunakan empat koin - seperempat, satu nikel, dan dua sen. 

Anda dapat menjalankan solusi staf untuk melihat apakah aturan yang mengatur kami dan proses memberikan kami jawaban yang tepat. Untuk sebagian besar masalah set, Anda akan dapat untuk menjalankan solusi staf untuk melihat bagaimana program Anda sendiri harus bekerja. Dan instruksi khusus akan berada dalam masalah set spesifikasi. 

Setelah kita menjalankan solusi staf, itu mendorong kita untuk berapa banyak perubahan yang berutang dicatat bahwa ia meminta untuk berjumlah dalam dolar. Kami masukan $ 0,32, 0,32. Ini memberitahu kita bahwa empat koin yang berutang, konsisten dengan jawaban kami. Fantastic. 

Jadi sekarang mari kita mulai mencari pada pelaksanaan dari algoritma Greedy. Kita tahu beberapa hal. Satu, bahwa kita harus meminta pengguna untuk jumlah perubahan. 

Dua, bahwa kita akan ingin mengikuti kami mengatur aturan untuk selalu menggunakan koin mungkin terbesar. Dan tiga, bahwa kita perlu untuk melacak berapa banyak koin yang kita gunakan. Karena terakhir, kita perlu untuk mencetak jumlah koin yang kita. 

Pertama, mendorong pengguna untuk jumlah perubahan. Setiap kali Anda berurusan dengan input pengguna, membuat Pastikan bahwa Anda memikirkan semua persyaratan input, dan hanya menerima masukan yang memenuhi mereka persyaratan. Dalam kasus ini, kita ingin berurusan dengan nilai moneter dalam dolar. 

The getFloat dan getInt fungsi memastikan bahwa input numerik. Namun pengguna dapat masukan nilai numerik negatif. Jadi ingat untuk hanya menggunakan non-negatif input, yang mencakup semua negatif angka dan nol. 

Dalam hal ini, input harus pelampung. Dengan kata lain, angka desimal. Karena masalah set spesifikasi membutuhkan Anda untuk meminta masukan dalam dolar. 

Tapi dalam C, nilai-nilai floating point tidak bisa diwakili secara akurat. Karena ada jumlah terbatas bit yang dapat digunakan untuk mewakili nilai-nilai yang tak terbatas. Mengambil nomor 0,1. Jika saya meminta Anda untuk menulis 0,1 oleh tangan ke tempat desimal keseratus, Anda akan menulis 1, diikuti oleh 99 angka nol. Kami harapkan bahwa komputer kita akan mencetak hal yang sama persis jika kita bertanya kepada. 

Jadi mari kita lihat apa yang dilakukannya. Saya akan meninjau nilai pencetakan terhadap akhir ini berjalan melalui. Untuk saat ini, lihat di sini bahwa f% adalah placeholder untuk floating point. Tapi kita tentukan sebelumnya bahwa kita ingin 100 desimal yang ditampilkan, dan kemudian baru line untuk format yang lebih baik. 

Setelah string, kita memilih 0.1 sebagai mengapung yang kita ingin mencetak. Dan hasilnya, satu, diikuti oleh beberapa angka nol, tapi kemudian Seluruh sekelompok angka. Tentu saja tidak seperti yang diharapkan. 

Floating point ketidaktepatan dapat memperkenalkan pembulatan kesalahan ke dalam perhitungan bahwa Anda akan pasti ingin menghindari. Jika Anda ingin melihat lebih banyak contoh, Anda dapat men-download imprecision.ce dari berjalan melalui kode, yang merupakan sederhana Program yang meminta mengapung dan mencetaknya kembali ke tempat desimal keseratus. Tentu saja, jika Anda ingin menunjukkan lebih atau kurang desimal Anda bisa mengubah diri Anda sendiri. 

Seperti yang Anda lihat, meskipun perbedaan antara keduanya adalah kecil, ketika Anda mendapatkan untuk mengalikan dan menambahkan mengapung, yang perbedaan akhirnya dapat menambahkan sampai. Kembali ke Greedy. Kami akan ingin menghindari kesalahan pembulatan oleh berurusan dengan bilangan bulat. Jadi setelah kami mendapatkan masukan yang valid dari pengguna, mari kita mengubahnya nilai dolar untuk sen. 

Secara mental, kita melakukan ini dengan mengalikan nilai dolar dengan 100. Tapi ingat, karena floating point ketidaktepatan, kami ingin membuat memastikan bahwa kita menggunakan nilai yang benar. Mengalikan dengan 100 pada dasarnya akan bergerak tempat desimal dua spasi untuk kanan, memenggal atau memotong apa-apa setelah itu. 

Jika Anda bermain-main dengan beberapa lebih contoh, Anda akan melihat bahwa Anda tidak akan selalu mendapat nomor yang benar jika Anda menggunakan metode ini truncating. Misalnya, 12,59 dicetak 100 tempat desimal, yang memberikan Anda 12,5899, dan sebagainya. Anda akan mendapatkan 12,58 jika Anda dipotong, tidak 12.59, seperti yang Anda butuhkan. 

Sebaliknya, yang terbaik untuk putaran nomor pertama. Untungnya, C dilengkapi dengan fungsi yang disebut Putaran. Ini di perpustakaan matematika. 

Jika Anda ingin tahu bagaimana menggunakan Putaran, maka Anda dapat membuka manual atau halaman manual untuk fungsi tersebut. Anda melakukan ini dengan mengetikkan man, singkatan manual, dan kemudian fungsi yang ingin mencari. Jadi mengetik man putaran ke terminal baris perintah akan memunculkan manual. 

Ini mungkin sedikit sulit untuk menguraikan, tapi akhirnya Anda akan mendapatkan menguasainya. Halaman manual menunjukkan apa fungsi tidak, dan kemudian beberapa kemungkinan pemanfaatan itu. Aku akan meninggalkan Anda untuk menjelajahi halaman manual untuk Bundar. Tapi tahu bahwa Anda dapat menggunakannya untuk putaran nilai selama konversi dari dolar untuk sen. 

Putaran akan memberikan kembali nomor tipe data ganda. Dan Anda dapat mengubah atau cor ke sebuah int sesudahnya. Besar. Sekarang kita sudah diminta pengguna untuk jumlah moneter, dan dikonversi menjadi sen. Sekarang kita dapat menerapkan algoritma yang selalu menggunakan koin terbesar yang tersedia. 

Perlu diketahui bahwa ada beberapa cara untuk menerapkan Greedy, seperti ada beberapa cara untuk mendekati setiap masalah ilmu komputer. Menemukan cara yang paling elegan, itulah bagian yang menyenangkan. Sepanjang ini p-set, jika program Anda tidak persis saya penjelasan dalam penelusuran, itu OK. Tapi pastikan bahwa itu melewati memeriksa 50, memenuhi semua persyaratan membentuk spesifikasi, dan bahwa Anda mempertimbangkan apakah Anda pendekatan memiliki desain yang baik. 

Dengan kata lain, seberapa efisien itu? Sebagai contoh, apakah Anda mengetik berulang-ulang baris kode, alih-alih menggunakan loop? Menulis kode dengan desain yang lebih baik akan datang pengalaman karena Anda maju melalui kursus. 

Untuk ini berjalan melalui, saya akan pergi ke dua metode yang dapat digunakan untuk menyelesaikan Greedy. Metode pertama adalah metode yang menggunakan loop dan pengurangan. Sebelumnya, ketika kita berbicara melalui Proses Greedy, kami terus memeriksa apakah kita bisa menggunakan seperempat, dan menggunakan seperempat sampai nilai sisa kurang dari $ 0,25. 

Hal ini diterjemahkan dengan baik ke sementara struktur loop. Sementara kita masih dapat menggunakan seperempat, gunakan salah satu. Itu loop sementara harus mengeksekusi selama sebagai nilai yang tersisa lebih besar dari atau sama dengan nilai persen seperempat itu. Itu berarti bahwa Anda juga akan ingin melacak sisa kas nilai, dan memperbaruinya setiap kali Anda menggunakan koin. 

Juga ingat bahwa pada akhirnya, Anda output jumlah koin yang digunakan. Jadi hal lain untuk melacak adalah jumlah koin yang Anda gunakan. Anda dapat melacak ini menggunakan variabel yang bernama. Dan dalam tubuh loop Anda akan menjadi update untuk variabel tersebut. Setelah loop untuk kuartal selesai, Anda dapat menggunakan yang serupa untuk dime, dan seterusnya dan sebagainya, sampai Anda sudah kembali semua uang tunai. 

Saya telah menulis beberapa pseudo-code di sini untuk membantu Anda memvisualisasikan hanya bagaimana Proses kita bahas mungkin menerjemahkan untuk C. Seperti yang Anda lihat di sini, saya masih menggunakan Kata dalam bahasa Inggris. Ini bukan C belum. Tapi aku sudah mulai hal-hal yang indent. Aku telah menempatkan kondisi di dalam kurung saya. Ini mulai terlihat sedikit sedikit seperti kode pemrograman. 

Pseudo-code adalah cara yang bagus untuk mendapatkan diri Anda mulai. Visualisasikan kode Anda sebelum Anda mencari sintaks. Karena sering bagian tersulit tentang Masalah benar-benar memahami apa yang persis yang perlu Anda lakukan. Setelah Anda menulis yang turun, maka itu adalah jauh lebih mudah untuk mencari fungsi dan sintaks khusus untuk Anda baris pseudo-code 

Perlu diingat bahwa ini mungkin tidak identik dengan jenis kerangka kode yang Anda tulis. Selalu ada optimasi yang akan dibuat. Dan terutama dalam pseudo-kode saya di sini, lihat apakah Anda dapat menemukannya. 

Tapi pada dasarnya proses dan cara berpikir sama kita bahas. Baris pertama memberitahu kita untuk mendapatkan jumlah tertentu dalam dolar. Dan yang kedua memberitahu kita untuk mengubahnya menjadi sen. 

Dan kemudian, sementara perempat dapat digunakan, kita ingin meningkatkan jumlah koin dan mengurangi jumlah uang tunai. Sama berlaku untuk dime, sen, dan uang. Dan akhirnya, kami memberitahu pengguna berapa banyak koin yang kita gunakan. 

Besar. Sehingga menyimpulkan metode loop. Sekarang mari kita bicara tentang metode modular, yang lebih seperti divisi. 

Kita semua akrab dengan ditambah, dikurangi, mengalikan, dan membagi operator tersedia bagi kita. C memiliki semua empat dari mereka, tetapi juga memiliki operator modulo, diwakili oleh tanda persen. Modulo benar-benar rapi. Ini memberi Anda sisanya dari membagi dua nomor. 

Ingat pesan pembagian panjang ketika Anda membagi, katakanlah, 74 oleh tiga? Dimulai dengan tempat puluhan, Anda akan tahu bahwa 3 masuk ke tujuh dua kali untuk membuat enam dengan sisa satu. Anda akan menulis dua di bagian atas, dan kemudian kurangi 6 dari tujuh, membawa lebih dari sisa 14 sampai ulangi proses. 

Tiga masuk ke 14 empat kali untuk membuat 12, dengan sisa dua. Dan dua tidak terbawa lagi. Jadi dua akan dibiarkan di bawah sebagai sisanya. 

Dan itulah yang memberi Modulo, Anda nomor di bagian bawah. Jadi 74 modulo tiga akan memberikan dua. Dan 10 modulo dua, baik itu akan memberikan Anda nol. Karena tidak ada sisa apapun ketika Anda membagi 10 dengan dua. 

Enam modulo lima, baik lima masuk ke enam kali. Dan saat itu telah salah satu yang tersisa. Jadi enam modulo lima adalah satu. 

Kemudian jika Anda memiliki tujuh modulo sembilan, Anda akan mendapatkan tujuh. Karena sembilan lebih besar dari tujuh. Jadi tidak membagi semuanya menjadi tujuh, meninggalkan tujuh sebagai jawaban Anda. 

Jika Anda berpikir tentang modulo sedikit lebih, ingat bahwa itu memberi Anda sisanya setelah Anda membagi sesuatu. Pikirkan tentang bagaimana Anda mungkin mampu menggunakannya dalam Greedy. Katakanlah pengguna meminta $ 400,11. Apa cara untuk mengetahui berapa banyak perempat Anda butuhkan tanpa harus menghitung masing-masing? 

Setelah Anda mengetahui berapa banyak perempat Anda dapat menggunakan untuk membuat $ 400,11, berapa banyak mengubah sisa-sisa? Mungkin kombinasi di sini antara modulo dan pembagian akan datang berguna untuk memberikan keren, elegan pendekatan untuk masalah Greedy. Tapi ingat bahwa yang mengatur aturan masih berlaku. Selalu gunakan koin terbesar mungkin. 

Setelah Anda sudah melakukan perhitungan bagaimana banyak koin untuk digunakan, langkah terakhir adalah untuk mencetak jumlah koin yang dihitung. Sejauh ini, kami telah menggunakan printf berfungsi semata-mata untuk string. Tetapi bila Anda ingin mencetak sebuah In, atau sembarang jenis data yang disimpan dalam variabel, Anda harus menunjukkan bahwa menggunakan placeholder. 

Di sini saya telah menyertakan beberapa tips tentang cara untuk mencetak nilai. Jika Anda memiliki sebuah integer, Anda akan menulis string Anda menggunakan% d sebagai placeholder. Setelah kutipan penutupan mark, masukkan koma. Dan kemudian dimasukkan ke dalam integer yang akan mengambil tempat% d saat dicetak. 

Jadi setelah menampilkan nomor koin yang digunakan, Anda selesai dengan Greedy. Pastikan untuk memeriksa semua kasus sudut, merapikan gaya Anda sedikit, dan Anda siap untuk menyerahkan. Pada akhir set ini masalah, Anda akan lebih akrab dengan CS50 alat, terminal, dan loop struktur dan variabel dalam C. 

Kau baik di jalan. Kurva belajar bisa tampak sulit. Jadi mengambil langkah demi langkah. Pastikan Anda menuliskan pseudo-code sebelum menyelam terlalu dalam ke dalam sintaks asing. 

Buat daftar yang harus dilakukan, dan memecah tugas menjadi lebih kecil, lebih tugas dikelola. Jelajahi semua sumber daya CS50. Selain kuliah, rewatch ini berjalan melalui. 

Perhatikan dekat dengan bagian. Check out celana pendek. Baca pertanyaan teman sekelas Anda ' Diskusikan tentang, dan posting Anda sendiri. 

Best of luck dengan p-set. Dan terima kasih untuk menonton. Ini adalah Greedy. 

[MUSIC PLAYING]