Sebelum menghadapi masalah, tonton kuliah 7-8 , baca dan teliti " Bahan tambahan minggu ketiga ". Mereka menumpukan kepada algoritma carian (linear dan binari), menyusun (terdapat banyak daripada mereka!), serta kerja penyahpepijat (keupayaan untuk bekerja dengan penyahpepijat untuk menyahpepijat program adalah kemahiran yang sangat penting!). Jika semuanya berjalan sebagaimana mestinya dengan kuliah dan teori, anda boleh menjawab soalan ujian dengan mudah:
Mengapakah carian binari memerlukan tatasusunan yang disusun?
Mengapakah jenis gelembung dianggarkan sebagai O(n2)?
Mengapakah anggaran isihan sisipan Ω(n)?
Bagaimanakah isihan pemilihan berfungsi? Terangkan dalam tiga ayat (atau kurang).
Apakah had atas (kes terburuk) tentang berapa lama jenis cantuman boleh dijalankan?
Penyahpepijat GDB membolehkan anda menyahpepijat atur cara. Dan jika anda merumuskan dengan lebih khusus, apakah sebenarnya yang ia benarkan boleh anda lakukan?
Matlamat
Belajar untuk bekerja dengan projek yang mengandungi berbilang fail
Belajar membaca kod sumber orang lain
Memahami pelbagai algoritma dan fungsi rekursif
Kebanyakan matlamat ini hampir mustahil untuk dinilai secara rasmi. Oleh itu, dari sudut pandangan pengesahan formal masalah, terdapat sedikit perkara yang akan kelihatan sukar kepada anda. Walau bagaimanapun, kami mengingatkan anda: anda hanya boleh belajar pengaturcaraan melalui latihan berterusan! Oleh itu, kami menggalakkan anda bukan sahaja menyelesaikan tugasan, tetapi juga meluangkan masa dan usaha tambahan serta melaksanakan semua algoritma yang telah dibincangkan minggu ini. ke hadapan!
Mulakan
Ingat bahawa untuk masalah latihan dalam minggu satu dan dua, anda menulis program dari awal dan mencipta direktori pset1 dan pset2 anda sendiri menggunakan arahan mkdir . Untuk tugasan latihan minggu ketiga, anda perlu memuat turun pengedaran (atau "distro" seperti yang kami panggil) yang kami tulis dan tambah baris kod anda sendiri padanya. Mula-mula, baca kod kami dan cuba memahaminya. Kemahiran yang paling penting minggu ini ialah mempelajari cara membaca kod orang lain. Jadi, log masuk ke cs50.io dan jalankan arahan update50 dalam tetingkap terminal untuk memastikan versi ruang kerja dikemas kini. Jika anda menutup tetingkap terminal secara tidak sengaja dan tidak menemuinya, pergi ke menu Lihat dan pastikan pilihan Konsol ditandakan (semak jika tidak). Klik pada (+), di dalam bulatan hijau pada bingkai tetingkap terminal, pilih Terminal Baharu . Selepas itu, jalankan arahan cd ~/workspace dan pastikan anda berada di dalam direktori ruang kerja (ini adalah direktori anda). Selepas itu, jalankan arahan: wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip untuk memuat turun arkib ZIP buku masalah ke dalam ruang kerja anda (wget ialah arahan muat turun Linux). Jika semuanya ok, anda akan melihat frasa berikut dalam baris: 'pset3.zip' saved Pastikan anda benar-benar memuat turun pset3.zip dengan menjalankan arahan: ls dan kemudian jalankan unzip pset3.zip untuk unzip fail. Jika anda kini menjalankan arahan ls sekali lagi , anda juga akan melihat direktori pset3 . Pergi ke sana dengan menjalankan arahan cd pset3 dan kemudian minta untuk melihat kandungan direktori sekali lagi: ls anda akan melihat bahawa terdapat dua subdirektori dalam direktori ini: fifteen find Sudah menarik!
Cari
Sekarang mari kita selami salah satu daripada subdirektori ini. Untuk melakukan ini, kami akan menjalankan arahan: cd ~/workspace/pset3/find Jika anda memaparkan kandungan folder ini pada skrin (anda mungkin sudah ingat bagaimana untuk melakukan ini), inilah yang anda patut lihat: helpers.c helpers.h Makefile find.c generate.c Wow, terdapat banyak fail. Tetapi jangan risau, kami akan berurusan dengan mereka sekarang. Fail generate.c mengandungi kod untuk atur cara yang menggunakan "penjana nombor pseudo-rawak" (dijana oleh fungsi drand48 ) untuk menjana sejumlah besar nombor rawak (sebenarnya pseudo-rawak, komputer tidak boleh mengendalikan rawak tulen!) , dan letakkannya satu demi satu dalam baris. Susun atur cara: make generate Sekarang jalankan ia dengan menjalankan arahan: ./generate Program ini akan memberi anda mesej berikut: Usage: generate n [s] Ini bermakna bahawa atur cara menjangkakan satu atau dua argumen baris arahan. Menggunakan yang pertama, n, adalah wajib; nombor ini bermaksud bilangan nombor pseudorandom yang anda ingin buat. Parameter s adalah pilihan, seperti yang ditunjukkan oleh kurungan segi empat sama. Nombor s boleh dipanggil "benih" untuk penjana nombor pseudorandom. Dengan "benih" kami maksudkan data input kepada penjana nombor pseudorandom yang mempengaruhi outputnya. Contohnya, jika anda menggunakan drand48, pertama Dengan memanggil srand48 (fungsi lain yang tujuannya adalah untuk "membenihkan" drand48) dengan hujah, katakan, 1, dan kemudian memanggil drand48 tiga kali, drand48 mungkin kembali 2728, kemudian 29785, kemudian 54710. Jika anda bukannya yang sebelumnya, menggunakan drand48, mula-mula panggil srand48 dengan hujah, katakan, 2, dan kemudian gunakan drand48 sekali lagi tiga kali, drand48 mungkin kembalikan 59797, kemudian 10425, kemudian 37569. Tetapi jika anda melihat semula drand48 dengan memanggil srand48 sekali lagi dengan hujah 1, hasil daripada tiga panggilan seterusnya ke drand48 anda akan mendapat 2728 sekali lagi, kemudian 29785, kemudian 54710! Anda lihat, segala-galanya berlaku untuk alasan. Jalankan program sekali lagi, kali ini, katakan n=10, seperti yang ditunjukkan di bawah; anda akan melihat senarai 10 nombor pseudo-rawak. ./generate 10 Mari kita jalankan program kali ketiga dengan nilai n yang sama; anda sepatutnya melihat satu lagi senarai 10 nombor. Sekarang cuba jalankan program dengan dua parameter. Mari kita ambil s=0 seperti yang ditunjukkan di bawah. ./generate 10 0 Sekarang jalankan arahan yang sama sekali lagi: ./generate 10 0 Anda tidak boleh berhujah pun: anda melihat jujukan "rawak" yang sama sepuluh digit sekali lagi. Inilah yang berlaku jika anda tidak menukar benih penjana nombor pseudorandom. Sekarang mari kita lihat program generate.c itu sendiri(ingat bagaimana?). Komen pada permulaan fail ini menerangkan fungsi umum program. Tetapi kami seolah-olah terlupa untuk mengulas tentang kod itu sendiri. Baca kod dengan teliti dan baca sehingga anda memahami maksud setiap baris. Kemudian ulas kod ini untuk kami, menggantikan setiap TODO dengan frasa yang menerangkan tujuan atau fungsi baris atau baris kod yang sepadan. (nota: unsigned int ialah int "unsigned", bermakna ia tidak boleh negatif). Untuk mendapatkan maklumat lanjut tentang rand atau srand, jalankan: man drand48 atau man srand48 Selepas anda mengulas sebanyak yang anda boleh dalam generate.c, susun semula atur cara untuk memastikan anda tidak melanggar apa-apa: make generate Jika jana tidak lagi menyusun, betulkan perkara yang anda pecah :)! Sebagai peringatan, arahan make mengautomasikan kompilasi kod, jadi anda tidak perlu menjalankan perintah clang dengan memasukkan sekumpulan suis secara manual. Tetapi sebenarnya, make hanya memudahkan input kami, tetapi sebenarnya, dentang yang sama dengan parameter yang kami perlukan tersembunyi di belakangnya. Walau bagaimanapun, apabila program anda menjadi lebih besar, make tidak lagi dapat mengetahui dari konteks bagaimana untuk menyusun kod. Dalam kes ini, anda perlu memberitahu make bagaimana untuk menyusun atur cara, terutamanya jika ia melibatkan penggunaan fail sumber yang berbeza (seperti .c). Untuk menyelesaikan masalah ini, kami akan menggunakan fail konfigurasi (Makefiles) yang memberitahu make apa yang perlu dilakukan. Bagaimanakah arahan make tahu bagaimana kita harus menyusun menjana? Malah, pasukan itu menggunakan fail konfigurasi yang telah kami tulis. Fail ini dipanggil Makefile dan ia terletak dalam direktori yang sama seperti generate.c . Makefile ialah senarai peraturan yang menyatakan cara mencipta fail yang dijana daripada generate.c. Dalam fail, anda akan dapati, khususnya, baris yang berkaitan: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c Baris pertama memberitahu menjadikan "sasaran" yang dipanggil jana harus dibuat dengan memanggil arahan dari baris kedua. Selain itu, baris pertama memberitahu make yang menjana bergantung pada generate.c, yang bermaksud bahawa make hanya akan membina semula menjana pada larian berikutnya jika fail tersebut telah diubah. Bukan helah penjimatan masa yang buruk, bukan? Malah, jalankan arahan di bawah sekali lagi jika anda tidak menukar generate.c . make generate Anda akan dimaklumkan bahawa jana telah pun dikemas kini kepada versi semasa. Nota : Lekukan pada permulaan baris kedua bukanlah jujukan ruang, sebaliknya aksara tab. Malangnya, buat memerlukan arahan untuk didahului oleh tab, jadi berhati-hati untuk tidak menukarnya kepada ruang atau anda akan menghadapi ralat pelik! Bendera -Werror memberitahu arahan clanganggap amaran (buruk) sebagai kesilapan (lebih teruk lagi), jadi anda akan dipaksa (dengan cara yang baik, pendidikan!) untuk membetulkannya. Sekarang mari kita lihat pada fail find.c . Ambil perhatian bahawa program ini menjangkakan satu hujah baris arahan: "igloo", yang mesti ditemui dalam "timbunan jerami" nilai. Selepas itu, semak kod dan susun atur cara dengan menjalankan arahan di bawah. make find make pada dasarnya memberi kami perkara berikut: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Beri perhatian! Anda baru sahaja menyusun aplikasi yang terdiri daripada satu, tetapi dua fail: helpers.c dan find.c . Bagaimana membuat tahu tentang perkara ini? Untuk memahami perkara ini, buka Makefile sekali lagi untuk melihat apa yang sebenarnya berlaku di sana. Baris yang berkaitan adalah di bawah. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Apa yang kami maksudkan dengan kebergantungan (selepas titik bertindih) ialah sebarang perubahan untuk find.c , helpers.c , atau helpers.h akan memaksa membuat untuk membina semula find apabila ia dipanggil untuk tujuan tersebut. Sekarang jalankan program ini dengan melakukan, sebagai contoh, perkara berikut: ./find 13 Selepas ini, anda akan diminta untuk menyediakan timbunan tertentu (iaitu, integer), dan memberi mereka satu straw pada satu masa. Setelah anda bosan menaip nombor, tekan kombinasi kekunci Ctrl-D . Gabungan ini akan menghantar aksara akhir fail (EOF) kepada program. Simbol akan memaksa fungsi GetInt daripada perpustakaan CS50 untuk mengembalikan pemalar INT_MAX , dan ini, seterusnya, find.c akan memaksa find untuk berhenti menaip "tindanan". Program ini kini akan mencari jarum dalam timbunan jerami yang anda sediakan, dan ia akhirnya akan memberitahu anda jika ia ditemui. Ringkasnya, program mencari beberapa nilai dalam tatasusunan. Sekurang-kurangnya dia sepatutnya, tetapi tangkapannya ialah dia tidak akan menemui apa-apa lagi! Tetapi di sini anda datang untuk menyelamatkan! Kami akan bercakap tentang kepentingan peranan anda sedikit kemudian. Malah, proses menyediakan timbunan jerami boleh diautomasikan, sekurang-kurangnya dengan "menggabungkan" output jana ke dalam find sebagai input. Sebagai contoh, arahan di bawah melepasi 1000 nombor pseudorandom untuk dicari, yang kemudian mencari antara nilai tersebut untuk 42. ./generate 1000 | ./find 42 Ambil perhatian bahawa apabila jana lulus data mentah untuk mencari, anda tidak akan melihat nombor jana, tetapi anda akan melihat carian berjalan . Sebagai alternatif, anda boleh "mengalih semula" output jana ke fail dengan arahan seperti ini: ./generate 1000 > numbers.txt Kandungan fail ini boleh dialihkan ke input find dengan arahan: ./find 42 < numbers.txt Mari kita lihat sekali lagi kod dalam Makefile dan perhatikan baris berikut: all: find generate Ini bermakna anda boleh membina menjana dan mencari dengan menjalankan arahan berikut: make all Selain itu, arahan di bawah baris ini adalah bersamaan dengan arahan di atasnya, kerana make membina entri pertama dalam Makefile secara lalai. make Sekiranya anda boleh menguraikan semua tugas latihan ini kepada satu arahan! Tetapi - malangnya! Akhir sekali, perhatikan baris terakhir ini dalam Makefile: clean: rm -f *.o a.out core find generate Entri ini membolehkan anda mengalih keluar semua fail yang berakhir dengan .o atau dipanggil teras (kami akan menerangkannya sebentar lagi!), dan juga menjalankan program cari atau jana dengan mudah. dengan melaksanakan baris: Jika anda ingin make clean bereksperimen , maka berikut adalah sesuatu yang perlu diberi perhatian: jangan tambah, katakan, *.c pada baris terakhir Makefile itu! (kenapa?) Semua baris yang bermula dengan tanda # hanyalah ulasan.
Tugasan 1: Cari
Sudah tiba masanya untuk sesuatu yang menarik! Ambil perhatian bahawa find.c memanggil carian , fungsi yang diisytiharkan dalam helpers.h . Malangnya, kami terlupa untuk melaksanakan fungsi ini sepenuhnya dalam helpers.c ! (Perlu diingatkan bahawa kita boleh meletakkan kandungan helpers.h dan helpers.c ke dalam satu find.c . Tetapi kadangkala adalah lebih baik untuk memisahkan atur cara kepada beberapa fail. Terutamanya jika beberapa fungsi, atau lebih tepatnya fungsi utiliti, mungkin berguna untuk atur cara lain. Seperti fungsi perpustakaan CS50 contohnya. Lihat helpers.c dan anda akan melihat bahawa carian sentiasa mengembalikan palsu, tidak kira sama ada nilai yang diberikan dalam nilai. Tulis semula carian supaya ia menggunakan carian linear, mengembalikan benar , jika nilai dalam nilai dan palsu jika nilai tiada dalam nilai. Berhati-hati untuk mengembalikan palsu dengan segera jika n tidak positif. Apabila anda bersedia untuk menyemak kesahihan, cuba panggil arahan berikut: Memandangkan salah satu nombor ./generate 1000 50 | ./find 127 dicetak dengan jana apabila 50 telah disemai ialah 127, kod anda sepatutnya mencari jarum! Sebaliknya, cuba perintah ini: ./generate 1000 50 | ./find 128 Memandangkan 128 bukan antara set nombor yang dijana oleh jana apabila 50 telah dibiji, kod anda tidak mesti mencari "jarum" . Jalankan ujian lain dengan menjalankan jana dengan beberapa biji, menganalisis output, dan mencari jarum yang sepatutnya berada dalam timbunan jerami. Ambil perhatian bahawa main dalam find.c ditulis sedemikian rupa sehingga find mengembalikan 0 jika "jarum" ditemui, jika tidak ia mengembalikan 1. Anda boleh menyemak apa yang dipanggil "kod output" yang pulangan utama apabila dilaksanakan selepas menjalankan beberapa yang lain arahan echo $? . Sebagai contoh, jika pelaksanaan carian anda betul, jika anda menjalankan ./generate 1000 50 | ./find 127 echo $? anda akan melihat 0, manakala 127 adalah antara 1000 nombor yang dikeluarkan dengan menjana dengan benih 50, jadi carian yang anda tulis harus kembali benar. Dalam kes ini, main (ditulis oleh kami) harus mengembalikan 0 (iaitu, keluar). Jika anda memberikan input berikut ./generate 1000 50 | ./find 128 echo $? , anda akan melihat 1 kerana 128 bukan antara 1000 nombor yang dikeluarkan dengan menjana dengan benih 50. Dalam kes ini, carian (ditulis oleh anda) akan mengembalikan palsu, dan utama (ditulis oleh kami ) akan mengembalikan 1 ( dan kemudian menyelesaikan kerja). Adakah anda faham logiknya? Apabila semuanya sedia untuk diperiksa menggunakan check50, jalankan arahan berikut: check50 2015.fall.pset3.find helpers.c Ngomong-ngomong, anda tidak seharusnya membiasakan diri untuk menguji kod anda menggunakan check50 sebelum mengujinya sendiri. Lagipun, check50 tidak benar-benar wujud, jadi menjalankan kod dengan sampel input anda sendiri, membandingkan output sebenar dengan output yang dijangkakan, adalah tabiat terbaik yang boleh anda lakukan pada ketika ini. Memang benar, jangan menjadi ketagih! Jika anda berminat untuk bermain dengan pelaksanaan pencarian pembantu cs50, jalankan arahan ini: ~cs50/pset3/find
Menyusun
Carian linear bukanlah sesuatu yang benar-benar mengagumkan, tetapi dari kuliah pertama (dan pada kuliah ketujuh kami mengulangi helah ini sekali lagi!) anda ingat bahawa anda boleh mencari jarum dalam timbunan jerami dengan lebih cepat. Tetapi pertama-tama kita perlu menyusun tumpukan jerami kita. Ambil perhatian bahawa find.c memanggil sort , fungsi yang diisytiharkan dalam helpers.h . Malangnya, kami "terlupa" untuk melaksanakan sepenuhnya ciri ini dalam helpers.c ! Lihat ke dalam helpers.c dan anda akan melihat jenis itu kembali serta-merta, walaupun fungsi utama find sebenarnya memberikannya kepada tatasusunan sebenar. Sekarang ingat sintaks pengisytiharan tatasusunan. Anda bukan sahaja menentukan jenis elemen tatasusunan ini, tetapi anda juga menentukan saiznya dalam kurungan segi empat sama. Inilah yang kami lakukan untuk timbunan jerami dalam find.c : int haystack [MAX]; Tetapi apabila melintasi tatasusunan, anda hanya menentukan namanya. Dan kita melakukannya dengan cara yang sama apabila kita melalui timbunan jerami untuk melakukan sorting dalam find.c : sort (haystack, size); (Teka mengapa kita lulus saiz tatasusunan itu secara berasingan?) Apabila kita mengisytiharkan fungsi yang mengambil tatasusunan satu dimensi sebagai hujah, kita tidak perlu menentukan saiz tatasusunan. Begitu juga, kami tidak melakukan ini apabila kami mengisytiharkan isihan dalam helpers.h (dan helpers.c): void sort (int values [] int n); Laksanakan isihan supaya fungsi benar-benar mengisih tatasusunan nombor daripada kecil ke besar. Ia perlu menjalankan masa sama dengan O(n 2 ), dengan n ialah saiz tatasusunan. Anda mungkin mahu melaksanakan isihan gelembung, isihan pemilihan atau isihan sisipan, seperti yang kita pelajari tentang perkara tersebut dalam minggu ketiga. Walau bagaimanapun, adalah penting untuk ambil perhatian: tiada cara "betul" untuk melaksanakan algoritma ini. Terdapat sejumlah besar variasi. Malah, anda sentiasa boleh memperbaikinya jika anda rasa sesuai, selagi pelaksanaan anda menumpu kepada O(n2 ) . Walau bagaimanapun, serahkan percubaan kepada badan fungsi, dan untuk memudahkan ujian, jangan ubah pengisytiharan isihan kami. Ia sepatutnya kelihatan seperti ini: void sort (int values [] int n); Memandangkan fungsi mengembalikan nilai kosong, ia tidak sepatutnya mengembalikan tatasusunan yang diisih. Sebaliknya, ia mesti "memusnahkan" menyusun tatasusunan sebenar yang "dijalankan" melaluinya, menggerakkan elemennya. Dalam minggu keempat kita akan membincangkan bahawa tatasusunan diluluskan melalui rujukan dan bukannya nilai. Iaitu, isihan tidak akan menerima salinan tatasusunan, tetapi tatasusunan asal itu sendiri. Walaupun anda tidak boleh menukar pengisytiharan isihan kami, anda sentiasa boleh menentukan fungsi anda sendiri dalam helpers.c, yang kemudiannya boleh dipanggil daripada isihan. Tentukan sendiri cara terbaik untuk menguji pelaksanaan isihan anda. Jangan lupa bahawa printf dan GDB akan membantu anda! Dan jangan lupa bahawa anda boleh mencipta urutan nombor rawak pseudo yang sama berulang kali dengan menyatakan secara eksplisit nilai benih untuk dijana.
Carian binari, petua
Perkara pertama yang anda perlu fahami tentang fungsi cari ialah kami sudah mempunyai kod bertulis (pengedaran). Kami hanya mengisi beberapa jurang dalam kod sedia ada. Program find.c meminta input nombor (iaitu, untuk mengisi "timbunan"), dan kemudian mencari "jarum" di dalamnya atas permintaan pengguna, menggunakan fungsi isihan dan carian yang ditakrifkan dalam helpers.c . Jadi, find sudah ditulis, kita perlu menulis pembantu . Jadi inilah yang perlu kita lakukan:
Laksanakan carian. Fungsi ini harus kembali benar jika nilai ditemui dalam timbunan dan palsu jika ia tidak ada.
Laksanakan isihan, fungsi yang menyusun tatasusunan nilai.
Pada mulanya, carian dilaksanakan sebagai linear. Tetapi anda boleh melakukan lebih baik. Algoritma carian linear berjalan dalam masa O(n) . Tugas anda ialah menulis algoritma carian binari. Masa pelaksanaannya ialah O(log n) . Walau bagaimanapun, masalahnya ialah ia memerlukan data yang diisih sebagai input, jika tidak, ia tidak akan berfungsi. Anda masih ingat contoh buku yang koyak itu, dan anda mungkin tahu mengapa demikian. Jika anda telah melalui carian binari melalui unsur-unsur dan tidak ada lagi unsur tersebut (iaitu, tiada "jarum" dalam "timbunan" ini), anda memerlukan fungsi untuk mengembalikan palsu. Carian binari boleh dilaksanakan secara iteratif atau rekursif (David Malan bercakap tentang rekursi dalam kuliah kelapan).
Selepas itu, jalankan arahan 
GO TO FULL VERSION