JASON Hirschhorn: Bine ați venit la trei saptamani, toată lumea. Avem o ocupat, dar interesant secțiune în fața noastră. Deci, în primul rând, pentru că am făcut ceva progrese cu cursul, dar am încă au o mulțime de învățare de făcut, eu sunt va arăta voi unele resurse care ar trebui să se dovedesc a fi extrem de utile cum vă apropiați nu numai dvs. Seturi problemă, ci și digera toate materialul va da tipi în prelegeri și pantaloni scurți și secțiunea. Apoi ne-am de gând să-și petreacă primele 20 la 25 de minute de secțiune a merge peste GDB, care poate sau nu poate avea folosit în acest moment, dar este o instrument incredibil de util, care va ajuta să vă depana programele pe care. O mulțime de ați fi putut folosi printf în mijloc de programul tău să dau ce a constituit o variabilă. GDB este chiar mai bine decât printf și nu șurub sus codul pentru că rulați-l pe un fișier executabil. Asa ca vom trece peste cele mai utile 10 comenzi aveți nevoie pentru GDB, și suntem de gând să meargă pe un exercițiu împreună așa în problema stabilit trei și dincolo, tu pot utiliza GDB pentru a ajuta la depanare programele. Și, în sfârșit, vom trece peste unele de sortare și căutare algoritmi că ai văzut în curs, și suntem va de fapt cod, nu doar pseudocod, dar cod binar de căutare, bule de sortare, și selecție de sortare. Deci, în primul rând, vreau să merg asupra resurselor. Aceasta este o listă extinsă, și este font mai mic pentru că am avut o mulțime de potrivi pe aici. Dar acestea te va ajuta nu numai, din nou, cu seturi de probleme și informații digestia ați învățat, dar cu siguranta, vin timp test, acestea vor fi incredibil de util. Deci, în primul rând, conspecte. Dacă te duci la cs50.net/lectures și derulați până la săptămâna specifice și a zilei, veți vedea că există note pentru fiecare prelegere, care nu este pur și simplu un transcriere, dar o versiune editată de ceea ce a fost acoperit în curs cu codul fragmente și alte lucruri utile. Am foarte recomandăm merge peste ele. Și apoi, de asemenea, nu există cod sursă disponibil de la fiecare curs. Și din nou, aceste slide-uri vor fi, de asemenea, disponibil online la cs50.net/sections în această seară. Deci, în al doilea rând sunt pantaloni scurți în fiecare săptămână că subiecte de acoperire, de obicei, 5-15 minute în lungime. Și cei care sperăm că vă va oferi un mare primer pe diferite teme. În al treilea rând - iar acest lucru este de brand nou acest an - este study.cs50.net. Dacă nu ați verificat, am foarte recomandăm să faceți acest lucru. Ai de a alege un subiect. Avem zeci de subiecte pe acolo. Deci, de exemplu, alegeți Funcții. Acesta vă oferă câteva diapozitive și notează pe funcții. Cei care sunt de fapt slide-uri care TFS sunt încurajați să folosească în timpul nostru prezentări în secțiune. Există, de asemenea, sfaturi și trucuri pentru a face cu funcții, și nu e probleme practice care ajută lucrați cu funcții. Se asemenea, va dau link-uri la scurt pe funcții și orele care funcționează au venit în curs. , Marca așa study.cs50.net nou acest an, o resursă fantastic. Apoi, am om, care este manualul comandă pe care le puteți rula de la linie de comandă. Deci, dacă aveți orice întrebări cu privire la o comandă, de exemplu, rand, pe care noi întâlnit săptămâna trecută în timpul secțiune și le-ați întâlnit, probabil, în problema ta setat atunci când merge prin genera cod, dar dacă tastați om rand, veți obține pagina care vă spune totul despre rand. Acesta vă oferă ceea ce este nevoie, parametrii pe care le ia, precum și retur tip și o scurtă descriere de această funcție. Deci, a verifica afară rand. Acesta poate fi un pic prolix și confuz, astfel încât, uneori mi se pare că pur și simplu cu Google ceea ce vreau să știu este cel mai bun mod de a găsi răspunsul. Deci, practica cu Google. Ia bun de la Google. Acesta va deveni cel mai bun prieten. La fel de bine ca și Google, în cazul în care nu se poate găsi pe Google, cs50.net/discuss, e forumul de discuții. Sanse sunt, dacă aveți o întrebare, una de dvs. 700 + colegii are, de asemenea, că întrebare și poate fi solicitat o deja în discuta forumuri și l-au răspuns. Deci, dacă aveți o întrebare comună sau aveți o întrebare care credeți că Poate că alte persoane ar fi putut rula în, a verifica afară cs50.net/discuss. În cele din urmă, ultimele două, dacă doriți să vorbesc cu o ființă umană reală, birou ore de luni până vineri. Există, de asemenea ore Office Online pentru elevii de extindere. Și ultimul, dar cu siguranță nu în ultimul rând, mine, semn de exclamare. Toți aveți informațiile mele de contact. Dacă ai nevoie de ceva, te rog nu ezitati sa ma contactati. Simt mereu liber să facă acest lucru. Foarte puțini dintre voi m-au adăugat în Gchat, astfel încât a fost dezamăgitor, dar sperăm că se va schimba între aceasta și secțiunea următoare. Orice întrebări până acum asupra resurselor? Mare. În cele din urmă, o altă mufă pentru feedback-ul, sayat.me/cs50. Poți să-mi dai feedback-ul anonim despre cum fac. Asta a fost foarte util săptămâna trecută. Am o pereche de comentarii de la voi imediat după secțiune, plus de la alți studenți care l-au vizionat în timpul săptămânii, și ea a fost incredibil de util. Am de gând să încerc și să limiteze utilizarea mea de cuvântul "dulce", dar voi arăta mea entuziasm și emoție în alte moduri. Dar au existat alte suplimentare feedback de fond, atât plusuri si delta. Asa ca te rog, eu voi da un feedback pe seturi de probleme. Simțiți-vă liber să-mi dea un feedback pe de predare mea. Sunt aici pentru voi. Mare. Asta e tot ce am pentru prima secțiune. Are cineva vreo întrebări până acum? Și am o notă de centrul de control. Elevii de extindere m-au trimis SMS spunând că nu vei primi nici un audio, dar că este în afara de puterea mea pentru a remedia. Deci, sperăm, care devine rezolvate în scurt timp. Dacă te uiți on-line, hi, dar tu nu mă poți auzi. Deci, în primul rând, vom pentru a merge prin GDB. GDB, așa cum am făcut aluzie la mai devreme, este un instrument de depanare mult mai bine decât printf. Deci, pentru a începe cu GDB, voi, dacă Vrei pentru a deschide aparatul și să ia fișierul pe care eu prin e-mail la tine mai devreme - acest fișier va fi, de asemenea, disponibil on-line într-un pic - și a alerga GDB. / numele fișierului. În primul rând, desigur, trebuie să compilați fișier deoarece GDB funcționează numai pe fișierele executabile. Dar, dacă vrei vreodată să începeți GDB, primul lucru pe care îl face, tu a alerga GDB. / Caesar. Deci asta e numele programului suntem O să merg cu ea chiar acum. Așa că am de gând să scrie face Cezar, care va da-mi un fișier executabil aici a subliniat în verde. Și apoi am de gând să ruleze GDB. / Cesar. Și acolo te duci. Veți vedea, avem un text mi-a spus despre versiunea de GDB, să-mi dea unele informații de garanție, și apoi ne-am au prompt PIB, ceea ce pare un fel a cum ar fi linia prompte nostru de comandă, dar veți vedea că e deschis paren, GDB, paren apropiate. Înainte de a continua și de depanare acest fișier pe care l-am trimis la voi toți, să ne uităm la unele comenzi utile așa că avem un sens de ceea ce vom acoperi. Aceste comenzi sunt enumerate aici, în ordinea în care eu, în general, le folosesc. Așa că am început programul meu de funcționare GBD. / Numele programului, în acest caz, Cezar. Și atunci primul lucru pe care eu 99,9% din timp este de tip break medie. Care stabilește un punct de pauză la principal. În esență, ce faci acolo este programul se va opri la principal astfel încât să puteți începe examinarea-l linie de linie, mai degrabă decât de funcționare toate drumul prin. Puteți rupe la diferite puncte în codul dvs., dar principal este, în general, o loc bun pentru a începe. Urmatoarea comanda am rulat este a alerga. Care începe programul în execuție, și în cazul în care aveți nevoie pentru a intra în linia de comandă argumente, executați-l că comanda. Rulați cu argumentele. Deci, din moment ce suntem de gând pe o versiune de C, care este programul de voi a scris pentru PSET două - aceasta, desigur, are unele bug-uri în ea, care sperăm că vom găsi - vom rula rula cu unele comenzi argumente în linia pentru că Cezar, ca voi stiti pe problema set spec., nevoie de ceva argumente în linia de comandă. Următoarele două comenzi, următorul unul este, de fapt numit viitor. Pe care o ia te linie cu linie prin intermediul programului dumneavoastră. Deci, lovind n apoi Enter te duce la linia următoare, executarea linia anterioară. Pas nu numai că va duce la următoarea linie, dar te duce funcții în interiorul. Deci, dacă ați scris o funcție în codul sau dacă doriți să explorați o la i, de exemplu, puteți lovi s, și mai degrabă decât a merge la următoarea linie de fișierul pe care ai de gând prin chiar acum, veți pas de fapt, în această funcție și a vedea codul său. Lista vă arată, în foarte ușor de utilizat format, de 10 sau cam asa ceva liniile din jurul în cazul în care în prezent sunt în codul dvs. astfel încât să puteți vedea de fapt fișierul mai degrabă decât a fi nevoie pentru a schimba înapoi și mai departe între puncte de vedere diferite. Imprimare este ca printf, cum sugerează și numele său. Care vă arată ceea ce este egal cu o variabilă. Localnici informații este foarte util. Aceasta este o versiune specială de imprimare. Localnici informații vă arată tot de la nivel local variabile, le imprimă pentru tine , care sunt disponibile în prezent. Așa că, în general, mai degrabă decât a fi nevoie să imprima cele patru variabile pe care eu sunt curios despre dacă sunt într-o buclă, pentru de exemplu, doar scriu info localnici, și o să-mi ce contra mea i arate este egal, ca și matrice care sunt de lucru la egal la egal. În cele din urmă, să continue. Tastarea pauză te oprește la punctul de pauză. Te poti plimba prin linie de conformitate cu următorul și pas. Continua rulează programul pentru următoarea rupe punct sau până la finalizarea în cazul în care nu există mai multe puncte de pauză. Dezactivați elimină puncte de pauză, dacă a decis pauza la principal a fost nepotrivit, pe care doriți să a pus-o în altă parte. Și, în sfârșit q, renunțe, iese din GDB. Deci acest program,. / Cezar, vom să se uite prin chiar acum și ne-am sunt de gând să folosească GDB pentru a găsi bug-uri în acest program. Am fugit acest program mai devreme cu Verificați 50, și am o încruntare. Tot ceea ce a existat, ea compilat, ea a trecut o mulțime de teste, dar pentru din anumite motive, ea nu a trecut de-a cincea de testare, de cotitură BARFOO, toate capacele, în E-D-U-I-R-R, majuscule, folosind trei ca o cheie. Am destul de aproape. Am vorbit cu o literă. Deci, există unele mica greseala aici. M-am uitat prin codul meu. Nu am putut da seama. Să sperăm că, voi mă poate ajuta dau seama ce acest bug este. Deci, asta e eroarea suntem căutați. Să se mute în GDB. Din nou, am alerga GDB. / Cezar, așa că acum suntem în GDB. Și ceea ce este primul lucru ar trebui să fac? Tocmai am intrat GDB. Cineva să-mi dea un bun comandă pentru a intra. STUDENT: Break principal. JASON Hirschhorn: Break principal. Fantastic. Să tastăm că inch Voi puteti viziona aici sau urmați de-a lungul pe computere. Break principal, și veți vedea o punct de pauză a fost stabilit la - dă-mi o adresa de memorie ciudat, și, de asemenea, dă-mi numărul liniei. Dacă ar fi să se uite din nou la acest fișier, Mi-ar da seama că principala sa întâmplat pe linia 21. Ce ar trebui să ruleze în continuare? Este programul meu de funcționare? Nu. Deci, ce ar trebui să ruleze în continuare? STUDENT: Run. JASON Hirschhorn: Run. Ar trebui să I a alerga doar alerga, sau ar trebui să Am adăuga alte lucruri in? STUDENT: Rulați cu argumentul. JASON Hirschhorn: A alerga cu argumentele de comandă. Și, din moment ce eu sunt de depanare un foarte specific caz, eu ar trebui să intre că argument linie de comandă. Deci, voi alerga trei, care este, din nou, de ieșire am primit de la Verificare 50. Programul de pornire. Trecem printr-o serie de linii. , Veți vedea acum că suntem pe linia 21. Cum știu că suntem pe linia 21? Pentru că, dacă te uiți la stânga de fereastra mea terminale, acolo se spune linia 21. Și asta îmi dă, de fapt, cod care este la linia 21. Așa că am misspoke mai devreme. Principal nu este, de fapt, la linia 21. Principal este o pereche de linii de mai sus 21. Dar la linia 21, care este unde suntem de rupere. Această linie de cod are Nu încă executat. Asta e important. Linia ce vezi nu are a fost executat încă. Asta e următoarea linie de cod esti pe cale de a executa. Deci, următoarea linie, ca voi sunt probabil, familiarizat cu, este aceasta condiție verificare pentru a vedea dacă am intrat într-un argument linie de comandă. Și o la i, ceea ce este de-a doua o parte din care face? Ce este o să am? STUDENT: Schimbarea se la un număr întreg. JASON Hirschhorn: Îmi pare rău? STUDENT: Se schimba argument pentru un întreg. JASON Hirschhorn: Deci, o să i se schimbă arg V1 de la un șir de la un număr întreg. Și atunci ce-o verificare? STUDENT: Dacă există un al doilea argument linie de comandă, la o parte de la rularea programului. JASON Hirschhorn: Și ce-i a doua jumătate a acestui Verificarea expresie boolean? Această parte pe aici, o să am? STUDENT: Dacă e negativ. JASON Hirschhorn: Asigurându-vă că ce? STUDENT: Asigurându-vă că ea este, de fapt, pozitiv. JASON Hirschhorn: Exact. Acest lucru este de verificare pentru a vedea dacă este negativ, iar dacă este negativ, am au o senzație de linia următoare s-ar putea fi-mi striga la utilizator. Deci, hai sa lovit scop de a executa această linie. Noi nu vedem că linia pe care voi poate aștepta pentru a vedea tipa la de utilizator și apoi se întorc, pentru că această linie nu sa executat. Am intrat 3. Așa că am făcut-o, de fapt, intre doua comanda argumente de linie, și 3 este mai mare decât zero. Așa că am văzut că linia, am executat, dar nu am pas în cazul în care starea. Deci, acum, urmatoarea, văd eu setarea cheie int egal o să i arg v1. Astfel că este mine crea o cheie variabilă. Deci, dacă am imprima cheie, chiar acum, pentru că care vă permite să vedeți valoare în variabila, cheie este egal cu 47. Asta-i ciudat, dar, desigur, Asta pentru că nu avem executat linia încă. Deci, acum, dacă n-am lovit, executa acea linie, și de a face cheie de imprimare, cheia va fi egală cu 3, care este ceea ce ne asteptam sa egaleze. Deci, din nou, în GDB, linia pe care Văd că nu s-au executat încă. Trebuie sa lovit n sau s sau un număr de alte comenzi de fapt, executa acea linie. Cheie de imprimare. A-cheie de la 3. Până în prezent, atât de bine. Șir este text simplu. Să execute acea linie. Primesc un șir de la utilizator. Să vedem în mea Plecare 50, I intra BARFOO toate capacele, așa asta e ceea ce voi intra. Dacă acum am imprima text simplu. Veți vedea că este egal cu un șir. Ea dă-mi o altă hexazecimal ciudat număr, dar nu în De fapt spune că șir meu este BARFOO. Dacă aș fi vrut să văd ce-cheie a fost de la acest punct, cum aș putea verifica cheia? STUDENT: tasta Print. JASON Hirschhorn: cheie Print, exact. Și, de fapt, nu există o scurtătură. Dacă v-ați plictisit de dactilografiere de imprimare, aveți posibilitatea să tastați doar p.. Deci, cheia p face exact acelasi lucru. Și din nou, văd că este egal cu 3. Dacă aș fi vrut să aflu ce atât cheie și BARFOO cifrat, în același timp dar am fost obosit de a tasta fiecare unul individual, I ar putea de tip info localnici. Asta îmi dă egali cheie 3. Text simplu este egal BARFOO. De asemenea, dă-mi aceste două lucruri ciudate în partea de sus, această variabilă i și aceasta n variabile. Cei care sunt de fapt existente în programul meu principal. Noi nu le-am întâlnit încă, ci ca o previzualizare, cei există în mea de buclă. Deci, chiar acum, ele egale unele ciudat Numerele pentru că ei nu au fost inițializat încă, dar ele nu există încă în memorie, astfel încât acestea sunt doar setat la o valoare de gunoi. Dar noi nu vedem cheie în câmpie text, chiar acolo. Așa că am de gând să execute această linie, linia 34, pentru bucla. Mergem să sară în pentru buclă prin lovirea n. Și suntem interior pentru buclă. Suntem la prima verificare. Și din nou, acestea ar trebui să arate un fel de familiar pentru tine, pentru că aceasta a fost o Program de Cezar, care a fost scris, dar din nou, are un fel de bug-uri. Și acum, dacă eu fac informații localnicii, pentru că eu sunt în care pentru bucla, veți vedea care i este egală cu zero, așa cum ne așteptăm. Asta e ceea ce am setat la și inițializat se la bucla for. n este egal cu 6. Care face, de asemenea sens, deoarece ne-am stabilit l la strlen de text simplu. Deci, îmi place să fac localnici informații sau de imprimare la variabila de multe ori pentru a vă asigura că totul este întotdeauna ceea ce Mă aștept să egaleze. În acest caz, tot ceea ce este ceea ce mă aștept să egaleze. Deci, haideți să înceapă să se miște prin acest lucru pentru bucla. Linia Sunt pe linie este de 36, în cazul în care campie Textul i este mai mare decât un simplu și Textul i este mai mic sau egal cu z. Știu că problema mea nu este cu primul meu scrisoare, e cu a doua scrisoare. Dacă ne uităm înapoi la check- 50, B merge la E bine. Iau A și lăsându-l ca o O, nu-l schimba la D. Deci, ceva e în neregulă cu a doua scrisoare. Așa că am de gând să se mute acolo într-o secundă. Dar, dacă am vrut să verifice ce simplu text, am egalat în această special caz, cred că ar trebui să fie ce? Ce ar trebui să text simplu să egaleze în acest primul tur de scrutin prin intermediul pentru buclă? STUDENT: Zero? JASON Hirschhorn: Text simplu de I? Deci, ar trebui să fie de capital B. I, desigur, este egală cu zero, dar text simplu Suport zero, suport închis este egal cu B deoarece siruri de caractere, așa cum am văzut săptămâna trecută, sunt matrice, așa că ne apropiem Primul caracter din asta. Deci, din nou, în cazul în care am printat text simplu din Eu, eu, de fapt, pentru a primi caracterul B. Și asta e curat, corect? Nu am de fapt text simplu I. Asta nu e una dintre variabilele I stabilite sau inițializat, dar aveți posibilitatea de a imprima o întreagă serie de lucruri dacă doriți să. Dar să trecem prin. Dacă text simplu I este mai mare decât A și text simplu I este mai mică sau egală cu Z, care în mod clar este adevărat că avem o B. de capital am de gând să ruleze anumite comenzi pe ea. Am văzut că matematica săptămâna trecută, așa că vom ia-o de la sine că funcționează dreptul în conformitate cu Verifică 50. Aceste acolade, prima a aratat ca am fost ieșirea din dacă stare, al doilea a arătat că eu sunt pentru ieșirea din buclă. Iar acum, când am lovit următoare, vom vedea ne-am întors de la bucla din nou. Mergem prin pentru bucla din nou. Să pas de fapt, în cea de a doua repetare a pentru buclă și tipul info localnici. Deci, suntem în cea de a doua iterație de buclă noastre pentru. I este egal cu 1, pe care ne asteptam. N este egal cu 6, pe care ne asteptam. Cheie este egal cu 3, pe care ne asteptam. Și text simplu, veți vedea, este egal cu EARFOO acum, nu mai BARFOO deoarece în iterație nostru anterior, B a fost schimbat la un capital de E. Deci, suntem pe cale de sa se confrunte cu această problemă, astfel încât aceasta este locul unde vom se arunca cu capul în depanare. Dar are cineva are întrebări despre ceea ce am făcut până acum? Fantastic. Deci, suntem pe cale de a executa acest lucru, dacă condiție, suport text simplu am închis suport mai mare decât A și text simplu am mai mic sau egal cu Z. Dar, înainte Mă duc în care, pentru că acest lucru este în cazul în care Știu că eroarea mea este, vreau să subliniez din text de I. Deci, să punem imprima. Face egal cu caracterul A, astfel încât se pare până acum, totul este bine și bun. Așa că am aștepta ca această linie pe logica mea, această linie ar trebui să fie adevărat. Este o scrisoare de capital. Dar dacă am lovit n, ne dăm seama că această linie, în fapt, nu sa executat. Am sărit jos la else if. De ce sa întâmplat asta? STUDENT: Pentru că aveți starea dumneavoastră de text simplu este mai mare decât A, nu este egal sau mai mare. JASON Hirschhorn: Deci, am avut textul simplu I este mai mare decât A, nu mai mare mare sau egal cu. Deci, în mod clar, capitalul A nu a făcut declanșa această condiție în cazul în care, și am făcut nu intra în ea, și am făcut nu face schimbarea necesară. Deci asta e, de fapt. Am dat seama bug mea. Am putea merge înapoi în dosarul meu sursă, schimba-l, și să o actualizați și rulați Verificați 50 din nou. Dar vom vedea, doar pentru pedagogie lui sake, dacă eu continui. Altfel daca nu se executa, fie, dar ceea ce în schimb este egală este comanda care nu se schimbă. Deci, nu sa schimbat deloc, și dacă am imprima text simplu aici, vom vedea merge prin care pentru bucla nu a făcut, de fapt, schimba faptul că al doilea caracter, la toate. Este încă o A. de capital Deci, din nou, ne-am depanat eroare nostru. Ne-am dat seama că nu a fost lipsesc unele logica. Și l-am depanat înainte de timp înainte de a executarea de fapt acea linie, dar v-ar fi observat avut ne-am Următorul lovit și a sări la care altfel dacă, ceea ce înseamnă că, dacă starea nu era adevărat. Noi nu am, de fapt, pentru a primi rezultatul ne-am asteptat. Deci ne-ar fi putut fi determinat, a avut nu am fost atât de abil, să se uite la că în cazul în care starea și verificați dacă, în fapt, starea noastră ar trebui să evalueze în adevărat în contextul actual. Asta e tot pentru depanarea acestui program. Are cineva vreo întrebare? Ce comanda ar putea l-am lovit la demisia GDB? Q. Și apoi se va solicita, renunta oricum? Da sau nu. Voi lovi da, și eu am renuntat GDB. Astfel că a fost un primer rapid pentru GDB. De fapt, într-un scenariu reală, Am făcut acest lucru la ore de birou. Am GDBed acest program exact la orelor de serviciu, cu un student. Și dacă ne întoarcem la comenzile le-am vazut înainte, am folosit pauza principal, în primul rând lucru am făcut. Am folosit rula cu argumente de linie de comandă, al doilea lucru am făcut. Am folosit lângă o mulțime de a muta ne prin linii. Și din nou, versiunea scurtă de este următorul n. Asta e în paranteze în gri pe diapozitiv. Nu am folosit pas, dar nu am făcut-o Trebuie neapărat să pentru acest caz. Dar s-ar putea folosi într-un pic mai târziu pe ziua de azi, dacă suntem de depanare, pentru exemplu, căutare binar când binar căutare este numit într-o separat funcție, dar există unele erori cu ea. Am de gând să vrea să-și intensifice în apelul la binar de căutare și de fapt, o depanare. Lista nu am folosit nici pentru că am avut un bun simt de cod noastre, dar dacă am a vrut pentru a obține un sentiment de cod ceea ce am a fost în jur, am putea folosi doar lista. Imprima am folosit, informații localnici le-am folosit. Continua nu am nevoie pentru a utiliza în acest caz, nu am nevoie pentru a utiliza dezactiva, dar am făcut-o utilizare renuntat. Din nou, aceste 10 de comenzi, le practică. Dacă ați înțeles aceste 10 de comenzi, ar trebui să fie stabilite pentru orice depanare emite cu GDB. Deci, suntem pe cale de a merge mai departe, din nou, la crucial de la punctul de azi, trecând peste acestea sortarea și căutarea algoritmi. Înainte de a face acest lucru, din nou, întrebări, comentarii, preocupări pentru GDB? Deci, toată lumea este de gând să utilizeze GDB, mai degrabă decât printf? Deci, toată lumea, de dragul lui perpetuu, toată lumea este cap drept cap acum, așa că veți vedea la ore de birou și toate TFS vă și veți vedea vor spune, arată-mi cum să utilizați GDB, și veți putea pentru a le arăta, corect? Un fel de? Poate sperăm. Rece. Așa că am de gând să se mute în sortarea și căutarea. Veți vedea Am o listă deja clasificate în funcție pentru noi, dar care nu se întâmplă să fie cazul întotdeauna. Deci, în problema stabilit caietul de sarcini pentru problema stabilit trei, aveți pantaloni scurți pe care le puteți viziona, și este de fapt vă solicită pentru a viziona aceste pantaloni scurți. De asemenea, în curs de săptămâna trecută, ne-am dus peste o mulțime de aceste algoritmi, așa că eu sunt Nu o să-și petreacă timpul în clasa a merge asupra acestor algoritmi din nou sau desen imagini de modul în care acestea algoritmi de lucru. Din nou, aceste informații puteți re-ceas prelegere, sau că informațiile este capturat deosebit pe pantaloni scurți pentru aceste căutări, toate de care sunt disponibile la cs50.net. Deci, în loc, ceea ce am de gând să faceți este să scrie aceste programe. Avem un sens, un model mental, de modul în care lucrează, și deci ceea ce vom să faceți este să le cod pentru adevărat. Vom transforma acest model mental, ca imagine, dacă vreți, în cod real. Și dacă ai fost un pic confuz sau tulbure pe modelul mental, am totul înțelege. Noi nu esti de fapt de gând să salt la codul imediat. Deci, în timp ce această solicitare în acest diapozitiv cere să cod binar de căutare, și de fapt, o versiune iterativ de binar de căutare, primul lucru pe care am Chiar vrei să faci este scrie unele pseudocod. Astfel încât să aveți acest model mental de modul în care funcționează de căutare binar. Ia o foaie de hârtie dacă aveți un ușor disponibile, sau deschide un editor de text, și mi-ar plăcea toată lumea pentru a scrie. Ia patru minute pentru a scrie pseudocod pentru căutare binară. Din nou, gândiți-vă că modelul mental. Voi veni în jurul dacă aveți întrebări și putem trage imaginea afară. Dar, în primul rând, înainte de a începe de programare, Aș vrea să scrie pseudocod pentru binar de căutare astfel încât atunci când ne-am se arunca cu capul în, avem o direcție ca pentru cazul în care ar trebui să ne îndreptăm. STUDENT: Putem presupune gama de Valorile primim este deja sortat? JASON Hirschhorn: Deci, de căutare binară la locul de muncă - întrebare excelentă - vă trebuie să ia într-o sortat matrice de valori. Deci, presupun că va funcționa. Ne vom întoarce la acest diapozitiv. Veți vedea în purpuriu funcția Declarația este bool binary_search int valoare, valori int, int n. Acest lucru ar trebui să arate familiar dacă ați deja abordat sau ajuns dvs. mâinile murdare cu setul de probleme. Dar asta e declarația ta funcție. Din nou, nu este nevoie să vă faceți griji cu privire la atât de mult în acest moment. Ceea ce eu chiar vreau să faceți este să luați Patru minute până la binar pseudocod căutare, iar apoi vom merge peste care ca un grup. Și voi veni în jur. Dacă aveți întrebări, simt liber pentru a ridica mâna. De ce nu luați mai mult de două minute pentru a termina pseudocod? Știu că acest lucru poate părea ridicol că vom petrece atât de mult timp pe ceva ce nici măcar nu e de fapt în C, dar mai ales pentru acestea și mai mult algoritmi de provocatoare și probleme seturi pe care le avem să ne dăm seama, începând din pseudocod nu îngrijorătoare despre sintaxa, doar griji logica, este incredibil de util. Și în acest fel, tu nu esti rezolvarea doi probleme incredibil de dificile, la o dată. Esti doar concentrându-se pe logica, și apoi vă mutați în sintaxa. OK. Să începem prin a merge pseudocod. Am scris aici, binar căutare pseudocod. Vom scrie acest lucru pe bordul împreună. Sau voi scrie și vă voi da mi instrucțiunile de care am nevoie. Deci, poate cineva să-mi dea primul linie de pseudocod te a scris pentru căutare binar? Da, Annie? STUDENT: În timp ce lungimea Lista este mai mare decât zero. JASON Hirschhorn: În timp ce lungime din lista mai mare decât zero. Și din nou, vom vedea unele C-căutarea sintactice lucrurile pe aici. Dar cea mai mare parte acest lucru este în limba engleză. Ai cineva vreo linie au pus înainte de aceasta, în lor de pseudo-cod? STUDENT: Ia-o matrice de sortat numere. JASON Hirschhorn: Ai scris "obține o matrice de numere sortate. "Per declarație funcție, vom trece o serie de numere sortate. STUDENT: [inaudibil]. JASON Hirschhorn: Deci, vom avea asta. Dar, da, dacă nu am avea asta, ne-am ar avea nevoie pentru a sorta gama noastră de numere, pentru că de căutare binară funcționează doar pe tablouri sortate. Deci, în timp ce lungimea de lista este zero, eu sunt de gând să pună în unele acolade pentru a face să arate un pic mai mult ca C. Dar, în același timp, pare să hartă pe o în timp ce bucla, astfel încât în ​​acest timp buclă de ce avem nevoie pentru a face de căutare binar? Cineva care nu mi-a dat un răspunde încă, dar cine a scris asta? STUDENT: Du-te la mijlocul listei. JASON Hirschhorn: Tom. Du-te la mijlocul listei. Și întrebarea follow-up, ceea ce facem o dată suntem la mijloc a listei? STUDENT: face o verificare dacă asta e numărul pe care îl căutați. JASON Hirschhorn: Excelent. Du-te la mijlocul listei și verificați dacă valoarea noastră este acolo - fantastic. Ai cineva au nimic altceva care a fost diferit decât aceasta? Asta-i exact corect. Primul lucru pe care îl facem în căutare binar se merge la mijlocul listei și verificați pentru a vedea dacă valoarea noastră este acolo. Așa că am asuma dacă valoarea noastră este acolo, ce facem? STUDENT: Ne întoarcem la zero [neauzit]. JASON Hirschhorn: Da, în cazul nostru valoare este acolo, l-am găsit. Deci, putem spune un fel, însă acest Funcția este definită, ne spune utilizatorului l-am găsit. Dacă nu este acolo, totuși, că este în cazul în care acest lucru devine dificil. Deci, dacă nu e acolo, cineva care a fost de lucru pe binar de căutare sau are o idee acum, ce facem? STUDENT: Întrebare. JASON Hirschhorn: Da? STUDENT: Este array sortat deja? JASON Hirschhorn: Da, suntem presupunând matrice este deja sortat. STUDENT: Deci, atunci va trebui să verificați dacă valoarea pe care o vedeți este mai mare decât valoarea pe care doriți, puteți muta la mijlocul cealaltă jumătate. JASON Hirschhorn: Deci, în cazul în care mijlocul de lista este mai mare decât ceea ce suntem cauta, atunci facem ce? Ne mutăm unde? STUDENT: Vrei să se mute în jumătate a listei cu un număr mai mic decât că. JASON Hirschhorn: Deci, vom numi stânga. Deci, dacă de mijloc este mai mare, putem căuta jumătatea din stânga a listei. Și apoi de căutare, ceea ce vreau sa spun de căutare? STUDENT: [inaudibil]. JASON Hirschhorn: Mergem la mijloc. Repetăm ​​de fapt, acest lucru. Ne întoarcem prin buclă în timp ce noastre. Îți voi da ultima - altfel, în cazul în care, de mijloc este mai mică decât ceea ce facem, ce facem aici? STUDENT: Du-te la dreapta. JASON Hirschhorn: Caută dreapta. Acest lucru arată bine, dar are pe nimeni ceva care am putea să lipsească sau orice altceva pe care le pune în dumneavoastră pseudo-cod? Deci, aceasta este ceea ce avem până acum. În timp ce lungimea listei este mai mare decât zero, vom merge la mijlocul listei și verificați dacă valoarea noastră este acolo. Dacă la mijloc este mai mare, vom căutare stânga, altfel, dacă la mijloc este mai puțin, vom căuta dreapta. Deci, am avut toți unele familiaritate cu condițiile pe care le folosim în informatică și instrumentele pe care le avem. Dar veți observa deja am fost vorbind în limba engleză, dar am găsit un mulțime de lucruri care păreau să hartă pe instrumente pe care le avem in trusa nostru instrument de codificare. Deci, chiar de la inceput, nu suntem O să codul de fapt încă. Ce vedem aici, în limba engleză, care hărți cu privire la lucruri pe care le poate scrie in C? STUDENT: în timp ce. JASON Hirschhorn: În timp ce. Deci, aceasta în timp ce aici hărți de pe la ce? STUDENT: o buclă în timp. JASON Hirschhorn: o buclă în timp ce? Sau, probabil, mai general, o buclă. Vrem să facem ceva peste si peste. Așa că am de gând să cod o buclă. Și știm deja, pentru că am făcut acest lucru de câteva ori și am au o multime de exemple de acolo, cum de fapt de a scrie acest indice pentru o buclă. Astfel că ar trebui să fie destul de ușor. Noi ar trebui să poată obține că a început destul de repede. Ce altceva mai vedem pe aici? Ce alte structuri sintaxe, lucrurile că suntem familiarizați cu în C, nu-i așa au deja un sentiment de Bazat pe de cuvintele pe care le utilizați? Da, Anna? [Inaudibil] Glumeam. Anna, dă-i drumul. STUDENT: În cazul în care și altceva. JASON Hirschhorn: În cazul în care și altfel - chiar aici. Deci, ce cei care arata ca? STUDENT: O dacă else. JASON Hirschhorn: Da, condiții, nu? Deci, vom avea nevoie, probabil, pentru a scrie unele condiții. Și, din nou, deși poate derutant în primul rând, avem în general un sens acum de cum să scrie condiții și sintaxa pentru condiții. Și dacă nu o facem, ne-am uita în sus sintaxa pentru condiții, cut și paste că, pentru că noi știm au nevoie de o condiție aici. Orice alte lucruri pe care le vedem ca pe harta lucruri pe care ar trebui să le facă în C? Da, Aleha? STUDENT: Acest lucru ar putea fi evident, doar prin a verifica dacă un valoare este egală cu ceva. JASON Hirschhorn: Deci, cum putem verifica și - merge atât de la mijlocul listei și verificați dacă valoarea noastră este acolo? Cum facem asta în C? Care este sintaxa pentru asta? STUDENT: Egal, este egal. JASON Hirschhorn: Egal, este egal. Deci, această verificare este, probabil, va pentru a fi un egali, egali. Deci, vom ști că avem nevoie de undeva. Și, de fapt, doar în scris-o, vom vedea aceste lucruri. Vom avea de a face unele operatori de comparare acolo - fantastic. Deci, este de fapt arata ca, prin și o mare, nu am scris cuvânt de cod C încă. Dar avem modelul mental jos prin prelegeri și aceste pantaloni scurți. Am scris pseudo-cod ca un grup. Și deja, avem 80% în cazul în care nu 90% din ceea ce trebuie să facem. Acum, avem nevoie doar de codul ea, care din nou, este o problema non-trivial pentru a rezolva. Dar cel puțin suntem blocați pe logica. Cel puțin acum, când vom merge la orele de birou, Pot să spun, știu ce am nevoie de a face, dar pot să vă reamintesc mi-a sintaxei? Sau chiar dacă orele de birou sunt aglomerate, te Poate Google pentru sintaxa, mai degrabă decat sa fie blocat pe logica. Și din nou, mai degrabă decât încercarea de a rezolva logica și problemele de sintaxă toate în același timp, este adesea mult mai bine să sparge aceste două probleme grele off în două cele mai ușor de gestionat și de a face pseudo-cod întâi și apoi de cod în C. Deci, haideți să vedem ce am făcut pentru pseudo-cod înainte de timp. În timp ce lungimea listei este mai mare decât zero, uita-te la mijloc listei. Dacă numărul găsit întors adevărat, altfel în cazul în număr mai mare, de căutare din stânga. Altceva în cazul în număr mai mic, căutare drept, intoarce false. Deci, care arata aproape identic în cazul în care nu aproape identic cu ceea ce am scris. De fapt, Tom, ceea ce ați spus în primul rând, rupere mijlocul listei și dacă Numărul de găsit în două declarații este de fapt ceea ce am făcut. Le-am combinat acolo. Ar fi trebuit ascultat tu prima dată. Astfel că este pseudo-codul avem. Dacă doriți să acum, îmi pare rău, du-te înapoi la problema noastră inițială. Să cod binary.c. Astfel încât să pună în aplicare o versiune iterativ de binar de căutare folosind următoarele declarație a funcției. Și nu aveți nevoie pentru a copia l doar încă. Sunt de fapt de gând să deschidă chiar aici binary.c. Astfel încât nu există declarația funcției în mijlocul ecranului. Și veți vedea am luat pseudo-codul de pe laturile mele, dar aproape identic la ceea ce am scris, și pune că în pentru tine. Deci, acum, să ia cinci minute la codul această funcție. Și din nou, dacă aveți întrebări, ridice mâna, să-mi spuneți, voi vină în jurul valorii. STUDENT: [inaudibil]. JASON Hirschhorn: Deci, am luat binar definiție de căutare din partea Sus, pe linia 12. Asta e ceea ce am primit de diapozitiv mea. Și apoi toate aceste pseudo-cod am doar copiați și lipite de diapozitiv, pseudo-cod diapozitiv. Încă nu aud [neauzit]. Deci, dacă ați terminat dvs. punerea în aplicare, vreau să-l verifice. Te-am trimis dosarul helpers.h mai devreme în această clasă. Și acesta va fi disponibil on-line, precum și pentru a descărca de oameni uitam de data aceasta secțiune întârziat. Și am folosit doar de distribuție generic Codul de pset3. Așa că am luat find.C, folosiți fișierul meu helpers.h nu direct fișierul helpers.h care a dat în codul de distribuție. Și am avut de a face o altă schimbare în find.C, mai degrabă decât de asteptare pur și simplu căutare, apel binary_search. Deci, dacă doriți să testați codul dumneavoastră, știu că este cum se face. De fapt, atunci când vom fi difuzate acest cod chiar acum, am făcut o copie de directorul meu pset3, din nou, schimbate fișierele asistenți și apoi a făcut ca schimba în find.C pentru a apela binary_search mai degrabă decât pur și simplu de căutare. JASON Hirschhorn: Da. Aveți o întrebare? STUDENT: Nevermind. JASON Hirschhorn: Nu vă faceți griji. Ei bine, hai să începem. Vom codifica aceasta ca un grup. O altă notă. Din nou, acest lucru este, poate fi ușor schimbate in pentru problema Set Trei. Am dosarul meu helpers.h care, mai degrabă decât helpers.h suntem dat, declară căutare binară, cu bule sortare, și selecție de sortare. Și în find.c veți observa pe linie, ceea ce este că, linia 68, numim binar căutare, mai degrabă decât de căutare. Deci, din nou, cod care este disponibil on-line sau codul care sunteți crearea de acum pot fi ușor schimbate in pentru p set 3 pentru a verifica. Dar, în primul rând, haideți să cod binar de căutare. Declarația noastră funcție, ne întoarcem un bool. Luăm un întreg numit valoare. Ne ia o serie de numere întregi numite valori, și vom lua n fi dimensiunea matricii. Pe linia 10, chiar aici, am ascuțite includ stdbool.h. Stie cineva de ce e acolo? Deci, ce are ca linie de cod fac? STUDENT: Acesta vă permite să folosesc un tip de revenire bool. JASON Hirschhorn: Exact. STUDENT: Sau este o bibliotecă care permite de a utiliza un tip de revenire bool. JASON Hirschhorn: Deci includ Sharp linie stdbool.h dă-mi ceva definiții și declarații de lucruri că eu am voie să folosească în această bibliotecă. Astfel printre cei se spune că nu există acest tip numit bool, și poate fi adevărat sau fals. Deci, asta e ceea ce face acea linie. Și dacă nu am avea acea linie, mi-ar avea probleme de scris acest cuvânt aici, bool, chiar acolo. Exact dreapta. Așa că am nevoie ca în acest cod. OK. Deci, acest, din nou, este o iterativ versiune, nu unul recursiv. Așa că haideți să ne începem. Să începem cu prima linie de cod pseudo. Și sperăm că, vom - sau nu sperăm. Vom merge în jurul camerei. Vom merge linie cu linie, iar eu te voi ajuta îți dai seama de linia de care avem nevoie pentru a scrie primul. Deci, în timp ce lungimea de liste este mai mare decât zero. Să începem de la partea din față. Ce linie ar trebui să scriu aici, în cod? STUDENT: În timp ce paranteză n este mai mare decât 0. JASON Hirschhorn: în timp ce n este mare decât 0. Deci, n este dimensiunea unei liste, și vom verifica dacă - [VOCI interpune] JASON Hirschhorn: - îmi pare rău? STUDENT: Cum știm că n este dimensiunea listei? JASON Hirschhorn: Îmi pare rău. Pe caietul de sarcini PSET, căutarea și un fel funcționează aveți nevoie pentru a scrie, n este mărimea listei. Am uitat să explice că aici. Dar da. n este dimensiunea lista, în acest caz. Deci, în timp ce n este mai mare decât 0. OK. Care se poate dovedi un pic problematic deși, dacă lucrurile merg mai departe. Pentru că vom continua să cunoască Dimensiunea listei parcursul acestui funcție, dar spun că începe cu o serie de 5 numere întregi. Și ne-am trece prin și ne-am acum redus la o serie de 2 numere întregi. Care 2 numere întregi este asta? Dimensiunea este de 2 acum că vrem să uita-te la, dar care 2 este asta? Asta face sens, această întrebare? OK. O să-l întreb din nou. Așa că am începe cu această matrice de 5 numere întregi, iar n este egal cu 5, corect? Vom alerga pe aici. ne vom schimba, probabil, dimensiunea, drept, ca lucrurile merg mai departe. Care este ceea ce spunem ce vrem să facem. Noi nu doriți să căutați un lucru complet nou. Deci, spune-am schimba la 2. Ne ia jumatate din lista asta e ciudat. Deci, alege doar 2. Deci, acum, n este egal cu 2. Îmi cer scuze pentru cei săraci markere uscate. Corect? Și suntem în căutare prin lista de din nou, cu o listă de dimensiune 2. Ei bine, gama noastră este încă de dimensiune 5. Noi spunem vrem doar să căutare 2 locuri în ea. Deci, care sunt cele 2 spoturi? Asta face sens? Sunt stânga 2 locuri? Sunt cele mai potrivite 2 locuri? Sunt cele de mijloc 2 locuri? Ne-am rupt în jos problema, dar ne-am de fapt, nu stiu care parte a problema suntem încă în căutarea la, doar de a avea aceste două variabile. Deci, avem nevoie de un pic mai mult, atunci, în timp ce n este mai mare decât 0. Trebuie să știm unde n este în gama noastră actuală. Deci, are cineva o schimba această linie? Cele mai multe din această linie este perfect corect. Este acolo un alt plus? Putem schimba ceva pentru n la face această linie un pic mai bine? Mm-hm? STUDENT: Poți să inițializa o variabilă cum ar fi lungimea de n care va fi folosit apoi mai târziu, în funcție? JASON Hirschhorn: Deci inițializa o lungime variabilă la n, și vom folosi mai târziu? Dar apoi ne-am actualizat doar lungime si ne-am încă rula în această problemă în cazul în care ne-am reduce durata de problema noastră, dar nu știm unde, de fapt, că lungimea hărți pe. STUDENT: Nu este asta o să se întâmple mai târziu, când spui, căutare stânga, search corect? Ai de gând să meargă la un alt domeniu de al tău - JASON Hirschhorn: Vom merge într-o zonă, dar cum știm care sunt pentru a merge la? Dacă avem doar matrice și acest n, cum nu știm de unde să du-te la matrice. În partea din spate, da? STUDENT: Ai, cum ar fi, o mai mică legat și o variabilă limită superioară sau ceva de genul asta? JASON Hirschhorn: OK. Deci, aceasta este o altă idee. , Mai degrabă decât păstrarea doar evidența dimensiune, am urmări de jos și variabilă limită superioară. Deci, cum putem calcula dimensiunea de o limită inferioară și limita superioară? [VOCI interpune] JASON Hirschhorn: Scădere. Și, de asemenea, urmărirea cea mai mică legat și limita superioară pentru a ne anunța, suntem în căutarea aceste două? Suntem în căutarea cei doi aici? Suntem în căutarea de mijloc doi? Probabil că nu de mijloc două, pentru că aceasta, de fapt, este binar de căutare. Dar acum vom fi capabili de a obține dimensiunea, dar și limitele matrice. În esență, dacă ne-am gigant nostru carte de telefon, îl rupe în două. Acum știm unde mai mici carte de telefon este. Dar noi nu suntem de fapt extragerea cartea de telefon în jumătate. Noi încă mai trebuie să știe unde noi limite de problema noastră este. Are cineva intrebari despre asta? Da? STUDENT: ar lucra prin crearea unui variabilă, i, pe care le apoi doar schimbare poziția relativă a acestuia i poziția curentă, și lungime, n? JASON Hirschhorn: Și ce este i? STUDENT: Cum am fi ca un fel de - Ca și cum ar inițializa i să fie poziție de mijloc de matrice. Și apoi, în cazul în care valoarea de la poziția i în mijlocul de matrice în constatat să fie mai mică decât valoarea de care aveți nevoie, i acum devine lungimea unui array, plus valoarea i împărțit la 2. Ca, vezi, tu schimba i - JASON Hirschhorn: Corect. STUDENT: - până la - JASON Hirschhorn: Deci, eu sunt aproape pozitiv care va lucra. Dar punct fiind, ai nevoie de două bucăți de informații aici. Poti sa o faci cu început și sfârșit, sau o poti face cu o dimensiune, și apoi unele marcator. Dar aveți nevoie de două bucăți de informații aici. Nu puteți obține de la doar unul. Asta are sens? Așa că am de gând să treacă prin, și vom face [inaudibil] și de a crea unele markeri. Deci, ce-ai scrie în codul dvs.? STUDENT: Am spus doar int legat unul este egal cu 0. JASON Hirschhorn: Să numim că Int, începând. STUDENT: OK. JASON Hirschhorn: Asta face mai mult sens pentru mine. Și? STUDENT: I-am spus, cred, int se încheie. JASON Hirschhorn: int se încheie. STUDENT: Cred că, n minus 1, sau ceva de genul asta. Cum ar fi, ultimul element. JASON Hirschhorn: Deci tu ai scris, int început este egal cu 0, punct și virgulă, și int final este egal cu n minus 1 punct și virgulă. Deci, în esență, ceea ce facem noi aici, 0 prima poziție. Și, după cum știm, în tablouri, ei nu merg până la n, ei merg până la n minus 1. Deci avem niște limite de matrice noastre. Și aceste limite initiale se întâmplă să fie limitele inițiale ale problemei noastre. OK. Așa că sună bine. Apoi, dacă ne întoarcem la această linie, în timp ce Lungimea de liste este mai mare decât 0, ce, în loc de n, ar trebui am pus aici? STUDENT: Scrie încheie minus început. JASON Hirschhorn: În timp ce se încheie minus începând este mai mare decât 0? OK. Și am putea, dacă am vrut să face că un pic mai frumos, ceea ce altceva am putea face? Dacă ne-am dorit pentru a curăța acest cod un pic? Cum putem scapa de 0? Aceasta este doar o chestiune de stil. Este corect acum. STUDENT: Ending nu egal început? JASON Hirschhorn: Putem face ce? [VOCI interpune] STUDENT: Terminarea este mai mare? JASON Hirschhorn: Da. Putem face doar în timp ce se încheie este mai mare de început. Corect. Am adăugat început pe partea cealaltă de care, și am scăpat de 0. Deci, acest lucru doar arată o puțin curat bit. OK. Deci, în timp ce lungimea de listă este de 0, am scris că, în timp ce se încheie este mai mare decât începutul. Vom pune în necesar nostru acolade, iar apoi primul lucru vrem să facem este să privim la le într-o listă mică. Tu? Poți să-mi dai - STUDENT: Dacă paranteză paranteză valoare - JASON Hirschhorn: Dacă paranteze paranteză valoare. STUDENT: Terminarea împărțit la 2. JASON Hirschhorn: Terminarea? STUDENT: Eu văd o problemă cu al tău - JASON Hirschhorn: OK. Ei bine, uita-te la mijloc. Cum știm ce mijloc este? Da. Deci, lasă-mă să ștergeți acest cod. Cum știm ce mijloc este? În ceva, atunci când ai început și sfârșitul, cum a face tu găsi la mijloc? STUDENT: Ai medie. STUDENT: Tu le adăugați împreună și apoi - JASON Hirschhorn: Adăugați-le împreună și apoi? STUDENT: Și tu medie. Împărțiți-l de 2. JASON Hirschhorn: Adăugați-le împreună și se împarte la 2. Astfel de mijloc Int egal? Tom, puteți să-l dai la mine? STUDENT: Începând plus se încheie - JASON Hirschhorn: Începutul plus se încheie. STUDENT: Toate, suport, împărțit la 2. JASON Hirschhorn: Toate, în paranteze, împărțit la 2. Așa că îmi dă mijloc de nimic, corect? STUDENT: De asemenea, trebuie să-l adune. JASON Hirschhorn: Ce te Adică, am nevoie pentru a rotunji? [VOCI interpune] STUDENT: Pentru că dacă e un ciudat număr, atunci e ca si cum - JASON Hirschhorn: Ei bine, OK. Așa că am putea rotunji. Dar dacă e un număr impar, un 5, pot luând o distanță de mijloc. Sau dacă este un număr par, mai degrabă, că e un caz mai bine. Dacă e 4, avem doar 4, eu pot lua primul "mijloc", citat, citatul sau de-a doua "de mijloc" o. Fie ar lucra pentru o căutare binară, asa ca nu au nevoie de fapt să-l rotunjească. Dar există un alt lucru pe care îl trebuie să se uite la această linie. Nu am putea-l dau seama încă, dar vom reveni la ea. Deoarece această linie de fapt încă are nevoie de un alt lucru. Dar, până acum, am scris patru linii de cod. Avem începutul nostru și se termină markeri. Avem bucla nostru în timp ce, care hărți pe direct pseudocod nostru. Ne uitam la mijloc care harti direct pe pseudocod nostru. Aș spune că acest lucru duce la mijloc listei, această linie de cod. Și apoi, odată ce vom merge la mijlocul lista, urmatorul lucru ce trebuie să facem se verifică dacă valoarea noastră este acolo pentru pseudocod am scris mai devreme. Deci, cum putem verifica dacă valoarea noastră este la mijlocul listei? Te. De ce nu faci asta? STUDENT: În cazul în care valoarea noastră este la mijloc este egal cu indiferent de ne-am stabilit - Adică egal egal - JASON Hirschhorn: A - OK. STUDENT: Eu nu sunt sigur ce variabilă căutăm pentru că, deși, este că - [VOCI interpune] STUDENT: [inaudibil]. JASON Hirschhorn: Exact. Pe declarația funcției, suntem în căutarea pentru o valoare. Deci, suntem în căutarea pentru o valoare într-o matrice de valori. Deci, tu ești exact dreptate. Vă va face, în cazul în care suportul valoare paren deschis mediu închis egal suport este egal cu valoare, și în interior Ce trebuie să facem? În cazul în care valoarea noastră de acolo, ceea ce Nu trebuie să facem? [VOCI interpune] STUDENT: Reveniți la zero. JASON Hirschhorn: Înapoi adevărat. STUDENT: Înapoi adevărat. JASON Hirschhorn: Michael, ceea ce face această linie fac? STUDENT: [inaudibil] programul a rula Desigur sale, și că este de peste, și ai ceea ce trebuie să faci? JASON Hirschhorn: Programul sau ce? În acest caz? STUDENT: Funcția. JASON Hirschhorn: Funcția. Și astfel, să se întoarcă la ceea ce numește l si da-l la valoarea, adevărat. Exact dreapta. Principal. Care este tipul de retur de principal, Michael? STUDENT: Int, întreg? JASON Hirschhorn: int, exact. Un întreg. Asta a fost doar o chestiune de a se asigura voi au fost pe partea de sus a acesteia. Ce nu-l întoarce, de obicei, în cazul în care toate lucrurile sunt de lucru bine? STUDENT: Zero. JASON Hirschhorn: Zero. Exact dreapta. STUDENT: În cazul în care acest lucru revine doar adevărat, nu există nici o informație fiind dat despre ceea ce - Oh, acest lucru este pur și simplu spune că Valoarea este în interiorul matricei. JASON Hirschhorn: Exact. Acest program nu este furnizarea de informații de unde valoarea este. Este doar spune, da, am găsit ea, sau nu, nu l-am găsit. Deci, dacă numărul găsit, return true. Ei bine, de fapt, ne-am făcut-o într-adevăr rapid cu o linie de cod. Deci, voi muta acea linie de pseudocod. STUDENT: Nu avem nevoie de pentru a schimba matrice? Ar trebui să fie valori, nu de valoare, nu? JASON Hirschhorn: Îmi pare rău. Mulțumesc. STUDENT: Da. JASON Hirschhorn: Această linie ar fi valori. Exact dreapta. OK. Deci, ne-am uitat la lista de mijloc. Dacă numărul găsit return true. Continuând cu pseudocod noastră, în cazul în care de mijloc este mai mare, de căutare a plecat. Deci, am avut aici, în cazul în care numărul de mai mare, de căutare a plecat. Constantin, pot da mi această linie de cod? STUDENT: În cazul în care valoarea de mijloc - JASON Hirschhorn: Deci, dacă valoarea - dacă paren deschis valori suport suport aproape de mijloc - STUDENT: Este mai mic decât valoarea? JASON Hirschhorn: Este mai puțin. STUDENT: Mai puțin de valoare. JASON Hirschhorn: Valoare. Ei bine, de fapt, pe care doriți să verificați dacă numărul - Scuze. Acesta este un pic confuz. Dar altfel dacă numărul în mijloc de listă este mai mare. STUDENT: Oh, OK. JASON Hirschhorn: Voi schimba asta. Altfel, dacă mijloc este mai mare, ne-am doriți să căutați stânga, OK? Și ce facem în interiorul dacă această condiție? STUDENT: Pot face o mică schimbare a condiție, schimba-l la altcineva dacă? JASON Hirschhorn: Altele dacă? OK. Deci, acest cod va executa aproximativ la fel. Dar un lucru frumos despre utilizarea în cazul în care, altfel în cazul în care, altfel, dacă sau în cazul în care, altfel, dacă, altfel înseamnă că doar unul dintre cei care va trebuie verificat, nu toate trei, potențial. Și că o face un pic mai frumos pe computer care este care rulează programul. Deci [? Constantin,?] noi suntem în interiorul această linie, altfel dacă valorile, Suport de mijloc suport aproape este mai mare decât valoarea. Ce trebuie să facem? Avem nevoie pentru a căuta în stânga. Cum facem asta? Am de gând să vă dau un început. Avem aceste două lucruri numite începe și se termină. Deci, ce trebuie să se întâmple la început? Dacă doriți să căutați în stânga lista, vom ajunge începutul noastră actuală. Ce avem nevoie pentru a face acest lucru? STUDENT: Am stabilit la început la mijloc plus 1. JASON Hirschhorn: Deci, dacă suntem căutarea stânga? STUDENT: Ne pare rău, minus de mijloc - astfel se încheie ar fi de mijloc minus 1 și început - JASON Hirschhorn: Și ce se întâmplă de la început? STUDENT: Acesta rămâne aceeași. JASON Hirschhorn: Deci, semnificație rămâne aceeași. Dacă suntem în căutarea stânga, suntem utilizând același început - exact dreapta. Și se termină? Ne pare rău, ceea ce face se încheie egal din nou? STUDENT: minus Middle 1. JASON Hirschhorn: minus Middle 1. Acum, de ce minus 1, nu doar de mijloc? STUDENT: mijloc este în afara imagine deja, pentru că am avut verificat că e afară? JASON Hirschhorn: Asta-i exact dreapta. Mijlocul este din imagine. Am verificat deja la mijloc. Deci, noi nu vrem "la mijloc", citat citatul, să continue să fie în matrice care le căutați. Deci, acest lucru este fantastic. Altfel, dacă valorile de suport de mijloc este mai mare decât valoarea care se încheie la egal la egal minus mijloc 1. Jeff, ce zici de asta ultimul rând? STUDENT: Else. Valorile de mijloc este mai mică decât valoarea? JASON Hirschhorn: Vom tu-mi dai altceva. Deci, dacă nu-mi dai - STUDENT: Deci, apoi începe ar fi plus de mijloc 1. JASON Hirschhorn: egali Început plus mijlociu 1, din nou, pentru același motiv pentru care Constantin ne-a dat mai devreme. Și la sfârșitul anului, care nu a dat mi-o linie de cod încă? Return false, Aleha, ceea ce nu vom scrie aici? STUDENT: Înapoi false. JASON Hirschhorn: Înapoi false. Și trebuie să facem asta, pentru că dacă noi nu-l găsesc, trebuie să spunem nu l-am găsit. Iar noi am spus că vom reveni un bool, așa că am avea cu siguranta pentru a reveni o undeva bool. Deci, haideți să ruleze acest cod. Sunt de fapt de gând să - deci suntem în terminal. Vom șterge fereastra noastră. Să-mi fac totul. Am găsit acolo este o eroare. Există o eroare pe linia 15, așteptat virgulă la sfârșitul declarație. Deci, ceea ce am uitat? STUDENT: Punct și virgulă. JASON Hirschhorn: Punct și virgulă chiar aici. Cred că a fost cod lui Tom. Deci, Tom, [neauzit]. Glumeam. Să nu-mi fac totul din nou. STUDENT: directorul Ce Dropbox ar trebui să fim în acest? JASON Hirschhorn: Deci, aveți posibilitatea să ceas doar pentru acest bit. Dar, din nou, în cazul în care ai vrut să se mute acest cod în directorul dvs. pset3 pentru a încerca l, asta e ceea ce am făcut. Dacă veți observa aici - îmi pare rău, bine întrebare. [? LS,?] Am aici codul find.c din Codul de distribuție din această săptămână. Am helpers.h. Am un fișier Marca pe care am de fapt, editat un pic pentru a include aceste noi fișierele suntem scris. Tot din acest cod va fi disponibil, nu Codul de distribuție, dar noua Face dosar, noul fișier va helpers.h fi disponibil on-line pentru descărcare. Din nou, astfel încât cei care sunt Codurile suplimentare avem. Deci, asigurați-toate, pe această linie, face găsi, binar, selecție bule - mărci toate trei dintre ele și compilează în acest cod găsi executabil. Deci, în general, nu vrem la drept la check50. Vrem să facem niște teste pe cont propriu. Dar doar astfel încât să putem accelera acest lucru un pic, check50 2013 pset3.find va trece in-helpers.c - rea mea. Nu am acest drept acum. Așa că de fapt de gând să rula cod de reală. Usage.find /, tu știi ce înseamnă asta? STUDENT: Ai nevoie de un al doilea linie de comandă pe ea. JASON Hirschhorn: Am nevoie de o linie de comandă al doilea. Și pe caietul de sarcini, am nevoie pentru a intra în ceea ce căutăm. Așa că haideți să ne uităm la 42. O să-l păstrați în sortat, pentru că noi nu s-au scris o funcție de sortare încă - 42, 43, 44. Și de control D nu a găsit acul în carul cu fân. Asta-i rău. Este cu siguranta acolo. Să încercăm altceva. Poate pentru că am pus ea la început. Să facem 41, 42, 43. Acolo mergem. L-am găsit. Să-l punem la finele acum, doar astfel încât să putem fi aprofundată - 40, 41, 42. Nu a găsit acul. Așa că am menționat asta mai devreme. Din păcate, am știut acest lucru a fost de gând să se întâmple. Dar pentru scopuri pedagogice, e bine să-l exploreze. Ea nu funcționează. Pentru unii motiv, nu se poate găsi. Noi știm ce e acolo, dar noi nu sunt o constatare. Deci, un lucru pe care îl putea face este să mergeți prin GDB să-l găsească, dar nu oricine, fără a trece prin GDB, au o sentiment de unde ne-am dat-o? [? Madu? ?] STUDENT: Cred că aceasta ar putea fi atunci când se încheie este egal cu începutul, și este doar o listă-un singur element. Atunci se ignoră în schimb de fapt verificare. JASON Hirschhorn: Asta-i exact dreapta. Când se încheie egal început, nu-i așa încă un element în lista noastră? STUDENT: Da. JASON Hirschhorn: Da, de fapt, ne-am au unul și numai un singur element. Și că se va întâmpla, cel mai probabil, atunci când, pe codul de testat de noi, suntem la față de carul cu fân sau la sfârșitul carul. Asta în cazul început și final este de gând să egal unul, cu binar de căutare. Deci, în aceste două cazuri nu au de lucru, pentru că se încheie a fost egal cu începutul. Dar în cazul în care se încheie este egal cu începutul, se executa această buclă în timp ce? Nu are. Și am putea fi verificat care din nou prin GDB. Deci, cum putem rezolva acest cod, deoarece atunci când în timp ce se încheie este egală cu început, ne-am dori, de asemenea, acest în timp ce bucla pentru a rula. Deci, ce putem face fix la linia de 18? STUDENT: [inaudibil] este mai mare mare sau egal cu. JASON Hirschhorn: Exact dreapta. În timp ce se încheie este mai mare decât sau egal cu începutul. Deci, acum, ne asigurați-vă că pentru a obține caz colț la sfârșitul anului. Și să vedem. Să facem asta de mai mult timp. Să facem tot. Din nou, va trebui să doar urmați de-a lungul aici. Găsi 41 de această dată. Doar păstrați-l consistent. Găsi 42. Să-l punem la început - 42, 43, 44. Am găsit-o. Astfel că a fost într-adevăr schimbarea avem nevoie pentru a face. Asta a fost o mulțime de codificare noi Tocmai am făcut, căutare binară. Are cineva întrebări înainte de a Eu merg mai departe în linii le-am scris în binar de căutare sau modul în care ne-am gândit ce ne-am dat seama? Înainte de a trece mai departe, aș dori să subliniez că, în general, ne mapate nostru de pseudo-cod unul pentru unul pe codul nostru. Noi am avut acel lucru complicat să dau seama cu începe și se termină. Dar nu te-a dat seama de asta, tu ar fi scris destul de mult cod identic, cu excepția aceste primele două linii. Și apoi s-ar fi dat seama atunci când ai ajuns la verificări și cazuri în care aveți nevoie de altceva. Deci, chiar dacă ar fi urmat nostru pseudo-cod linie la linie, te-ar fi primit toate, dar două linii de cod ai nevoie pentru a scrie. Și aș fi dispus să pariez că voi ar fi dat seama că tot afară destul de repede, că ai nevoie pentru a pune un fel de marcaj acolo să dau unde ai fost. Că din nou, este puterea de a face pseudo-cod înainte de timp. Deci, putem face logica primul rând, și apoi putem să vă faceți griji cu privire la sintaxa. Dacă am fost confuz despre logica în timp ce încearcă să scrie acest cod în C, ne-ar fi ajuns tot incurcat. Și atunci am fi întrebări despre logică și sintaxă și discretizare le pe toate împreună. Și ne-ar fi ajuns pierdut în ceea ce poate deveni rapid un problemă foarte dificilă. Deci, haideți să mergem mai departe acum la selecția fel. Avem 20 de minute. Deci, am un sentiment nu vom fi capabili să trece prin toate de selecție fel și bule de sortare. Dar permiteți-ne, cel puțin încercare pentru a termina selecție fel. Astfel încât punerea în aplicare a selecție de sortare cu ajutorul în urma declarației funcție. Din nou, acest lucru este luat din problema stabilit caietul de sarcini. Valorile Int este paranteze, este o serie de numere întregi. Și int.n este dimensiunea de matrice. Un fel de selecție se va pentru a sorta această matrice. Deci, pe modelul nostru mental de selecție fel, am trageți - în primul rând, vom merge prin lista de primul timp, afla numărul cel mai mic, a pus-o la început, găsi de-al doilea cel mai mic număr, pune-l în a doua poziție în cazul în care dorim să sortare în ordine crescătoare. Eu nu te forțează să scrie pseudo-cod chiar acum. Dar inainte de a face codul ca o clasă în cinci minute, am de gând să scrie pseudo-cod așa că avem un anumit sens de unde mergem. Deci, încercați să scrie pseudo-cod pe cont propriu. Și apoi încercați să rândul său, că pseudo-cod în cod. Vom face acest lucru ca un grup în cinci minute. Și, bineînțeles, să-mi spuneți dacă aveți întrebări. STUDENT: Asta este? JASON Hirschhorn: a se vedea cât de departe poate obține în mai multe de două minute. Am înțeles că nu va putea termina. Dar vom trece peste acest lucru ca pe un grup. Ești tot atât de codificare [inaudibil], așa că eu sunt îmi pare rău pentru a opri ceea ce faci. Dar să mergem prin acest lucru ca pe un grup. Și din nou, binar de căutare, vă dau toate mi-o dacă nu mai multe linii de cod. Vă mulțumesc pentru asta. Vom face același lucru aici, cod împreună ca un grup. Astfel selecție fel - să scrie unele rapid pseudo-cod. Pe model mental, poate cineva să-mi dea prima linie de pseudo-cod, vă rog? Ce vreau să fac? STUDENT: În timp ce lista este în afara de ordine. JASON Hirschhorn: OK, în timp ce lista este în ordine. Și ce vrei să spui "de ordine?" STUDENT: În timp ce [inaudibil] nu au fost sortate. JASON Hirschhorn: În timp ce lista este în afara de ordine, ce facem? Dă-mi de-a doua linie, vă rog, Marcus. STUDENT: Deci găsi următorul cel mai mic număr. Acest lucru va fi indentat. JASON Hirschhorn: Deci găsi următor cel mai mic număr. Și apoi altcineva? După ce vom gasi cel mai mic următoare număr, ce facem? Am de gând să spun găsi cel mai mic număr. Asta e ceea ce vrem să facem. Deci, gasiti cel mai mic număr. Atunci ce facem? STUDENT: [inaudibil] la început. JASON Hirschhorn: Îmi pare rău? STUDENT: puneți-l în de început a listei. JASON Hirschhorn: Deci, puneți-l în începutul listei. Și ce facem de lucru care a fost la început din lista, nu? Suntem suprascrierea ceva. Deci, unde ne-am pus asta? Da, Anna? STUDENT: În cazul în care cel mai mic număr a fost? JASON Hirshhorn: Deci, pune la început listei unde cel mai mic număr a fost. Deci, în timp ce lista este în afara de ordine, găsi cel mai mic numar, puneți-l în la începutul listei, a pus începutul listei unde cel mai mic număr a fost. Marcus, poți să reformulez această linie în timp ce lista este în ordine? STUDENT: În timp ce numărul nu au fost clasificate în funcție? JASON Hirshhorn: OK, deci în scopul de a știu că numerele nu au fost sortate, ce trebuie să facem? Cât de mult avem nevoie să trece prin această listă? STUDENT: Deci, cred ca o pentru buclă, sau în timp ce, în timp ce numerele de verificat este mai puțin decât lungimea listei? JASON Hirshhorn: OK, asta e bine. Cred că misphrased întrebarea mea prost. Am fost doar încercarea de a ajunge la am de gând să trebuie să meargă prin toata lista. Deci, în timp ce lista este în afara de ordine, pentru mine, este greu de pe hartă. Dar, în esență, așa Cred că despre asta. Du-te prin intreaga lista, găsi cel mai mic număr, puneți-l în început - de fapt, ai dreptate. Să-i pe amândoi pus. Deci, în timp ce lista este în afara de ordine, ne-am trebuie să treacă prin întreaga listă o dată, a găsi cel mai mic număr, locul ea la începutul listei, a pus începutul listei unde cel mai mic număr a fost, iar apoi în cazul în care Lista este încă de ordine, ne-am Trebuie să treacă prin acest proces din nou, corect? De aceea selecție fel, Big-O execuție de selecție fel, cineva? STUDENT: n patrat. JASON Hirshhorn: n patrat. Pentru că așa cum Marcus și am dat seama aici, vom avea la du-te prin lista de lista număr de ori. Deci, trece prin ceva de lungime n n număr de ori este, de fapt, n pătrat. Deci, aceasta este pseudocod nostru. Acest lucru arata foarte bine. Are cineva intrebari despre pseudocod? Pentru că, de fapt un fel de selecție ar trebui să probabil veni unu la unu, codul de la pseudocod. Astfel încât orice întrebări cu privire la logică de pseudocod? Vă rugăm să-l întrebați acum. Un fel de selecție - în timp ce lista este în afara de ordine, vom trece prin ea și de a găsi cel mai mic de fiecare dată și-l pune în față. Deci, în timp ce lista este în afara de ordine, poate cineva da-mi ca linie de cod care nu mi-a dat o linie de cod dar, te rog? Se pare ca un ce? STUDENT: E o pentru buclă. JASON Hirshhorn: Sună ca un pentru buclă. OK, poti sa-mi oferi pentru buclă? Pentru - STUDENT: I ​​= 0. JASON Hirshhorn: i sau - ceea ce ne lipsește? Ce se întâmplă aici? STUDENT: Int. JASON Hirshhorn: Exact. (Int i = 0; - STUDENT: i