Sebelum mengerjakan soal, tontonlah perkuliahan 7-8 , baca dan pelajari “ Materi tambahan minggu ketiga ”. Mereka dikhususkan untuk algoritma pencarian (linier dan biner), pengurutan (ada banyak!), serta pekerjaan debugger (kemampuan untuk bekerja dengan debugger untuk men-debug program adalah keterampilan yang sangat penting!). Jika semuanya berjalan sebagaimana mestinya dengan perkuliahan dan teori, Anda dapat dengan mudah menjawab soal tes:
Mengapa pencarian biner memerlukan array yang diurutkan?
Mengapa bubble sort diperkirakan O(n2)?
Mengapa estimasi pengurutan penyisipan Ω(n)?
Bagaimana cara kerja pengurutan seleksi? Jelaskan dalam tiga kalimat (atau kurang).
Berapa batas atas (kasus terburuk) berapa lama pengurutan gabungan dapat berjalan?
Debugger GDB memungkinkan Anda men-debug suatu program. Dan jika Anda merumuskannya secara lebih spesifik, apa sebenarnya yang dapat Anda lakukan?
Sasaran
Belajar bekerja dengan proyek yang berisi banyak file
Belajar membaca kode sumber orang lain
Memahami berbagai algoritma dan fungsi rekursif
Sebagian besar dari tujuan-tujuan ini praktis tidak mungkin untuk dievaluasi secara formal. Oleh karena itu, dari sudut pandang verifikasi formal atas suatu masalah, ada sedikit hal yang tampak sulit bagi Anda. Namun, kami mengingatkan Anda: Anda hanya dapat mempelajari pemrograman melalui latihan terus-menerus! Oleh karena itu, kami mendorong Anda tidak hanya menyelesaikan tugas, tetapi juga meluangkan waktu dan tenaga tambahan serta menerapkan semua algoritme yang dibahas minggu ini. Maju!
Mulai
Ingatlah bahwa untuk latihan soal di minggu pertama dan kedua, Anda menulis program dari awal dan membuat direktori pset1 dan pset2 Anda sendiri menggunakan perintah mkdir . Untuk tugas latihan minggu ketiga, Anda perlu mengunduh distribusi (atau "distro" begitu kami menyebutnya) yang kami tulis dan menambahkan baris kode Anda sendiri ke dalamnya. Pertama, baca kode kami dan cobalah memahaminya. Keterampilan terpenting minggu ini adalah mempelajari cara membaca kode orang lain. Jadi, masuk ke cs50.io dan jalankan perintah update50 di jendela terminal untuk memastikan versi ruang kerja adalah yang terbaru. Jika Anda tidak sengaja menutup jendela terminal dan tidak dapat menemukannya, buka menu Lihat dan pastikan opsi Konsol dicentang (centang jika tidak). Klik (+), di dalam lingkaran hijau pada bingkai jendela terminal, pilih Terminal Baru . Setelah itu, jalankan perintah cd ~/workspace dan pastikan Anda berada di dalam direktori ruang kerja (ini adalah direktori Anda). Setelah itu, jalankan perintah: wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip untuk mengunduh arsip ZIP dari buku masalah ke ruang kerja Anda (wget adalah perintah unduh Linux). Jika semuanya baik-baik saja, Anda akan melihat kalimat berikut di baris: 'pset3.zip' saved Pastikan Anda benar-benar mengunduh pset3.zip dengan menjalankan perintah: ls lalu jalankan unzip pset3.zip untuk mengekstrak file. Jika sekarang Anda menjalankan perintah ls lagi , Anda juga akan melihat direktori pset3 . Buka dengan menjalankan perintah cd pset3 lalu minta untuk melihat kembali isi direktori: ls Anda akan melihat ada dua subdirektori di direktori ini: fifteen find Sudah menarik!
Mencari
Sekarang mari selami salah satu subdirektori ini. Untuk melakukannya, kita akan menjalankan perintah: cd ~/workspace/pset3/find Jika Anda menampilkan isi folder ini di layar (Anda mungkin sudah ingat cara melakukannya), inilah yang akan Anda lihat: helpers.c helpers.h Makefile find.c generate.c Wow, ada banyak file. Tapi jangan khawatir, kami akan menanganinya sekarang. File generate.c berisi kode untuk program yang menggunakan "generator angka acak semu" (dihasilkan oleh fungsi drand48 ) untuk menghasilkan sejumlah besar angka acak (sebenarnya acak semu, komputer tidak dapat menangani keacakan murni!) , dan letakkan satu per satu dalam satu baris. Kompilasi program: make generate Sekarang jalankan dengan menjalankan perintah: ./generate Program akan memberi Anda pesan berikut: Usage: generate n [s] Ini berarti program mengharapkan satu atau dua argumen baris perintah. Menggunakan yang pertama, n, bersifat wajib; angka ini berarti berapa banyak angka pseudorandom yang ingin Anda buat. Parameter s bersifat opsional, seperti ditunjukkan dalam tanda kurung siku. Angka s dapat disebut sebagai "benih" untuk pembuat angka pseudorandom. Dengan "seed" yang kami maksud adalah data input ke generator bilangan pseudorandom yang mempengaruhi outputnya. Misalnya, jika Anda menggunakan drand48, pertama-tama panggil srand48 (fungsi lain yang tujuannya adalah untuk "menyemai" drand48) dengan argumen, katakanlah, 1, dan lalu memanggil drand48 tiga kali, drand48 mungkin akan menghasilkan 2728, lalu 29785, lalu 54710. Jika Anda menggunakan drand48 alih-alih yang sebelumnya, panggil srand48 terlebih dahulu dengan argumen, katakanlah, 2, lalu gunakan drand48 lagi tiga kali, drand48 mungkin kembalikan 59797, lalu 10425, lalu 37569. Tetapi jika Anda melihat kembali drand48 dengan memanggil srand48 lagi dengan argumen 1, hasil dari tiga panggilan berikutnya ke drand48 Anda akan mendapatkan 2728 lagi, lalu 29785, lalu 54710! Soalnya, segala sesuatu terjadi karena suatu alasan. Jalankan kembali programnya, kali ini katakanlah n=10, seperti gambar di bawah ini; Anda akan melihat daftar 10 angka pseudo-acak. ./generate 10 Mari kita jalankan program untuk ketiga kalinya dengan nilai n yang sama; Anda akan melihat daftar 10 angka lainnya. Sekarang coba jalankan program dengan dua parameter. Mari kita ambil s=0 seperti yang ditunjukkan di bawah ini. ./generate 10 0 Sekarang jalankan perintah yang sama lagi: ./generate 10 0 Anda bahkan tidak dapat berdebat: Anda melihat urutan sepuluh digit "acak" yang sama lagi. Inilah yang terjadi jika Anda tidak mengubah seed generator nomor pseudorandom. Sekarang mari kita lihat program generate.c itu sendiri(ingat bagaimana caranya?). Komentar di awal file ini menjelaskan fungsionalitas umum program. Namun sepertinya kami lupa mengomentari kode itu sendiri. Bacalah kode tersebut dengan cermat dan bacalah hingga Anda memahami arti setiap barisnya. Kemudian beri komentar pada kode ini untuk kami, ganti setiap TODO dengan frasa yang menjelaskan tujuan atau fungsi dari baris kode yang sesuai. (catatan: unsigned int adalah int “unsigned”, artinya tidak boleh negatif). Untuk mendapatkan informasi lebih lanjut tentang rand atau srand, jalankan: man drand48 atau man srand48 Setelah Anda memberi komentar sebanyak yang Anda bisa di generate.c, kompilasi ulang program untuk memastikan Anda tidak merusak apa pun: make generate Jika generate tidak lagi dapat dikompilasi, perbaiki apa yang Anda bangkrut: )! Sebagai pengingat, perintah make mengotomatiskan kompilasi kode, jadi Anda tidak perlu menjalankan perintah clang dengan memasukkan banyak sakelar secara manual. Namun pada kenyataannya, make hanya menyederhanakan masukan kita, namun pada kenyataannya, dentang yang sama dengan parameter yang kita perlukan tersembunyi di baliknya. Namun, seiring dengan semakin besarnya program Anda, make tidak lagi dapat memahami konteksnya bagaimana cara mengkompilasi kodenya. Dalam hal ini, Anda harus memberi tahu cara mengkompilasi program, terutama jika program tersebut melibatkan penggunaan file sumber yang berbeda (seperti .c). Untuk mengatasi masalah ini kita akan menggunakan file konfigurasi (Makefiles) yang memberitahukan apa yang harus dilakukan. Bagaimana perintah make mengetahui bagaimana kita harus mengkompilasi hasil? Faktanya, tim menggunakan file konfigurasi yang telah kami tulis. File ini bernama Makefile dan terletak di direktori yang sama dengan generate.c . Makefile adalah daftar aturan yang menentukan cara membuat file yang dihasilkan dari generate.c. Dalam file tersebut Anda akan menemukan, khususnya, baris-baris yang relevan: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c Baris pertama memberi tahu make bahwa "target" yang disebut generate harus dibuat dengan memanggil perintah dari baris kedua. Terlebih lagi, baris pertama memberitahukan make bahwa generate bergantung pada generate.c, yang berarti make hanya akan membangun kembali generate pada proses berikutnya jika file tersebut telah diubah. Bukan trik menghemat waktu yang buruk, bukan? Faktanya, jalankan kembali perintah di bawah ini jika Anda tidak mengubah generate.c . make generate Anda akan diberitahu bahwa generator telah diperbarui ke versi saat ini. Catatan : Indentasi di awal baris kedua bukanlah rangkaian spasi, melainkan karakter tab. Sayangnya, make mengharuskan perintah diawali dengan tab, jadi hati-hati jangan sampai mengubahnya menjadi spasi atau Anda akan mengalami kesalahan aneh! Bendera -Werror memberitahukan perintah dentangperlakukan peringatan (buruk) sebagai kesalahan (bahkan lebih buruk), sehingga Anda akan dipaksa (dengan cara yang baik dan mendidik!) untuk memperbaikinya. Sekarang mari kita lihat file find.c. Perhatikan bahwa program ini mengharapkan satu argumen baris perintah: "igloo", yang harus ditemukan di "tumpukan jerami" nilai. Setelah itu, review kodenya dan kompilasi programnya dengan menjalankan perintah di bawah ini. make find make pada dasarnya memberi kita hal berikut: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Perhatikan! Anda baru saja mengkompilasi aplikasi yang terdiri dari satu, tapi dua file: helpers.c dan find.c . Bagaimana cara mengetahui hal ini? Untuk memahami hal ini, buka kembali Makefile untuk melihat apa yang sebenarnya terjadi di sana. Baris yang relevan ada di bawah. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Yang kami maksud dengan ketergantungan (setelah titik dua) adalah perubahan apa pun pada find.c , helpers.c , atau helpers.h akan memaksa make untuk membangun kembali find saat dipanggil lagi untuk tujuan tersebut. Sekarang jalankan program ini dengan melakukan, misalnya, hal berikut: ./find 13 Setelah ini, Anda akan diminta untuk menyediakan tumpukan tertentu (yaitu bilangan bulat), dan memberi mereka sedotan satu per satu. Setelah Anda bosan mengetik angka, tekan kombinasi tombol Ctrl-D . Kombinasi ini akan mengirimkan karakter end-of-file (EOF) ke program. Simbol tersebut akan memaksa fungsi GetInt dari pustaka CS50 untuk mengembalikan konstanta INT_MAX , dan ini, pada gilirannya, find.c akan memaksa find untuk berhenti mengetik "stack". Program sekarang akan mencari jarum di tumpukan jerami yang Anda berikan, dan pada akhirnya akan memberi tahu Anda jika jarum itu ditemukan. Singkatnya, program mencari beberapa nilai dalam sebuah array. Setidaknya dia harus melakukannya, tetapi masalahnya dia belum menemukan apa pun! Tapi di sinilah Anda datang untuk menyelamatkan! Kami akan membicarakan pentingnya peran Anda nanti. Faktanya, proses penyediaan tumpukan jerami dapat diotomatisasi, setidaknya dengan "menggabungkan" output dari generate ke find sebagai input. Misalnya, perintah di bawah ini meneruskan 1000 angka pseudorandom ke find, yang kemudian mencari 42 di antara nilai tersebut. ./generate 1000 | ./find 42 Perhatikan bahwa ketika generate meneruskan data mentah ke find, Anda tidak akan melihat nomor generate, tetapi Anda akan melihat find berjalan . Alternatifnya, Anda dapat "mengarahkan" output dari generate ke file dengan perintah seperti ini: ./generate 1000 > numbers.txt Isi file ini dapat dialihkan ke input find dengan perintah: ./find 42 < numbers.txt Mari kita lihat lagi kode di Makefile dan perhatikan baris berikut: all: find generate Ini berarti Anda dapat membangun menghasilkan dan menemukan dengan menjalankan perintah berikut: make all Selain itu, perintah di bawah baris ini setara dengan perintah di atasnya, karena make membangun entri pertama di Makefile secara default. make Andai saja Anda dapat meringkas semua tugas latihan ini menjadi satu perintah! Tapi - sayang sekali! Terakhir, perhatikan baris terakhir di Makefile: clean: rm -f *.o a.out core find generate Entri ini memungkinkan Anda untuk menghapus semua file yang diakhiri dengan .o atau disebut inti (kami akan menjelaskannya sebentar lagi!), dan juga menjalankan program find atau generate dengan mudah. dengan mengeksekusi baris: Jika Anda ingin make clean bereksperimen, maka ada sesuatu yang perlu diperhatikan: jangan menambahkan, katakanlah, *.c ke baris terakhir Makefile! (mengapa?) Semua baris yang dimulai dengan tanda # hanyalah komentar.
Tugas 1: Pencarian
Saatnya untuk sesuatu yang menarik! Perhatikan bahwa find.c memanggil search , sebuah fungsi yang dideklarasikan dalam helpers.h . Sayangnya, kami lupa menerapkan fungsi ini sepenuhnya di helpers.c ! (Perlu dicatat bahwa kita dapat menggabungkan konten helpers.h dan helpers.c ke dalam satu find.c . Namun terkadang lebih baik untuk memisahkan program menjadi beberapa file. Terutama jika beberapa fungsi, atau lebih tepatnya fungsi utilitas, mungkin berguna untuk program lain. Seperti fungsi perpustakaan CS50 misalnya. Lihatlah helpers.c dan Anda akan melihat bahwa pencarian selalu menghasilkan nilai salah, terlepas dari apakah nilai yang diberikan ada dalam nilai. Tulis ulang pencarian sehingga menggunakan pencarian linier, menghasilkan nilai benar , jika nilai ada dalam nilai dan salah jika nilai tidak ada dalam nilai. Berhati-hatilah untuk segera mengembalikan false jika n tidak positif. Saat Anda siap untuk memeriksa validitas, coba panggil perintah berikut: Karena salah satu nomor ./generate 1000 50 | ./find 127 dicetak dengan menghasilkan ketika 50 diunggulkan adalah 127, kode Anda harus menemukan jarumnya! Sebaliknya, coba perintah ini: ./generate 1000 50 | ./find 128 Karena 128 tidak termasuk dalam kumpulan angka yang dihasilkan oleh hasilkan ketika 50 diunggulkan, kode Anda tidak harus menemukan "jarum" . Jalankan tes lainnya dengan menjalankan generate dengan beberapa seed, menganalisis output, dan mencari jarum yang seharusnya ada di tumpukan jerami. Perhatikan bahwa main di find.c ditulis sedemikian rupa sehingga find mengembalikan 0 jika "jarum" ditemukan, jika tidak maka akan mengembalikan 1. Anda dapat memeriksa apa yang disebut "kode keluaran" yang dikembalikan main ketika dijalankan setelah menjalankan beberapa lainnya perintah echo $? . Misalnya, jika implementasi pencarian Anda benar, jika Anda menjalankannya ./generate 1000 50 | ./find 127 echo $? Anda akan melihat 0, sedangkan 127 adalah di antara 1000 angka yang dihasilkan dengan menghasilkan benih 50, sehingga pencarian yang Anda tulis akan menghasilkan nilai true. Dalam hal ini, main (yang kami tulis) harus mengembalikan 0 (yaitu, keluar). Jika Anda memberikan input berikut ./generate 1000 50 | ./find 128 echo $? , Anda akan melihat 1 karena 128 bukan salah satu dari 1000 angka yang dihasilkan dengan seed 50. Dalam hal ini, pencarian (ditulis oleh Anda) akan menghasilkan false, dan main (ditulis oleh kami ) akan mengembalikan 1 ( dan kemudian menyelesaikan pekerjaan). Apakah Anda memahami logikanya? Jika semuanya sudah siap untuk diperiksa menggunakan check50, jalankan perintah berikut: check50 2015.fall.pset3.find helpers.c Omong-omong, Anda tidak boleh membiasakan diri menguji kode Anda menggunakan check50 sebelum mengujinya sendiri. Lagi pula, check50 tidak benar-benar ada, jadi menjalankan kode dengan sampel masukan Anda sendiri, membandingkan keluaran aktual dengan keluaran yang diharapkan, adalah kebiasaan terbaik yang dapat Anda lakukan saat ini. Benar sekali, jangan jadi ketagihan! Jika Anda tertarik untuk bermain-main dengan implementasi find asisten cs50, jalankan perintah ini: ~cs50/pset3/find
Penyortiran
Pencarian linier bukanlah sesuatu yang benar-benar mengesankan, tetapi dari kuliah pertama (dan pada kuliah ketujuh kami mengulangi trik ini lagi!) Anda ingat bahwa Anda dapat menemukan jarum di tumpukan jerami lebih cepat. Tapi pertama-tama kita perlu memilah tumpukan jerami kita. Perhatikan bahwa find.c memanggil sort , sebuah fungsi yang dideklarasikan dalam helpers.h . Sayangnya, kami “lupa” mengimplementasikan sepenuhnya fitur ini di helpers.c ! Lihatlah helpers.c dan Anda akan melihat bahwa pengurutan kembali secara instan, meskipun fungsi utama find sebenarnya meneruskannya ke array yang sebenarnya. Sekarang ingat sintaks deklarasi array. Anda tidak hanya menentukan tipe elemen array ini, tetapi Anda juga menentukan ukurannya dalam tanda kurung siku. Inilah yang kami lakukan untuk haystack di find.c : int haystack [MAX]; Namun saat melintasi array, Anda hanya menentukan namanya. Dan kita melakukannya dengan cara yang persis sama ketika kita menelusuri tumpukan jerami untuk melakukan pengurutan di find.c : sort (haystack, size); (Coba tebak mengapa kita meneruskan ukuran array itu secara terpisah?) Saat kita mendeklarasikan fungsi yang menggunakan array satu dimensi sebagai argumen, kita tidak perlu menentukan ukuran array. Demikian pula, kita tidak melakukan ini ketika kita mendeklarasikan pengurutan di helpers.h (dan helpers.c): void sort (int values [] int n); Terapkan pengurutan sehingga fungsinya benar-benar mengurutkan array angka dari kecil ke besar. Perlu waktu berjalan sama dengan O(n 2 ), di mana n adalah ukuran array. Anda mungkin ingin menerapkan pengurutan gelembung, pengurutan pilihan, atau pengurutan penyisipan, seperti yang kita pelajari di minggu ketiga. Namun, penting untuk diperhatikan: tidak ada cara yang "benar" untuk mengimplementasikan algoritma ini. Ada banyak sekali variasi. Faktanya, Anda selalu dapat memperbaikinya jika Anda mau, selama implementasi Anda menyatu dengan O(n2 ) . Namun, serahkan eksperimen pada isi fungsi, dan untuk menyederhanakan pengujian, jangan ubah deklarasi pengurutan kami. Seharusnya terlihat seperti ini: void sort (int values [] int n); Karena fungsi mengembalikan nilai kosong, maka seharusnya tidak mengembalikan array yang diurutkan. Sebaliknya, ia harus "secara destruktif" mengurutkan array aktual yang "dijalankannya", memindahkan elemen-elemennya. Pada minggu keempat kita akan membahas bahwa array dilewatkan berdasarkan referensi, bukan berdasarkan nilai. Artinya, sortir tidak akan menerima salinan array, tetapi array asli itu sendiri. Meskipun Anda tidak dapat mengubah deklarasi pengurutan kami, Anda selalu dapat mendefinisikan fungsi Anda sendiri di helpers.c, yang kemudian dapat dipanggil dari pengurutan. Putuskan sendiri cara terbaik untuk menguji penerapan pengurutan Anda. Jangan lupa bahwa printf dan GDB akan membantu Anda! Dan jangan lupa bahwa Anda dapat membuat urutan bilangan pseudo-acak yang sama berulang kali dengan menentukan secara eksplisit nilai benih untuk dihasilkan.
Pencarian biner, tip
Hal pertama yang perlu Anda pahami tentang fungsi find adalah kita sudah memiliki kode tertulis (distribusi). Kami hanya mengisi beberapa celah pada kode yang ada. Program find.c meminta masukan angka (yaitu, untuk mengisi "tumpukan"), dan kemudian mencari "jarum" di dalamnya atas permintaan pengguna, menggunakan fungsi pengurutan dan pencarian yang ditentukan dalam helpers.c . Jadi, find sudah ditulis, kita perlu menulis helpers . Jadi, inilah yang perlu kita lakukan:
Terapkan pencarian. Fungsi ini harus mengembalikan nilai benar jika nilai ditemukan di tumpukan dan salah jika tidak ada.
Menerapkan pengurutan, fungsi yang mengurutkan array nilai.
Awalnya, pencarian diimplementasikan secara linier. Tapi Anda bisa melakukannya lebih baik. Algoritme pencarian linier berjalan dalam waktu O(n) . Tugas Anda adalah menulis algoritma pencarian biner. Waktu eksekusinya adalah O(log n) . Namun masalahnya adalah perlunya data yang diurutkan sebagai masukan, jika tidak maka tidak akan berfungsi. Anda ingat contoh buku yang robek, dan Anda mungkin tahu mengapa demikian. Jika Anda telah melakukan pencarian biner melalui elemen-elemen dan tidak ada lagi yang tersisa (yaitu, tidak ada "jarum" di "tumpukan" ini), Anda memerlukan fungsi untuk mengembalikan false. Pencarian biner dapat diimplementasikan secara iteratif atau rekursif (David Malan berbicara tentang rekursi pada kuliah kedelapan).
Setelah itu, jalankan perintah 
GO TO FULL VERSION