Sadurunge njupuk ing masalah, nonton ceramah 7-8 , maca lan delve menyang " Bahan tambahan minggu katelu ". Dheweke dikhususake kanggo algoritma telusuran (linear lan binar), ngurutake (ana akeh!), Uga karya debugger (kemampuan kanggo nggarap debugger kanggo debug program minangka skill sing penting banget!). Yen kabeh wis rampung karo ceramah lan teori, sampeyan bisa kanthi gampang mangsuli pitakon tes:
Napa panelusuran binar mbutuhake larik sing diurutake?
Napa urutan gelembung ditaksir dadi O(n2)?
Kenapa perkiraan urut sisipan Ω(n)?
Kepiye cara ngurutake pilihan? Terangna ing telung ukara (utawa kurang).
Apa watesan ndhuwur (kasus paling awon) babagan suwene ngurutake gabungan?
Debugger GDB ngidini sampeyan debug program. Lan yen sampeyan ngrumusake luwih spesifik, apa sing bisa ditindakake?
gol
Sinau nggarap proyek sing ngemot pirang-pirang file
Sinau maca kode sumber wong liya
Ngerti macem-macem algoritma lan fungsi rekursif
Umume tujuan kasebut meh ora bisa dievaluasi kanthi resmi. Mulane, saka sudut pandang verifikasi resmi masalah, mung ana sing angel kanggo sampeyan. Nanging, kita ngelingake sampeyan: sampeyan mung bisa sinau program liwat latihan terus-terusan! Mulane, disaranake sampeyan ora mung kanggo ngatasi tugas, nanging uga nglampahi wektu lan gaweyan tambahan lan ngleksanakake kabeh algoritma sing dibahas minggu iki. Maju!
miwiti
Elinga yen kanggo masalah latihan ing minggu siji lan loro, sampeyan nulis program saka ngeruk lan nggawe direktori pset1 lan pset2 dhewe nggunakake printah mkdir . Kanggo tugas latihan minggu katelu, sampeyan kudu ngundhuh distribusi (utawa "distro" sing diarani) sing kita tulis lan nambahake baris kode sampeyan dhewe. Pisanan, waca kode kita lan coba ngerti. Katrampilan sing paling penting minggu iki yaiku sinau maca kode wong liya. Dadi, mlebu menyang cs50.io lan jalanake perintah kasebut update50 ing jendela terminal kanggo mesthekake yen versi ruang kerja anyar. Yen sampeyan ora sengaja nutup jendhela terminal lan ora bisa nemokake, pindhah menyang menu View lan priksa manawa pilihan Console wis dicenthang (priksa yen ora). Klik ing (+), ing jero bunder ijo ing pigura jendhela terminal, pilih New Terminal . Sawise iku, jalanake perintah kasebut cd ~/workspace lan priksa manawa sampeyan ana ing direktori ruang kerja (iki direktori sampeyan). Sawisé iku, jalanake printah: wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip kanggo ndownload arsip ZIP saka buku masalah menyang ruang kerja sampeyan (wget minangka perintah download Linux). Yen kabeh iku ok, sampeyan bakal weruh tembung ing ngisor iki ing baris: 'pset3.zip' saved Priksa manawa sampeyan pancene diundhuh pset3.zip dening mbukak printah: ls lan banjur mbukak unzip pset3.zip kanggo unzip file. Yen saiki sampeyan mbukak printah ls maneh , sampeyan uga bakal weruh direktori pset3 . Pindhah menyang kanthi mbukak printah cd pset3 banjur njaluk kanggo ndeleng isi direktori maneh: ls sampeyan bakal weruh sing ana rong subdirektori ing direktori iki: fifteen find Wis nyenengake!
Nggoleki
Ayo saiki nyilem menyang salah sawijining subdirektori kasebut. Kanggo nindakake iki, kita bakal mbukak printah: cd ~/workspace/pset3/find Yen sampeyan nampilake isi folder iki ing layar (sampeyan mbokmenawa wis ngelingi carane nindakake iki), iki apa sampeyan kudu ndeleng: helpers.c helpers.h Makefile find.c generate.c Wah, ana akeh file. Nanging aja kuwatir, saiki kita bakal ngatasi. File generate.c ngemot kode kanggo program sing nggunakake "generator nomer pseudo-acak" (digawe dening fungsi drand48 ) kanggo generate nomer akeh acak (bener pseudo-acak, komputer ora bisa nangani randomness murni!) , lan nyelehake siji-sijine ing baris.Kompilasi program: make generate Saiki jalanake kanthi nglakokake printah: ./generate Program bakal menehi pesen ing ngisor iki: Usage: generate n [s] Iki tegese program ngarepake siji utawa loro argumen baris perintah. Nggunakake sing pisanan, n, wajib; nomer iki tegese nomer pseudorandom sing pengin digawe. Parameter s opsional, kaya sing dituduhake ing tanda kurung. Nomer s bisa kasebut "wiji" kanggo generator nomer pseudorandom. Miturut "wiji" kita tegese data input menyang generator nomer pseudorandom sing mengaruhi output sawijining.Contone, yen sampeyan nggunakake drand48, pisanan Kanthi nelpon srand48 (fungsi liyane sing tujuane kanggo "wiji" drand48) karo argumen, ngomong, 1, lan banjur nelpon drand48 kaping telu, drand48 bisa bali 2728, banjur 29785, banjur 54710. Yen sampeyan tinimbang sing sadurunge, nggunakake drand48, pisanan nelpon srand48 kanthi argumen, ucapake, 2, banjur nggunakake drand48 maneh kaping telu, drand48 bisa uga. bali 59797, banjur 10425, banjur 37569. Nanging yen sampeyan ndeleng maneh drand48 dening nelpon srand48 maneh karo bantahan 1, asil saka telung telpon sabanjuré kanggo drand48 sampeyan bakal njaluk 2728 maneh, banjur 29785, banjur 54710! Sampeyan ndeleng, kabeh kedadeyan amarga ana alesan. Mbukak program maneh, wektu iki, ngandika n = 10, minangka kapacak ing ngisor iki; sampeyan bakal weruh dhaptar 10 nomer pseudo-acak. ./generate 10 Ayo dadi mbukak program kaping telune karo nilai padha n; sampeyan kudu ndeleng dhaptar liyane 10 nomer. Saiki coba mbukak program kanthi rong paramèter. Ayo njupuk s = 0 minangka ditampilake ing ngisor iki. ./generate 10 0 Saiki mbukak printah padha maneh: ./generate 10 0 Sampeyan malah ora bisa argue: sampeyan ndeleng padha "acak" urutan sepuluh digit maneh. Iki kedadeyan yen sampeyan ora ngganti wiji generator nomer pseudorandom. Saiki ayo kang katon ing generate.c program dhewe(elinga carane?). Komentar ing wiwitan file iki nerangake fungsi umum program kasebut. Nanging kita koyone wis lali kanggo komentar ing kode dhewe. Waca kode kasebut kanthi teliti lan waca nganti sampeyan ngerti makna saben baris. Banjur komentar metu kode iki kanggo kita, ngganti saben TODO karo frase njlèntrèhaké tujuan utawa fungsi baris cocog utawa baris kode. (cathetan: unsigned int minangka "unsigned" int, tegese ora bisa negatif). Kanggo entuk informasi luwih lengkap babagan rand utawa srand, mbukak: man drand48 utawa man srand48 Sawise sampeyan wis menehi komentar sabisane ing generate.c, ngumpulake maneh program kanggo mesthekake yen sampeyan ora nglanggar apa-apa: make generate Yen generate ora dikompilasi maneh, ndandani apa sing sampeyan tindakake. putus :)! Minangka pangeling, printah make ngotomatisasi kompilasi kode, supaya sampeyan ora kudu mbukak printah clang kanthi manual nglebokake akeh switch. Nanging nyatane, nggawe mung simplifies input kita, nanging nyatane, clang padha karo paramèter kita kudu didhelikake konco. Nanging, nalika program dadi luwih gedhe, nggawe ora bisa ngerti maneh saka konteks carane ngumpulake kode. Ing kasus iki, sampeyan kudu menehi pitutur marang nggawe carane ngumpulake program, utamané yen padha melu nggunakake file sumber beda (kayata .c). Kanggo ngatasi masalah iki, kita bakal nggunakake file konfigurasi (Makefiles) sing ngandhani apa sing kudu ditindakake. Kepiye carane nggawe printah ngerti carane kita kudu ngumpulake generate? Nyatane, tim nggunakake file konfigurasi sing wis ditulis. Berkas iki diarani Makefile lan dumunung ing direktori sing padha karo generate.c . Makefile minangka dhaptar aturan sing nemtokake carane nggawe file generate saka generate.c. Ing file sampeyan bakal nemokake, ing tartamtu, baris cocog: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c Ing baris pisanan ngandhani nggawe sing "target" disebut generate kudu digawe dening nelpon printah saka baris kapindho. Menapa malih, baris pisanan ngandhani make sing generate gumantung generate.c, kang tegese make mung bakal mbangun maneh generate ing mlaku sakteruse yen file sing wis diganti. Ora trick ngirit wektu sing ala, ta? Nyatane, mbukak printah ing ngisor iki maneh yen sampeyan ora ngganti generate.c . make generate Sampeyan bakal dilaporake yen generate wis dianyari kanggo versi saiki. Cathetan : Indentasi ing wiwitan baris kapindho dudu urutan spasi, nanging minangka karakter tab. Sayange, nggawe mbutuhake printah kanggo didhisiki dening tab, supaya ati-ati supaya ora ngganti menyang spasi utawa sampeyan bakal nemoni kasalahan aneh! Gendéra -Werror ngandhani printah clangnganggep bebaya (ala) minangka kasalahan (malah luwih elek), supaya sampeyan bakal dipeksa (kanthi cara sing apik, pendidikan!) kanggo mbenerake. Saiki ayo goleki file find.c . Elinga yen program iki ngarepake siji argumen baris perintah: "igloo", sing kudu ditemokake ing "haystack" nilai. Sawisé iku, deleng kode lan ngumpulake program kanthi nglakokake printah ing ngisor iki. make find nggawe Sejatine menehi kita ing ngisor iki: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Pay manungsa waé! Sampeyan mung wis nyusun aplikasi sing dumadi saka siji, nanging rong file: helpers.c lan find.c . Kepiye carane ngerti babagan iki? Kanggo mangerteni iki, bukak Makefile maneh kanggo ndeleng apa sing kedadeyan ing kana. Garis sing cocog ana ing ngisor iki. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Apa tegese gumantung (sawise titik loro) yaiku owah-owahan apa wae sing bakal ditemokake.c , helpers.c , utawa helpers.h bakal meksa nggawe maneh nemokake yen sabanjure diarani kanggo tujuan kasebut. Saiki mbukak program iki kanthi nindakake, contone, ing ngisor iki: ./find 13 Sawise iki, sampeyan bakal dijaluk kanggo nyedhiyani tumpukan tartamtu (yaiku, integers), lan Feed wong kang dipercoyo siji ing wektu. Sawise kesel ngetik angka, pencet kombinasi tombol Ctrl-D . Kombinasi iki bakal ngirim program karakter end-of-file (EOF). Simbol bakal meksa fungsi GetInt saka perpustakaan CS50 kanggo bali INT_MAX pancet , lan iki, ing siji, ing find.c bakal meksa golek kanggo mungkasi ngetik "tumpukan". Program saiki bakal nggoleki jarum ing tumpukan jerami sing diwenehake, lan pungkasane bakal ngandhani yen ditemokake. Ing cendhak, program nggoleki sawetara nilai ing array. Paling ora dheweke kudu, nanging sing nyekel dheweke ora bakal nemokake apa-apa! Nanging ing kene sampeyan teka kanggo ngluwari! Kita bakal ngomong babagan pentinge peran sampeyan mengko. Nyatane, proses nyedhiyakake tumpukan jerami bisa otomatis, paling ora kanthi "nggabungake" output ngasilake dadi golek minangka input. Contone, printah ing ngisor iki ngliwati 1000 nomer pseudorandom kanggo nggoleki, sing banjur nggoleki ing antarane nilai kasebut kanggo 42. ./generate 1000 | ./find 42 Elinga yen nalika generate pass data mentah kanggo nggoleki, sampeyan ora bakal weruh nomer generate, nanging sampeyan bakal weruh golek mlaku. . Utawa, sampeyan bisa "ngalihake" output saka generate menyang file kanthi printah kaya iki: ./generate 1000 > numbers.txt Isi file iki bisa redirected menyang input saka golek karo printah: ./find 42 < numbers.txt Ayo dipikir liyane ing kode ing Makefile lan sok dong mirsani baris ing ngisor iki: all: find generate Iki tegese sampeyan bisa mbangun generate lan nemokake dening mlaku printah ing ngisor iki: make all Menapa malih, printah ing ngisor iki baris padha karo printah ing ndhuwur iku, wiwit nggawe mbangun entri pisanan ing Makefile minangka standar. make Yen mung sampeyan bisa nggodhok kabeh tugas latihan iki dadi siji prentah! Nanging - ala! Akhire, mbayar manungsa waé kanggo baris pungkasan iki ing Makefile: clean: rm -f *.o a.out core find generate Entri iki ngijini sampeyan kanggo mbusak kabeh file sing pungkasan ing .o utawa disebut inti (kita bakal nerangake iki ing wayahe!), Lan uga mbukak golek utawa generate program mung. dening nglakokaké baris: Yen sampeyan pengin make clean eksprimen , banjur kene soko sing kudu ati-ati karo: ora nambah, ngomong, * .c kanggo baris pungkasan Makefile! (kenapa?) Kabeh baris sing diwiwiti kanthi tandha # mung komentar.
Tugas 1: Nggoleki
Iku wektu kanggo soko menarik! Elinga yen find.c nelpon search , fungsi sing diumumake ing helpers.h . Sayange, kita kelalen ngleksanakake fungsi iki rampung ing helpers.c ! (Perlu dicathet menawa kita bisa nyelehake isi helpers.h lan helpers.c dadi siji find.c . Nanging kadhangkala luwih apik kanggo misahake program dadi sawetara file. Utamane yen sawetara fungsi, utawa fungsi utilitas, bisa migunani. kanggo program liyane. Kaya fungsi perpustakaan CS50 contone. Coba deleng helpers.c lan sampeyan bakal weruh sing telusuran tansah bali palsu, preduli saka apa nilai diwenehi ing nilai. Tulis maneh panelusuran supaya nggunakake search linear, bali bener , yen nilai ana ing nilai lan palsu yen nilai ora ana ing nilai. Ati-ati bali palsu yen n ora positif. Yen sampeyan siyap mriksa validitas, coba nelpon printah ing ngisor iki: Wiwit salah siji saka nomer ./generate 1000 50 | ./find 127 dicithak karo generate nalika 50 wis winih punika 127, kode sampeyan kudu golek jarum! Kanggo kontras, nyoba printah iki: ./generate 1000 50 | ./find 128 Wiwit 128 ora antarane pesawat saka nomer kui dening generate nalika 50 wis winih, kode sampeyan ora kudu nemokake "jarum" . Mbukak tes liyane dening mlaku generate karo sawetara wiji, nganalisa output, lan looking for jarum sing kudu ing haystack. Elinga yen utama ing find.c ditulis kanthi cara sing nemokake ngasilake 0 yen "jarum" ditemokake, yen ora, bakal ngasilake 1. Sampeyan bisa mriksa sing disebut "kode output" sing ngasilake utama nalika dieksekusi sawise mlaku sawetara liyane. dhawuh echo $? . Contone, yen implementasine telusuran sampeyan bener, yen sampeyan mbukak ./generate 1000 50 | ./find 127 echo $? sampeyan bakal weruh 0, dene 127 ana ing antarane 1000 nomer output kanthi ngasilake wiji 50, mula telusuran sing sampeyan tulis kudu bali bener. Ing kasus iki, utama (ditulis dening kita) kudu bali 0 (yaiku, metu). Yen sampeyan menehi input ing ngisor iki ./generate 1000 50 | ./find 128 echo $? , sampeyan bakal weruh 1 amarga 128 ora ana ing antarane 1000 nomer sing digawa metu kanthi wiji 50. Ing kasus iki, panelusuran (ditulis dening sampeyan) bakal bali palsu, lan utama (ditulis dening kita). ) bakal bali 1 ( banjur rampung proyek). Apa sampeyan ngerti logika? Yen kabeh wis siyap dipriksa nggunakake check50, jalanake printah ing ngisor iki: check50 2015.fall.pset3.find helpers.c Miturut cara, sampeyan ora bisa digunakake kanggo nyoba kode nggunakake check50 sadurunge nyoba dhewe. Sawise kabeh, check50 ora ana, mula kode kasebut nganggo conto input sampeyan dhewe, mbandhingake output nyata karo output sing dikarepake, minangka pakulinan paling apik sing bisa ditindakake ing wektu iki. Bener, aja ketagihan! Yen sampeyan kepengin main karo implementasine asisten cs50, jalanake printah iki: ~cs50/pset3/find
Ngurutake
Panelusuran linear ora soko sing saestu nyengsemaken, nanging saka ceramah pisanan (lan ing kapitu kita mbaleni trick iki maneh!) Sampeyan elinga yen sampeyan bisa nemokake jarum ing tumpukan jerami luwih cepet. Nanging pisanan kita kudu ngurutake tumpukan jerami. Elinga yen find.c nelpon Urut , fungsi sing diumumake ing helpers.h . Sayange, kita "kelalen" kanggo ngleksanakake fitur iki kanthi lengkap ing helpers.c ! Deleng menyang helpers.c lan sampeyan bakal weruh sing Urut bali enggal, sanajan fungsi utama find bener ngliwati array nyata. Saiki elinga sintaks deklarasi array. Sampeyan ora mung nemtokake jinis unsur array iki, nanging uga nemtokake ukuran ing kurung kothak. Iki sing ditindakake kanggo tumpukan jerami ing find.c : int haystack [MAX]; Nanging nalika ngliwati array, sampeyan mung nemtokake jenenge. Lan kita nindakake iku persis cara sing padha nalika kita liwat tumpukan jerami kanggo nindakake Urut ing find.c : sort (haystack, size); (Guess kok kita pass ukuran array sing kapisah?) Nalika kita wara-wara fungsi sing njupuk Uploaded siji-dimensi minangka bantahan, kita ora perlu nemtokake ukuran array. Uga, kita ora nindakake iki nalika kita ngumumake Urut ing helpers.h (lan helpers.c): void sort (int values [] int n); Ngleksanakake Urut supaya fungsi bener ngurutake Uploaded nomer saka cilik kanggo gedhe. Iku perlu kanggo mbukak wektu witjaksono kanggo O(n 2 ), ngendi n iku ukuran array. Sampeyan bisa uga pengin ngleksanakake urutan gelembung, urutan pilihan, utawa ngurutake sisipan, kaya sing kita sinau babagan minggu telu. Nanging, penting kanggo dicathet: ora ana cara sing "bener" kanggo ngetrapake algoritma kasebut. Ana akeh variasi. Nyatane, sampeyan bisa tansah nambah yen sampeyan ndeleng pas, anggere implementasine converges kanggo O(n2 ) . Nanging, ninggalake eksperimen menyang awak fungsi, lan kanggo nyederhanakake tes, aja ngganti deklarasi urut. Iku kudu katon kaya iki: void sort (int values [] int n); Wiwit fungsi ngasilake nilai roso sepi, iku ngirim ora ngasilake Uploaded diurutake. Nanging, iku kudu "destructively" ngurutake array nyata iku "mlaku" liwat, obah sawijining unsur. Ing minggu papat kita bakal ngrembug manawa array dilewati kanthi referensi tinimbang kanthi nilai. Tegese, Urut ora bakal nampa salinan array, nanging array asli dhewe. Nalika sampeyan ora bisa ngganti deklarasi Urut, sampeyan bisa tansah nemtokake fungsi dhewe ing helpers.c, kang banjur bisa disebut saka Urut. Temtokake dhewe carane paling apik kanggo nyoba implementasine ngurutake sampeyan. Aja lali yen printf lan GDB bakal mbantu sampeyan! Lan aja lali manawa sampeyan bisa nggawe urutan nomer pseudo-acak sing padha bola-bali kanthi kanthi tegas nemtokake nilai wiji kanggo ngasilake.
Panelusuran binar, tips
Babagan pisanan sampeyan kudu ngerti babagan fungsi temokake yaiku kita wis duwe kode ditulis (distribusi). Kita mung ngisi sawetara kesenjangan ing kode sing ana. Program find.c njaluk input nomer (yaiku, kanggo ngisi "tumpukan"), banjur nggoleki "jarum" ing panjalukan pangguna, nggunakake fungsi urut lan telusuran sing ditetepake ing helpers.c . Dadi, golek wis ditulis, kita kudu nulis helpers . Mangkene apa sing kudu ditindakake:
Ngleksanakake panelusuran. Fungsi iki kudu ngasilake bener yen nilai ditemokake ing tumpukan lan palsu yen ora ana.
Ngleksanakake Urut, fungsi sing ngurutake array saka nilai.
Kaping pisanan, telusuran dileksanakake minangka linear. Nanging sampeyan bisa nindakake luwih apik. Algoritma telusuran linier mlaku ing wektu O(n) . Tugas sampeyan nulis algoritma telusuran binar. Wektu eksekusi yaiku O(log n) . Nanging, masalahe yaiku mbutuhake data sing diurutake minangka input, yen ora, ora bakal bisa digunakake. Sampeyan elinga conto saka buku ambruk, lan sampeyan mbokmenawa ngerti apa iki supaya. Yen sampeyan wis ngliwati telusuran binar liwat unsur-unsur kasebut lan ora ana sing isih ana (yaiku, ora ana "jarum" ing "tumpukan" iki), sampeyan butuh fungsi kanggo ngasilake palsu. Panelusuran biner bisa ditindakake kanthi iteratif utawa rekursif (David Malan ngomong babagan rekursi ing kuliah kaping wolu).
Sawise iku, jalanake perintah kasebut 
GO TO FULL VERSION