JASON Hirsch: Welkom te week drie, almal. Ons het 'n besige maar opwindende artikel voor ons. So die eerste, want ons het 'n paar vordering met die kursus, maar ons het nog steeds het 'n baie leer oor om te doen, is ek gaan julle te wys n paar hulpbronne wat moet bewys ongelooflik wees nuttig as jy nie net nader jou probleem sit nie, maar ook verteer al Die materiaal wat ons gee julle in lesings en kortbroek en afdeling. Dan gaan ons die eerste 20 te spandeer tot 25 minute van die artikel gaan oor GDB, wat jy mag of nie mag hê gebruik op hierdie punt, maar dit is 'n ongelooflike nuttige hulpmiddel wat sal help om jou programme te ontfout. Baie van julle kan printf gebruik het in die middel van jou program om uit te vind uit te vind wat 'n veranderlike geëwenaar. GDB is selfs beter as printf en nie skroef jou kode omdat jy loop dit op 'n uitvoerbare lêer. So ons gaan oor die 10 mees nuttige beveel jy nodig het vir GDB, en ons is gaan om te gaan op 'n oefening saam so in probleem van drie en verder, jy kan gebruik GDB debug te help jou programme. En uiteindelik, ons gaan om te gaan oor 'n paar sorteer en soek algoritmes wat jy gesien het in lesing, en ons is gaan eintlik kode, nie net pseudokode, maar kode binêre soek, borrel soort, en die seleksie soort. So die eerste, ek wil gaan oor die hulpbronne. Dit is 'n uitgebreide lys, en dit is kleiner lettergrootte, want ek het 'n baie te pas op hier. Maar dit sal nie net help om jou, weer met die probleem sit en verteer inligting wat jy geleer het, maar beslis, kom quiz tyd, dit sal ongelooflik nuttig. So die eerste, die lesing notas. As jy na cs50.net/lectures en gaan na die spesifieke week en dag, Jy sal sien dat daar notas vir elke lesing, wat nie net 'n transkripsie, maar 'n geredigeerde weergawe van wat gedek in lesing met kode brokkies en ander nuttige goedjies. Ek raai gaan oor hulle. En dan ook, daar is die bron-kode beskikbaar is vir elke lesing. En weer, sal hierdie skyfies ook aanlyn beskikbaar by cs50.net/sections hierdie aand. So tweede is die kortbroek elke week wat dek onderwerpe, gewoonlik 5 tot 15 minute in lengte. En diegene hopelik sal jy gee 'n groot primer oor verskillende onderwerpe. Derde - en dit is splinternuwe hierdie jaar - is study.cs50.net. As jy nog nie nagegaan dit uit, ek raai dat jy dit doen. Jy kry 'n onderwerp te kies. Ons het dekades van die onderwerpe op daar. So byvoorbeeld, jy kies funksies. Dit gee jou 'n paar skyfies notas en funksies. Dit is eintlik die skyfies wat TFS word aangemoedig om te gebruik tydens ons aanbiedings in afdeling. Daar is ook wenke en truuks vir die hantering met funksies, en daar is praktyk probleme wat help jy werk met funksies. Ons gee jou ook skakels na die kort op funksies en die tye wat funksies opgekom het in lesing. So study.cs50.net, splinternuwe hierdie jaar, 'n fantastiese hulpbron. Volgende, ek het die mens, wat is die handleiding opdrag wat jy kan loop op die command line. So as jy enige vrae het oor 'n opdrag, byvoorbeeld, rand, wat ons laaste week wat tydens artikel en jy het waarskynlik teëgekom in jou probleem stel wanneer gaan deur die genereer kode, maar as jy tik man rand, sal jy die bladsy kry wat vertel jou alles oor rand. Dit gee jou wat dit neem om die parameters wat dit neem, asook opbrengs tipe en 'n kort beskrywing van daardie funksie. So check rand. Dit kan 'n bietjie langdradig en verwarrend, so soms vind ek dat eenvoudig Googlen wat ek wil weet is die beste manier om die antwoord te vind. So oefen met Google. Kry goed op Google. Dit sal jou beste vriend word. Sowel as Google, as jy kan dit nie vind nie op Google, cs50.net/discuss, dit is die gespreksforum. Die kans is as jy 'n vraag, 'n van jou 700 + eweknieë het ook dat vraag en kan gevra het dit reeds in die bespreek forums en het dit beantwoord. So as jy 'n algemene vraag of jy het 'n vraag wat jy dink Miskien ander mense kan hardloop in, check cs50.net/discuss. Ten slotte, die laaste twee, as jy wil praat met 'n ware mens, kantoor Maandag tot Vrydag. Daar is ook aanlyn kantoorure vir uitbreiding studente. En laaste maar beslis nie die minste nie, my uitroepteken. Julle almal het my kontak inligting. As jy iets nodig het, kan jy nooit huiwer om my te kontak. Voel altyd vry om dit te doen. Baie min van julle het bygevoeg my op Gchat, sodat was teleurstellend, maar hopelik sal verander tussen hierdie en volgende afdeling. Enige vrae so ver op die hulpbronne? Groot. Ten slotte, 'n ander prop vir terugvoer, sayat.me/cs50. U kan my anonieme terugvoer oor hoe ek doen. Dit was werklik nuttig verlede week. Ek het 'n paar van die kommentaar van julle reg na artikel, plus uit ander studente wat dit gekyk gedurende die week, en dit was ongelooflik nuttig. Ek gaan om te probeer en my gebruik van beperk die woord "soet", maar ek sal jou wys my entoesiasme en opwinding op ander maniere. Maar daar was ook ander addisionele substantiewe terugvoer, beide plus punte en delta. So asseblief, ek gee julle terugvoer op jou probleem stelle. Voel vry om terugvoer gee my op my onderrig. Ek is hier om vir julle. Groot. Dit is al wat ek het vir Die eerste deel. Het enige iemand enige vrae so ver? En ek het 'n nota vir die beheer sentrum. Uitbreiding studente het my messaged sê hulle is nie om enige klank, maar dit is uit my krag op te los. So hopelik, wat kry opgelos kort. As jy online kyk, hi, maar jy kan my nie hoor nie. So die eerste, ons gaan om te gaan deur GDB. GDB, soos ek terloops by vroeër, is 'n debugging hulpmiddel baie beter as printf. So om te begin met GDB, julle ouens, indien jy wil maak jou toestel en neem die lêer wat ek per e-pos aan u vroeër - hierdie lêer sal ook aanlyn beskikbaar in 'n bietjie - en hardloop GDB / die naam van die lêer.. Eerstens, natuurlik, jy het op te stel liasseer omdat GDB werk net op uitvoerbare lêers. Maar as jy ooit wil begin GDB, die eerste ding wat jy doen, jy hardloop GDB. / Caesar. So wat is die naam van die program is ons gaan om te gaan met dit nou. So ek gaan om te skryf maak Caesar, wat gee my 'n uitvoerbare lêer hier uitgelig in groen. En dan gaan ek GDB. / Keiser uit te voer. En daar gaan jy. Jy sien ons het 'n paar teks vertel my oor die weergawe van GDB, gee my sommige inligting oor die waarborg, en dan het ons het die BBP vinnige, wat lyk soort van soos ons opdrag lyn vinnige, maar jy sien dit is oop paren, GDB, naby hakie. Voordat ons verder gaan en debug hierdie lêer dat ek na julle gestuur al, laat ons kyk na paar nuttige instruksies sodat ons 'n sin van wat ons gaan dek. Hierdie opdragte word hier gelys in die volgorde waarin ek oor die algemeen gebruik. So begin ek my program deur die loop GBD. / Naam van die program, In hierdie geval, die keiser. En dan is die eerste ding wat ek doen 99,9% van die tyd is die tipe break beteken. Dit stel 'n breek punt by die hoof. In wese, wat jy daar doen Die program gaan om te stop by hoof, sodat jy kan begin ondersoek dit lyn deur die lyn, eerder as om die hele die pad deur. Jy kan breek op verskillende punte in jou kode, maar belangrikste is oor die algemeen 'n goeie plek om te begin. Die volgende opdrag ek hardloop, is hardloop. Dit begin die program loop, en As jy nodig het opdrag lyn in te voer argumente, loop jy dat opdrag. Hardloop met die argumente. So, aangesien ons gaan oor 'n weergawe van C, wat is die program wat jy ouens geskryf het vir pset twee - hierdie een, natuurlik, het 'n paar foute in dit wat hopelik sal ons vind - ons gaan run hardloop met 'n paar command line argumente omdat Caesar, as julle weet per die probleem stel spec, neem 'n paar command line argumente. Die volgende paar bevele, is die volgende een is eintlik genoem volgende. Dat 'n mens neem jou lyn deur die lyn deur jou program. So slaan n tik dan neem jou na die volgende lyn, uitvoering die vorige lyn. Stap neem jy nie net tot die volgende lyn, maar dit neem jy binne funksies. So as jy het 'n funksie in 'n geskrewe jou kode of as jy wil om te verken 'n te Ek, byvoorbeeld, kan jy druk s en eerder as om te gaan na die volgende lyn van die lêer wat jy gaan deur reg nou, jy eintlik stap in hierdie funksie en sien die kode. Lys wys jou, in 'n baie gebruikers vriendelik formaat, die 10 of so lyne om waar jy tans in jou kode sodat jy kan eintlik sien die lêer eerder as om terug te ruil en weer tussen verskillende menings. Print is soos printf, soos sy naam impliseer. Dit wys jou wat 'n veranderlike gelyk. Inligting locals is werklik nuttig. Dit is 'n spesiale weergawe van die gedrukte media. Inligting locals wys jou al die plaaslike veranderlikes, druk hulle almal uit vir jou wat tans beskikbaar is. So ek oor die algemeen, eerder as om te druk die vier veranderlikes wat ek nuuskierig oor as ek in 'n lus vir die, vir Byvoorbeeld, ek skryf net info locals, en dit sal vir my wat my toonbank wys ek gelyk, sowel as die skikking dat ek werk op gelykes. Ten slotte, gaan voort. Tik break stop jy aan die breek punt. Jy kan loop deur die lyn deur lyn met die volgende stap en. Gaan voort lopies die program na die volgende breek punt of tot die voltooiing indien daar is nie meer breek punte. Afskakel verwyder breek punte as jy besluit om die breuk by die hoof was onvanpas, jy wil stel dit iewers anders. En uiteindelik Q, stop, klim uit GDB. So hierdie program, / Caesar, ons gaan. kyk nou deur en ons gaan GDB te gebruik om uit te vind die foute in hierdie program. Ek het hierdie program vroeër met Gaan 50, en ek het een frons. Alles wat dit bestaan, is dit saamgestel is, is dit geslaag het 'n groot deel van die toetse nie, maar vir een of ander rede, is dit nie die vyfde geslaag het nie toets, draai BARFOO, hoofletters, in E-D-U-ek-R-R, hoofletters, met behulp van drie as 'n sleutel. Ek het redelik naby. Ek het af deur een letter. So is daar 'n paar klein fout hier. Ek het kyk deur my kode. Ek kon dit nie vind dit uit. Hopelik kan julle my help uit te vind wat hierdie fout is. So dit is die fout is ons soek. Kom ons beweeg in GDB. Weereens, ek hardloop GDB. / Caesar, So nou is ons in GDB. En wat is die eerste ding wat ek moet doen? Ek het nou net ingeskryf het GDB. Iemand gee my 'n goeie opdrag te betree. STUDENT: Breek hoof. JASON Hirsch: Breek hoof. Fantasties. Kom ons tik wat in Julle kan kyk hier of volg saam op jou rekenaar. Breek hoof, en jy sal sien 'n breek punt is vasgestel op - dit gee my 'n paar vreemde geheue adres, en dit gee my ook die lyn nommer. As ek terug kyk na hierdie lêer, Ek wil hê dat die hoof besef gebeur op die lyn 21. Wat moet ek hardloop volgende? Is my program loop? No So, wat moet ek hardloop volgende? STUDENT: Begin. JASON Hirsch: Begin. Moet ek net hardloop hardloop, of indien Ek voeg 'n paar ander dinge in? STUDENT: Begin met die argument. JASON Hirsch: Begin met die opdrag argumente. En omdat ek die opsporing van 'n baie spesifieke geval is, moet ek in daardie command line argument. So ek sal loop nie drie, wat weer die uitset wat ek van Check 50. Begin program. Ons gaan deur 'n paar van die lyne. Jy sal nou sien dat ons op die lyn 21. Hoe weet ek dat ons op die lyn 21? Want as jy kyk na die linkerkant van my terminale venster, is daar dit sê lyn 21. En dit gee my, eintlik, die kode wat in reël 21. So ek misspoke vroeër. Main is nie eintlik op lyn 21. Main is 'n paar van die lyne bo 21. Maar op lyn 21, dis waar ons breek. Hierdie lyn van die kode het nog nie uitgevoer is. Dit is belangrik. Die lyn wat jy sien het nie is nog nie uitgevoer is. Dit is die volgende lyn van die kode jy oor om te voer. So die volgende lyn, as jy ouens is waarskynlik vertroud is met, is hierdie toestand nagaan om te sien of ek ingeskryf vir 'n opdrag lyn argument. En om 'n i, wat is die tweede deel van daardie doen? Wat is 'n te i? STUDENT: Verandering is dit tot 'n heelgetal. JASON Hirsch: Jammer? STUDENT: Dit is die verandering van die argument tot 'n heelgetal. JASON Hirsch: So 'n te verander i arg v1 van 'n string na 'n heelgetal. En dan wat dit nagaan? STUDENT: Indien daar 'n tweede command line argument, opsy van die uitvoer van die program. JASON Hirsch: En wat is die tweede helfte van hierdie Boole-uitdrukking te keur? Hierdie deel hier, om 'n i? STUDENT: As dit negatief. JASON Hirsch: Maak seker wat? STUDENT: Maak seker dat dit is, in werklikheid, positief. JASON Hirsch: Presies. Dit is om te kyk of dit negatiewe, en as dit negatief is, het ek het 'n gevoel die volgende lyn mag word my skree op die gebruiker. So laat ons getref einde hierdie lyn uit te voer. Ons sien nie dat die lyn dat jy ouens Miskien verwag om te sien skree op die gebruiker en dan weer terug, want hierdie lyn het nie uit te voer. Ek het in 3. So ek het, in werklikheid, tree twee opdrag line argumente, en 3 is groter as nul. So het ons gesien dat die lyn, het ons uitgevoer word, maar ons het nie stap binne-in die indien toestand. So nou, volgende, ek sien ek die opstel int sleutel gelyk om 'n i ARG v1. So dit is my skep van 'n veranderlike sleutel. So as ek druk die sleutel op die oomblik, want wat u toelaat om te sien die waarde in die veranderlike, sleutel is gelyk aan 47. Dit is vreemd, maar natuurlik, dit is, want ek het nie uitgevoer dat die lyn nie. So as ek nou getref N, voer die lyn, en doen druk die sleutel, sal die sleutel gelyk 3, en dit is wat ons verwag om dit te ewenaar. So weer, in GDB, die lyn wat jy sien jy nog nie uitgevoer nie. Jy het om te tref N of S of 'n aantal ander opdragte om werklik voer die lyn. Print sleutel. Sleutel se op 3. So ver, so goed. String is plain text. Kom ons voer die lyn. Ek kry 'n string van die gebruiker. Kom ons kyk in my Check 50, ek Tik BARFOO hoofletters, so dit is wat ek sal gaan. As ek druk nou plain text. Jy sal sien dit is gelyk aan 'n tou. Dit gee my 'n paar ander vreemde heksadesimale nommer, maar dit nie in feit sê dat my string is BARFOO. As ek wou om te sien wat die sleutel geëwenaar by hierdie punt, hoe kon ek seker sleutel? STUDENT: Druk sleutel. JASON Hirsch: Druk sleutel, presies. En eintlik, daar is 'n kortpad. As jy moeg van tik druk, jy kan net tik p. So p sleutel doen presies dieselfde ding. En weer, ek sien dit is gelyk aan 3. As ek wou om uit te vind wat beide sleutel en BARFOO geëwenaar op dieselfde tyd Maar ek was moeg van tik elke een uit individueel, ek kon tik info locals. Dit gee my sleutel gelyk aan 3. Plain text gelyk BARFOO. Dit gee my ook hierdie twee vreemde dinge aan die bokant, hierdie veranderlike en ek hierdie veranderlike n. Diegene eintlik bestaande in my program. Ons het nog nie teëgekom het, maar as 'n voorbeeld, wat bestaan ​​in my lus. So nou het hulle 'n paar vreemde gelyk getalle, omdat hulle nie geïnisialiseer nie, maar hulle nie nog steeds bestaan in die geheue, sodat hulle net soos sommige vullis waarde. Maar ons sien sleutel in plain teks reg daar. So ek gaan hierdie lyn uit te voer, lyn 34, die lus. Ons gaan om te spring in die lus deur slaan n. En ons is binne-in die for-lus. Ons is op ons eerste tjek. En weer, moet hierdie soort van kyk bekend aan jou, want dit was 'n Caesar program wat geskryf is nie, maar weer, het 'n soort van fout. En as ek nou doen info inwoners, omdat ek binne daardie lus, sal jy sien dat ek gelyk is aan nul, as ons verwag. Dit is wat ons stel dit en geïnisialiseer dit in die te for-lus. n gelyk 6. Dit maak ook sin, want ons stel dit aan die StrLen van plain text. So ek wil info locals of druk om te doen om veranderlike dikwels om seker te maak dat alles is altyd wat Ek verwag dat dit gelyk. In hierdie geval is, is alles wat ek verwag dat dit gelyk. So laat ons begin beweeg deur dit vir lus. Die lyn Ek is 'n lyn is 36, as plain teks wat ek is groter as 'n gewone en teks wat ek minder as of gelyk aan Z. Ek weet my probleem is nie met my eerste brief, dit is die tweede brief. As ons terugkyk na Check 50, B gaan na E fyn. Ek neem die A-en laat dit as 'n A, nie om dit te verander na D. So iets is verkeerd met die tweede brief. So ek gaan om te beweeg daar in 'n tweede. Maar as ek wil het wat plain om te kyk teks wat ek geëwenaar in hierdie spesifieke geval, ek dink dit behoort te wees wat? Wat moet plain text ek in hierdie gelyk eerste ronde deur die lus? STUDENT: Zero? JASON Hirsch: Plain teks van I? So dit moet kapitaal B. Ek, natuurlik, gelyk is aan nul, maar plain text bracket nul geslote bracket gelyk aan B omdat snare, soos ons verlede week gesien het, is skikking, so ons kry die eerste karakter van daardie. So weer, as ek gedruk gewone teks van Ek, ek, in werklikheid, kry die karakter B. En dit is netjies, reg? Ek doen eintlik nie gewone teks I. Dit is nie een van die veranderlikes ek of geïnisialiseer nie, maar jy kan druk uit 'n hele leër van die dinge wat As jy wil. Maar laat ons beweeg deur. As plain text ek is groter as A en plain text Ek is minder as of gelyk aan Z, wat duidelik is waar, want ons het 'n kapitale B. Ek gaan om te hardloop sommige opdrag op dit. Ons het gesien dat wiskunde verlede week, so ons sal neem dit as vanselfsprekend dat dit werk reg volgens Gaan 50. Hierdie krullerige draadjies, die eerste een getoon dat ek die verlaat van die as toestand is, die tweede een het ' dat ek die verlaat van die for-lus. En so nou wanneer ek getref Volgende, ons sal sien Ons is terug by die lus weer. Ons gaan deur die lus weer. Kom ons eintlik stap in die tweede iterasie van die lus en die tipe info locals. So is ons in die tweede iterasie van ons lus. Ek is gelyk aan 1, wat ons verwag. N gelyk aan 6, wat ons verwag. Sleutel gelyk aan 3, wat ons verwag. En gewone teks, sal jy sien, is gelyk aan EARFOO nou, nie meer BARFOO omdat In ons vorige iterasie, die B was verander na 'n kapitale E. So ons gaan die probleem te ontmoet, so hierdie is waar ons gaan duik in die opsporing. Maar nie almal het vrae oor wat ons tot dusver gedoen het? Fantasties. So ons is oor hierdie uit te voer indien toestand is, gewone teks bracket ek gesluit bracket groter as 'n gewone teks en ek minder as of gelyk aan Z. Maar voordat Ek gaan in, want dit is waar Ek weet my fout, ek wil om te wys uit gewone teks van I. So laat ons uitdraai. Dit maak gelyk aan die karakter N, sodat lyk so ver, al is goed en wel. So ek verwag dat hierdie lyn per my logika, Hierdie reël moet waar wees. Dit is 'n hoofletter. Maar as ek getref N, het ons besef dat hierdie lyn, in werklikheid, het nie uit te voer. Ek het opgespring af na die else if. Hoekom het dit gebeur? STUDENT: Omdat jy jou toestand van gewone teks is groter as A, nie gelyk of groter as. JASON Hirsch: So ek het my gewone teks Ek is meer as 'n nie groter as of gelyk aan. So duidelik, die hoofstad A nie aktiveer hierdie As toestand, en ons het nie stap in dit, en ons het nie die nodige verskuiwing. So dit is dit nie, eintlik. Ek het gedink my fout. Ek kon terug gaan in my bron lêer, verander, en werk dit en hardloop Check 50 weer. Maar ons sal sien, net vir pedagogie se ontwil, as ek gaan hou. Die anders as nie óf uit te voer, maar wat in plaas gelyk aan die opdrag wat nie verander nie. So dit is nie verander nie, en as ek druk plain text hier, sal ons sien gaan deur daardie lus het nie, in werklikheid, verander dat die tweede karakter nie. Dit is nog steeds 'n kapitale A. So weer, ons ontfout ons fout. Ons besef dat daar ' sommige logika ontbreek. En ons ontfout dit voor die tyd voor eintlik die uitvoering van die lyn, maar jy sal opgemerk het ons net getref Volgende en spring aan daardie anders as, Dit beteken dat indien toestand was nie waar nie. Ons het nie, in werklikheid, kry die resultaat wat ons verwag het. So het ons gevra kon gewees het, het ons nie so slim, om te kyk na dat indien die toestand en kyk of, in werklikheid, ons toestand moet evalueer waar in die huidige konteks. Dit is al vir die opsporing van hierdie program. Het enige iemand enige vrae? Wat opdrag kon ek getref GDB om op te hou? Vraag en dan sal ek gevra word, hou in elk geval? Ja of nee. Ek sal getref ja, en ek sal ophou het GDB. So dit was 'n vinnige primer te GDB. Eintlik, in 'n werklike scenario, Ek het dit by kantoorure. Ek GDBed hierdie presiese program by kantoorure met 'n student. En as ons gaan terug na die instruksies wat ons gesien het voor, wat ons gebruik break hoof, eerste ding wat ons gedoen het. Ons gebruik run met command line argumente, tweede ding wat ons gedoen het. Ons gebruik die volgende 'n baie om te beweeg ons deur lyne. En weer, die kort weergawe volgende is n. Dit is in die hakies in grys op die skyfie. Ons het nie stap gebruik nie, maar ons het nie noodwendig moet vir hierdie geval. Maar ons kan dit later gebruik in 'n bietjie vandag as ons die opsporing, vir Byvoorbeeld, binêre soek wanneer binêre Soek in 'n afsonderlike genoem funksie, maar daar is sommige fout met dit. Ons gaan om te wil om te stap in die oproep na binêre soek en eintlik te ontfout. Lys ons dit nie gebruik nie, want ons het 'n goeie sin van ons kode, maar as ek wou 'n gevoel van wat ek kode te kry was rond, ek kon net gebruik lys. Druk ons ​​gebruik, info locals wat ons gebruik. Gaan voort ons nie nodig het om te gebruik in hierdie geval nie, en het ons nodig het om te gebruik afskakel, maar ons het gebruik te hou. Weereens, hierdie 10 gebooie, oefen hulle. As jy verstaan ​​hierdie 10 gebooie, jy moet opgestel word vir die opsporing van enige reik GDB. So ons is oor te gaan, weer, aan die kern van artikel vandag, gaan oor hierdie sortering en soek algoritmes. Voordat ons dit doen, weer, enige vrae het, kommentaar, knelpunte vir GDB? So is almal gaan gebruik GDB eerder as printf? So almal, ter wille van ewigheid's, almal knik hul kop reg nou, so ek sal jy sien by kantoorure en al die TFS sal jy sien Hulle sal sê, wys my hoe om te gebruik GDB, en jy sal in staat wees om hulle te wys, reg? Soort? Miskien hopelik. Cool. So ons gaan om te skuif na sorteer en soek. Jy sal sien ek het 'n lys wat reeds uitgesorteer vir ons, maar dit is nie gaan om die saak te altyd wees. So in die probleem stel spesifikasie vir probleem van drie, het jy kortbroek wat jy kan sien, en dit eintlik vra jy daardie broekie te kyk. Ook in lesing verlede week, het ons oor 'n groot deel van hierdie algoritmes, so ek is gaan nie tyd te spandeer in die klas gaan oor hierdie algoritmes weer of tekening foto's vir hoe hierdie algoritmes werk. Weereens, dat die inligting wat jy kan weer sien lesing, of dat die inligting is uitstekend vasgelê op die kortbroek vir die soeke, almal van wat beskikbaar is op cs50.net. So in plaas daarvan, wat ons gaan doen, is skryf hierdie programme. Ons het 'n gevoel, 'n geestelike model, hoe hulle werk, en so wat ons gaan om te doen is die kode om hulle vir die ware. Ons gaan dat die geestelike model om te draai, dat die foto, as jy wil, in die werklike kode. En as jy 'n bietjie verward of vaag op die geestelike model, ek is dit heeltemal verstaan. Ons is eintlik nie van plan om spring kode dadelik. Dus, terwyl die vinnige in hierdie skyfievertoning vra jy binêre soek na kode, en die Eintlik is 'n iteratiewe weergawe van binêre soek, is die eerste ding wat ek regtig wil hê jy moet doen, is om skryf 'n paar pseudokode. So jy het die geestelike model hoe binêre soek werk. Neem 'n vel papier as jy ' een geredelik beskikbaar is nie, of maak 'n teks editor, en ek wil graag almal te skryf. Neem vier minute om te skryf die pseudokode vir binêre soek. Weereens, dink oor wat geestelike model. Ek sal kom rond as jy vrae en ons kan die prentjie teken nie. Maar eers, voordat ons begin ontwikkeling, Ek wil graag om te skryf die pseudokode vir binêre soek sodat wanneer ons duik in, ons het 'n rigting as waar ons moet kop. STUDENT: Kan ons aanvaar die verskeidenheid van waardes wat ons kry, is reeds gesorteer? JASON Hirsch: So vir binêre soek om te werk - 'n uitstekende vraag - jy het aan 'n gesorteerde verskeidenheid van waardes. So neem aan dit sal werk. Ons sal na hierdie skyfie gaan. Jy sal sien in die pers die funksie verklaring is Bool binary_search int waarde, int waardes, int n. Dit moet lyk bekend as jy het reeds genader of gekry jou hande vuil met die probleem stel. Maar dit is jou funksie verklaring. Weereens, moet nie hoef te bekommer oor dat daar nog baie op hierdie oomblik. Wat ek regtig wil hê jy moet doen, is om vier minute te pseudokode binêre soek, en dan sal ons gaan oor wat as 'n groep. En Ek sal om kom. As jy vrae het, voel vry om jou hand op te steek. Hoekom het jy nie neem twee minute tot die einde van die pseudokode? Ek weet dit mag lyk belaglik dat ons so baie tyd is spandeer op iets wat nie eens werklik in C, maar veral vir die meer uitdagende algoritmes en probleem stelle wat ons het om uit te vind, begin in pseudokode nie bekommerd te wees oor die sintaksis, net bekommerd te wees oor die logika, is ongelooflik nuttig. En op die manier, is jy nie die oplossing van twee ongelooflik moeilike probleme in 'n keer. Jy is net te fokus op die logika, en dan beweeg jy na die sintaksis. OK. Kom ons begin gaan deur die pseudokode. Ek het geskryf hier, binêre Soek pseudokode. Ons sal hierdie skrywe op die saam boord. Of sal ek dit skryf en jy sal gee my die aanwysings wat ek nodig het. So kan enige iemand gee my die eerste lyn van die pseudokode jy geskryf het vir binêre soek? Ja, Annie? STUDENT: Terwyl die lengte van die lys is groter as nul. JASON Hirsch: Terwyl lengte van 'n lys van groter as nul. En weer, sien ons 'n paar C-soek sintaktiese dinge hier. Maar die meeste van hierdie is in Engels. Het enigiemand enige lyn het hulle voordat dit in hul pseudo-kode? STUDENT: Kry 'n skikking van gesorteer nommers. JASON Hirsch: Jy het geskryf: "kry 'n verskeidenheid van gesorteer getalle "Per die. funksie verklaring, sal ons aanstuur 'n verskeidenheid van gesorteer nommers. STUDENT: [onhoorbaar]. JASON Hirsch: So ons sal dit. Maar ja, as ons nie dat ons nodig sou wees om ons verskeidenheid van te sorteer getalle, want binêre soek werk net op gesorteer skikkings. Dus, terwyl die lengte van die lys is gelyk aan nul, ek is gaan sit in 'n krulhakies te maak dat dit lyk 'n bietjie meer soos C. Maar terwyl, lyk na die kaart op 'n while loop, so binne hierdie terwyl lus wat ons nodig het om te doen vir binêre soek? Iemand anders wat nog nie 'n aan my gegee beantwoord nie, maar wat hierdie geskryf? STUDENT: Gaan na die middel van die lys. JASON Hirsch: Tom. Gaan na die middel van die lys. En die opvolg vraag, wat doen ons wanneer ons by die middel van die lys? STUDENT: Doen 'n tjek of dit die getal wat jy soek. JASON Hirsch: Uitstekende. Gaan die middel van die lys en maak seker As ons waarde is daar - fantasties. Het enigiemand iets anders dit was anders as dit? Dit is presies reg. Die eerste ding wat ons doen in binêre soek word na die middel van die lys en kyk om te sien of ons waarde is daar. So ek neem aan as ons waarde is daar, wat doen ons? STUDENT: Ons keer terug zero [onhoorbaar]. JASON Hirsch: Ja, as ons waarde is daar, ons het dit gevind. So kan ons een of ander manier vertel, maar dit funksie gedefinieer is, vertel ons die gebruiker ons het dit gevind. As dit nie daar is nie, al is, dit is Waar dit kry lastig. So as dit is nie daar nie, iemand anders wat besig was op binêre soek of het 'n idee nou, wat doen ons? STUDENT: Vraag. JASON Hirsch: Ja? STUDENT: Is die skikking reeds gesorteer? JASON Hirsch: Ja, ons is die veronderstelling die skikking reeds uitgesorteer. STUDENT: So dan het jy om te kyk of die waarde wat jy sien is groter as die waarde wat jy wil, kan jy beweeg tot in die middel van die ander helfte. JASON Hirsch: So as die middel van die lys is groter as wat ons is soek, dan doen ons wat? Ons beweeg waar? STUDENT: Jy wil om te skuif na die helfte van die lys met getalle laer as dit. JASON Hirsch: So ons sal noem dat die linkerkant. So as middel is groter, kan ons soek die linker helfte van die lys. En dan deur die search, wat bedoel ek met soek? STUDENT: [onhoorbaar]. JASON Hirsch: Ons gaan na die middel. Ons het eintlik hierdie ding herhaal. Ons gaan terug deur ons lus. Ek gee jou die laaste een - anders, indien middel is minder as wat ons doen, wat ons hier doen? STUDENT: Gaan na die regterkant. JASON Hirsch: Soek die reg. Dit lyk goed, maar niemand het iets wat ons dalk ontbreek of enigiets anders wat jy in jou pseudo-kode? So dit is wat ons tot dusver. Terwyl die lengte van die lys is groter as nul, ons gaan om te gaan na die middel van die lys en kyk of ons waarde is daar. As die middel is groter, gaan ons soek verlaat, anders as die middel is minder, gaan ons die reg om te soek. So het ons almal het 'n paar vertroudheid met die terme wat ons gebruik in rekenaarwetenskap en die gereedskap wat ons het. Maar jy sal al sien ons was praat in Engels, maar ons het 'n Baie van die dinge wat gelyk kaart op te gereedskap wat ons in ons kodering instrument stel. So reg uit die kolf, ons is nie gaan eintlik kodeer nie. Wat doen ons hier te sien in Engels wat kaarte op die dinge wat ons kan skryf in C? STUDENT: Terwyl. JASON Hirsch: Terwyl. So dit terwyl hier kaarte op wat? Student: a while loop. JASON Hirsch: 'n lus? Of waarskynlik meer algemeen, 'n lus. Ons wil oor en oor om iets te doen. So ons gaan 'n lus om te kode. En ons weet reeds, want ons het gedoen dit 'n paar keer en ons het baie van die voorbeelde wat daar is, Hoe werklik te skryf hierdie indeks vir 'n lus. So wat moet wees redelik maklik. Ons moet in staat wees om dit te kry begin redelik vinnig. Wat anders sien ons hier? Watter ander strukture syntaxes, dinge dat ons vertroud is met in C, doen ons reeds 'n gevoel van Based het af van die woorde wat ons gebruik? Ja, Anna? [Onhoorbaar] net 'n grap. Anna, gaan voort. STUDENT: Indien en anders. JASON Hirsch: As en anders - reg hier. So wat doen hulle lyk? STUDENT: 'n as anders verklaring. JASON Hirsch: Ja, voorwaardes, reg? So ons sal waarskynlik nodig het om te skryf 'n paar voorwaardes. En weer, al is miskien verwarrend Eerstens, ons het oor die algemeen 'n gevoel nou van hoe die toestande en te skryf die sintaksis vir toestande. En as ons dit nie doen nie, ons kyk net na die sintaksis vir toestande, sny en plak dat, omdat ons weet dat ons 'n toestand hier. Enige ander dinge sien ons dat die kaart op dinge wat ons dalk nodig het om te doen in C? Ja, Aleha? STUDENT: Dit kan duidelik wees, deur net seker te maak dat 'n waarde gelyk iets. JASON Hirsch: So hoe kan ons seker en - so gaan na die middel van die lys en kyk of ons waarde is daar? Hoe doen ons dit in C? Wat is die sintaksis vir daardie? STUDENT: gelykes, gelyk. JASON Hirsch: gelykes, gelyk. So hierdie tjek is waarskynlik gaan 'n gelykes te wees, is gelyk aan. So sal ons weet ons moet dit iewers. En eintlik, net om dit te skryf, ons sien die ander dinge. Ons gaan 'n paar om te doen vergelyking operateurs in daar - fantasties. Dus is dit eintlik lyk, deur en groot, het ons nie 'n geskrewe woord van C-kode nie. Maar ons het die geestelike model af via lesings en diegene kortbroek. Ons het pseudo-kode as 'n groep. En al het ons 80%, indien nie 90% van wat ons nodig het om te doen. Nou, het ons net nodig het om te kodeer dit, wat weer, is 'n nie-triviale probleem op te los. Maar ten minste ons vas op die logika. By nou minste wanneer ons gaan na kantoorure, Ek kan sê, ek weet wat ek nodig het om te doen, maar jy kan herinner my van die sintaksis? Of selfs as kantoorure is oorvol, jy Google kan vir die sintaksis, eerder as om vas op die logika. En weer, eerder as om te probeer om op te los die logika en die sintaksis probleme al gelyktydig, is dit dikwels baie beter te breek die twee harde probleme af in twee meer hanteerbare kinders en doen die pseudo-kode en dan die kode in C. So laat ons sien wat ek gedoen het vir die pseudo-kode voor die tyd. Terwyl die lengte van die lys is groter as nul is, kyk na die middel van die lys. As aantal gevind teruggekeer waar is, anders As aantal hoër, soek linkerkant. Anders as nommer laer, soek regs, terug onwaar. So wat lyk byna identies indien nie byna identies aan wat ons geskryf het. Eintlik, Tom, wat jy die eerste keer gesê, breek die middel van die lys, en indien nommer word in twee state is eintlik wat ek gedoen het. Ek gekombineer hulle daar. Ek moet geluister het na jy die eerste keer. So dit is die pseudo-kode wat ons het. As jy wil nou, jammer, gaan Terug na ons aanvanklike probleem. Kom ons kode binary.c. So implementeer 'n iteratiewe weergawe van binêre soek met behulp van die volgende funksie verklaring. En jy hoef nie te kopieer dit af net nog nie. Ek is eintlik van plan om oop te maak up hier binary.c. So is daar die funksie verklaring in die middel van die skerm. En jy sal sien ek het die pseudo-kode uit op my kante, maar byna identies wat ons geskryf het, en sit dit in vir jou. So nou, laat ons 'vyf minute hierdie funksie te kode. En weer, as jy enige vrae het, lig jou hand, laat weet my, ek sal kom rond. STUDENT: [onhoorbaar]. JASON Hirsch: Toe het ek die binêre Soek definisie aan die bo, op die lyn 12. Dit is wat ek vir my skuif. En dan sal al hierdie pseudo-kode het ek net kopieer en plak van die skyfie, pseudo-kode skuif. Ek is nog steeds nie hoor [onhoorbaar]. So as jy klaar is met jou implementering, ek wil om dit te sien. Ek e-pos wat jy die helpers.h lêer vroeër in hierdie klas. En dit sal ook aanlyn beskikbaar wees vir aflaai vir mense kyk hierdie artikel tyd vertraag. En ek het net gebruik om die generiese verspreiding kode van pset3. Toe het ek find.C, gebruik my helpers.h lêer eerder as om die lêer helpers.h dit is gegee in die verspreiding kode. En ek het een ander verandering in te maak find.C eerder as 'n beroep net eenvoudig Soek, bel binary_search. So as jy jou kode te toets, weet dat dit is hoe om dit te doen. Trouens, wanneer ons sal loop hierdie kode nou, ek het net 'n afskrif van my pset3 gids weer omgeruil die helpers lêers en dan gemaak dat verander in find.C binary_search te roep eerder as om net te soek. JASON Hirsch: Ja. Jy het 'n vraag? STUDENT: Nevermind. JASON Hirsch: Geen sorge. Wel, laat ons begin. Ons sal hierdie kode as 'n groep. Een ander noot. Weereens, dit is, kan maklik omgeruil word in vir Probleem van drie. Ek het my helpers.h lêer wat eerder as die helpers.h ons gegee, verklaar binêre soek, borrel soort, en die seleksie soort. En in find.c jy sal sien op die lyn, wat is dit, lyn 68, binêre noem ons soek eerder as soek. So weer, die kode wat beskikbaar is aanlyn of die kode wat jy skep nou kan maklik omgeruil word in die p stel 3 om dit te sien. Maar eers, laat se gedragskode binêre soek. Ons funksie verklaring, ons terugkeer 'n Bool. Ons neem 'n heelgetal waarde genoem. Ons neem 'n verskeidenheid van heelgetalle genoem waardes, en ons neem n wees die grootte van die skikking. On line 10, reg hier, ek het skerp sluit stdbool.h. Het enige iemand weet waarom dit daar? So, wat beteken dat die lyn van die kode te doen? STUDENT: Dit kan jy gebruik om 'n Bool return. JASON Hirsch: Presies. STUDENT: Of dit is 'n biblioteek wat toelaat 'n Bool terugkeer tipe om te gebruik. JASON Hirsch: So het die skerp sluit stdbool.h lyn gee my 'n paar definisies en verklarings vir dinge dat ek toegelaat om te gebruik in hierdie biblioteek. So onder diegene sê dat daar hierdie tipe genoem Bool, en dit kan wees ware of vals. So dit is wat daardie lyn nie. En as ek het nie daardie lyn, sou ek kry in die moeilikheid vir die skryf van hierdie woord reg hier, Bool, reg daar. Presies reg. So ek moet die wat in hierdie kode. OK. So dit, weer, is 'n herhalende weergawe, nie 'n rekursiewe een. So laat ons begin. Kom ons begin met die eerste lyn van pseudokode. En hopelik, sal ons - of nie hopelik. Ons gaan om te gaan in die kamer rond. Ons gaan reël vir reël, en ek sal jou help jy uitvind die lyn wat ons nodig eerste skryf. Dus, terwyl lengte van lys groter as nul is. Kom ons begin in die voorkant. Watter lyn moet ek skryf hier, in die kode? STUDENT: Terwyl hakies n groter as 0. JASON Hirsch: Terwyl n groot as 0. So n is die grootte van 'n lys, en ons nagaan indien - [INTERPOSING Voices] JASON Hirsch: - jammer? STUDENT: Hoe weet ons dat n is die grootte van die lys? JASON Hirsch: Jammer. Per die pset spesifikasie, die soektog en sorteer funksies wat jy nodig het om te skryf, n is die grootte van die lys. Ek het vergeet dat hier te verduidelik. Maar ja. n die grootte van die lys, in hierdie geval. Dus, terwyl n groter as 0. OK. Dit kan bewys dat 'n bietjie problematies al is, as dinge gaan op. Omdat ons sal voortgaan om te weet wat die grootte van die lys in hierdie funksie nie, maar sê dat ons begin met 'n verskeidenheid van 5 heelgetalle. En ons gaan en ons het nou verklein dit af te 'n skikking van 2 heelgetalle. Watter 2 heelgetalle is dit? Die grootte is 2 nou dat ons wil kyk, maar waarvan 2 is dit? Is wat sin maak, dat die vraag? OK. Ek sal dit weer vra. So begin ons met hierdie verskeidenheid van 5 heelgetalle, en n gelyk 5, reg? Ons sal loop deur hier. Ons sal waarskynlik die grootte verander, reg, as dinge gaan op. En dit is wat ons sê ons wil doen. Ons wil nie te soek die volle ding weer. So sê ons verander dit na 2. Ons neem die helfte van die lys wat is vreemd. So net kies 2. So nou n gelyk 2. Ek vra om verskoning vir die swak droë vee merkers. Reg? En ons is op soek na die lys weer met 'n lys van grootte 2. Wel, ons skikking is nog steeds van groot 5. Ons sê ons wil net om te soek 2 kolle in. So wat 2 kolle is dié? Is wat sin maak? Is hulle die linker 2 vlekke? Is hulle die reg 2 vlekke? Is hulle die middel 2 vlekke? Ons het die probleem afgebreek, maar ons eintlik nie weet watter deel van Die probleem wat ons nog steeds op soek na, deur net met hierdie 2 veranderlikes. So het ons 'n bietjie meer dan terwyl n groter as 0. Ons moet weet waar daardie n is in ons werklike skikking. So nie almal het 'n verander na hierdie lyn? Die meeste van hierdie lyn is heeltemal korrek. Is daar 'n ander Benewens? Kan ons ruil iets uit vir N 'n bietjie beter te maak hierdie lyn? Mm-hm? STUDENT: Kan jy inisialiseer 'n veranderlike soos lengte n wat dan gebruik sal word later in die funksie? JASON Hirsch: So inisialiseer 'n veranderlike lengte n, en ons wat later gebruik? Maar dan moet ons net werk lengte en ons nog steeds loop in hierdie probleem waar ons sny die lengte van ons probleem, maar ons weet nooit waar nie, eintlik, dat lengte kaarte op. STUDENT: Is dit nie gaan gebeur later wanneer jy sê, soek links, soek reg? Jy gaan om te gaan na 'n ander area van jou - JASON Hirsch: Ons gaan om te gaan na 'n gebied nie, maar hoe weet ons wat om te gaan na? As ons net die skikking en dit n, hoe weet ons waar om te gaan in die skikking. In die rug, ja? STUDENT: Het jy soos 'n laer gebonde en 'n bogrens veranderlike of iets soos dit? JASON Hirsch: OK. So, dit is 'n ander idee. Eerder as om net die dop van die grootte, hou ons op hoogte van die laer en bogrens veranderlike. So hoe kan ons bereken die grootte van 'n ondergrens en bogrens? [INTERPOSING Voices] JASON Hirsch: aftrek. En ook die dop van die laer gebind en boonste gebind om ons te laat weet, is ons op soek hierdie twee? Is ons op soek hierdie twee hier? Is ons op soek die middelste twee? Waarskynlik nie die middelste twee nie, want hierdie, in werklikheid, is binêre soek. Maar nou sal ons in staat wees om die grootte te kry, maar ook die grense van die skikking. In wese is, as ons ons reuse telefoon boek, ons rip dit in die helfte. Ons weet nou waar dat kleiner telefoon boek is. Maar ons is nie eintlik rip die telefoon boek in die helfte. Ons het nog steeds nodig om te weet waar die nuwe grense van ons probleem is. Het enige iemand enige vrae oor wat? Ja? STUDENT: Sal dit werk deur die skep van 'n veranderlike, i, dat jy dan net verskuif die posisie van i relatief tot sy huidige posisie, en die lengte, n? JASON Hirsch: En wat is ek? STUDENT: Soos ek om soos soort van - Soos jy sou inisialiseer i die te wees Midde-posisie van die skikking. En dan, as die waarde by posisie i in die middel van die skikking in gevind minder as die waarde wat jy nodig het, het ek nou word die lengte van die skikking, plus die waarde van i gedeel deur 2. Soos, sien, jy skuif ek - JASON Hirsch: Right. STUDENT: - tot die - JASON Hirsch: So is ek amper positiewe wat sal werk. Maar die punt is, moet jy twee stukkies inligting hier. Jy kan dit doen met die begin en die einde, of jy kan dit doen met die grootte, en dan sommige merker. Maar jy moet twee stukke inligting hier. Jy kan nie kry deur met net een. Maak dit sin maak? So ons gaan deur te gaan, en ons gaan doen [onhoorbaar] en 'n paar merkers. So Wat het jy in jou kode te skryf? STUDENT: Ek het net gesê int gebonde een is gelyk aan 0. JASON Hirsch: Kom ons noem dat int, begin. STUDENT: OK. JASON Hirsch: Dit maak meer sin vir my. En? STUDENT: Ek het gesê, dink ek, Int eindig. JASON Hirsch: INT eindig. STUDENT: Ek dink, n minus 1, of iets soos dit. Soos, die laaste element. JASON Hirsch: So jy geskryf het, int begin gelyk aan 0, kommapunt, en int einde gelyk aan n minus 1, kommapunt. So in wese, wat ons doen Hier 0 die eerste posisie. En as ons weet in skikkings, gaan hulle nie tot N, hulle gaan na n minus 1. So ons het 'n paar grense van ons verskeidenheid. En hierdie aanvanklike grense gebeur om te wees die aanvanklike grense van ons probleem. OK. So dit klink goed. Dan as ons gaan terug na hierdie lyn, terwyl lengte van die lys is groter as 0, wat, in plaas van N, moet ons sit hier? STUDENT: Skryf eindig minus begin. JASON Hirsch: Terwyl eindig minus begin is groter as 0? OK. En ons kon, as ons wou te maak dat 'n bietjie mooier, watter anders kan ons doen? As ons wou om skoon te maak hierdie kode 'n bietjie? Hoe kan ons ontslae te raak van die 0? Dit is net 'n styl kwessie. Dit is korrek nou. STUDENT: eers nie gelyke begin? JASON Hirsch: Ons kan dit doen wat? [INTERPOSING Voices] STUDENT: eers is groter? JASON Hirsch: Ja. Ons kan net doen terwyl eindig groter is as die begin. Right. Ons het bygevoeg begin tot die ander kant van daardie, en ons het ontslae te raak van die 0. So dit lyk net 'n bietjie skoner. OK. So, terwyl die lengte van die lys is 0, ons geskryf dat, terwyl die einde is groter as die begin. Ons gaan sit in ons nodig krulhakies, en dan is die eerste ding wat ons wil doen, is om te kyk na hulle in 'n klein lys. Jy? Kan jy my die - STUDENT: Indien hakies waarde vierkante hakies - JASON Hirsch: As hakies waarde vierkante hakies. STUDENT: eers gedeel deur 2. JASON Hirsch: eers? STUDENT: Ek sien 'n probleem met jou - JASON Hirsch: OK. Wel, kyk na die middel. Hoe weet ons wat die middel is? Ja. So laat my wat die kode verwyder. Hoe weet ons wat die middel is? In niks nie, wanneer jy die begin en die einde, hoe kry jy die middel? STUDENT: Jy gemiddelde. STUDENT: Jy voeg dit saam en dan - JASON Hirsch: Voeg hulle saam en dan? STUDENT: En jy gemiddelde. Deel dit deur 2. JASON Hirsch: Voeg hulle bymekaar en deel deur 2. So int middel gelyk? Tom, kan jy dit vir my gee? STUDENT: Begin plus eindig - JASON Hirsch: Begin plus eindig. STUDENT: All, bracket, gedeel deur 2. JASON Hirsch: All, in hakies, gedeel deur 2. So wat gee my die middel enigiets, reg? STUDENT: Jy moet ook om dit te rond. JASON Hirsch: Wat doen jy bedoel, ek het dit nodig om rond? [INTERPOSING Voices] STUDENT: want as dit is 'n vreemde getal is, dan is dit soos - JASON Hirsch: Wel, OK. So ek dit kon aankeer. Maar as dit is 'n vreemde nommer, 'n 5, kan ek neem 1 weg van die middel. Of as dit 'n ewe getal, eerder, dit is 'n beter geval. As dit is 4, het ons net 4, kan ek die eerste "middel", quote, unquote of die tweede "middel" een. Óf sal werk vir 'n binêre soek, sodat ek nie eintlik nodig het om dit af te rond. Maar daar is een ander ding wat ek nodig het om te kyk na hierdie lyn. Ons kan nie besef dit nie, maar ons sal terug te kom dit. Omdat hierdie lyn eintlik nog moet 'n ander ding. Maar tot dusver, het ons geskryf vier reëls van die kode. Ons het ons begin en eindig merkers. Ons het ons lus, wat kaarte op direk aan ons pseudokode. Ons is op soek na die middel wat kaarte direk op ons pseudokode. Ek sou sê dit gaan om die middel van die lys, die reël van die kode. En dan, wanneer gaan ons na die middel van die lys, is die volgende ding wat ons nodig het om te doen is seker te maak dat ons waarde is daar vir die pseudokode ons geskryf vroeër. So hoe kan ons kyk of ons waarde is op die middel van die lys? Jy. Hoekom doen jy dit nie doen nie? STUDENT: As ons waarde se is teen die middel is gelyk aan alles wat ons die - Ek bedoel gelyk gelyk aan - JASON Hirsch: Dit - OK. STUDENT: Ek is nie seker wat die veranderlike wat ons soek Want al is, is omdat - [INTERPOSING Voices] STUDENT: [onhoorbaar]. JASON Hirsch: Presies. Per die funksie verklaring, Ons is op soek na 'n waarde. So ons is op soek na 'n waarde in 'n verskeidenheid van waardes. So jy is presies reg. Jy sal doen, as oop hakie waarde bracket middel gesluit bracket gelykes gelyk aan waarde, en binnekant is daar wat moet ons doen? As ons waarde is daar, wat ons nodig het om te doen? [INTERPOSING Voices] STUDENT: Terug nul. JASON Hirsch: Terug waar. STUDENT: Terug waar. JASON Hirsch: Michael, Wat beteken hierdie lyn te doen? STUDENT: [onhoorbaar] die program hardloop sy loop, en dit is verby, en jy het wat jy nodig het om te doen? JASON Hirsch: Die program, of wat? In hierdie geval? STUDENT: Die funksie. JASON Hirsch: Die funksie. En so, om terug te keer na wat genoem dit en gee dit die waarde, waar is. Presies reg. Main. Wat is die terugkeer tipe van die hoof, Michael? STUDENT: int, heelgetal? JASON Hirsch: int, presies. 'N heelgetal. Dit was net 'n kwessie om seker te maak julle ouens is op die top van dit. Wat beteken dit gewoonlik terugkeer, as alles goed werk? STUDENT: Zero. JASON Hirsch: Zero. Presies reg. STUDENT: Indien dit terug net waar, daar is geen inligting wat gegee oor wat die - Ag, dit is net te sê dat dit waarde is binne-in die skikking. JASON Hirsch: Presies. Hierdie program is nie inligting gee waar presies die waarde is. Dit is net te sê, ja, ons het dit of nie, ons het dit nie vind nie. So as nommer word, terug waar. Wel, eintlik het ons net gedoen het wat werklik vinnig met daardie een lyn van kode. So ek sal dat die lyn van pseudokode beweeg. STUDENT: Moenie ons nodig die skikking te verander? Dit moet waardes, nie waarde wees, reg? JASON Hirsch: Jammer. Dankie. STUDENT: Ja. JASON Hirsch: Hierdie lyn moet waardes. Presies reg. OK. Ons het dus in die middel lys. As aantal gevind terugkeer waar. Voortgesette op met ons pseudokode, indien middel is groter, soek gelaat. So het ek hier, as nommer hoër, soek gelaat. Konstantyn, kan jy gee my hierdie reël van die kode? STUDENT: Indien waarde van middel - JASON Hirsch: So as waarde - As oop hakie waardes bracket middel naby bracket - STUDENT: is kleiner as waarde? JASON Hirsch: minder as. STUDENT: Minder as waarde. JASON Hirsch: Waarde. Wel, eintlik, jy wil kyk of die nommer - Jammer. Dit is 'n bietjie verwarrend. Maar anders as die getal in die middel van die lys is groter. STUDENT: O, OK. JASON Hirsch: Ek sal dit verander nie. Anders as middel is hoër, ons wil soek links, OK? En wat doen ons binnekant hierdie Indien die toestand? STUDENT: Kan ek 'n klein verandering aan die toestand is, verander dit na else if? JASON Hirsch: want as? OK. So hierdie kode sal voer ongeveer dieselfde. Maar die lekker ding oor die gebruik indien anders Indien anders as, of indien, anders as, anders beteken dat slegs een van daardie gaan nagegaan word, nie al drie van hulle, potensieel. En dit maak dit 'n bietjie mooier op die rekenaar wat hardloop jou program. So [? Konstantyn,?] ons is in hierdie lyn, anders as waardes, bracket middel naby bracket is groter as waarde. Wat moet ons doen? Ons moet die links te soek. Hoe doen ons dit? Ek gaan vir jou 'n begin. Ons het hierdie twee dinge genoem begin en eindig. So, wat moet gebeur aan die begin? As jy wil die linkerkant van die te soek lys, kry ons ons huidige begin. Wat moet ons dit doen? STUDENT: Ons het die begin na die Midde-plus 1. JASON Hirsch: So as ons soek die linkerkant? STUDENT: Jammer, die Midde-minus - So het die einde middel sou wees minus 1 en begin - JASON Hirsch: En wat gebeur aan die begin? STUDENT: Dit bly dieselfde. JASON Hirsch: So het die betekenis bly dieselfde. As ons die linker op soek is, is ons gebruik dieselfde begin - presies reg. En die beëindiging van? Jammer, wat beteken die eindig weer gelyk? STUDENT: Midde-minus 1. JASON Hirsch: Midde-minus 1. Nou, hoekom minus 1, en nie net die middel? STUDENT: Die middel is uit die foto reeds, want ons het bewys dat dit uit? JASON Hirsch: Dis presies reg. Die middel is uit die prentjie. Ons het reeds nagegaan die middel. So ons wil nie "die middel," aanhaling unquote, om voort te gaan om te wees in die skikking wat ons soek. So dit is fantasties. Anders as waardes bracket middel is groter as waarde eindig gelykes middel minus 1. Jeff, wat oor hierdie laaste reël? STUDENT: anders. Waardes middel is minder as die waarde van? JASON Hirsch: Ons sal jy my gee anders. So as jy nie gee my nie - STUDENT: So dan begin sou middel plus 1 wees. JASON Hirsch: Begin gelykes Midde-plus 1, weer, vir dieselfde rede dat Konstantyn het ons vroeër. En aan die einde, het wat nie gegee my 'n reël van die kode nie? Terug valse, Aleha, wat nie hier skryf ons? STUDENT: Terug onwaar. JASON Hirsch: Terug onwaar. En ons moet dit te doen nie, want as ons nie vind nie, moet ons ons om te sê het dit nie vind nie. Maar ons het gesê ons gaan om terug te keer 'n Bool, so ons het beslis om terug te keer 'n Bool iewers. So laat ons gebruik hierdie kode. Ek is eintlik van plan om - so ons is in die terminale. Ons sal ons venster skoon te maak. Kom ons maak All. Ons het gevind dat daar 'n fout. Daar is 'n fout op die lyn 15, verwag kommapunt aan die einde van die verklaring. So, wat het ek vergeet? STUDENT: Flitser. JASON Hirsch: Flitser reg hier. Ek dink dit was Tom se kode. So Tom, [onhoorbaar]. Net 'n grap. Kom ons maak almal weer. STUDENT: Wat Dropbox gids moet ons in vir hierdie? JASON Hirsch: So jy kan net kyk vir hierdie bietjie. Maar weereens, as jy wou om dit te beweeg kode in jou pset3 gids om te probeer dit, dit is wat ek gedoen het. As jy hier sal sien - Jammer, goeie vraag. [? LS,?] Ek het hier die find.c kode uit hierdie week se distro kode. Ek het helpers.h. Ek het 'n make-lêer dat ek eintlik redakteur van 'n bietjie hierdie nuwe te sluit lêers wat ons wil skryf. Al wat die kode sal beskikbaar wees nie die verspreiding kode, maar die nuwe Maak lêer, die nuwe helpers.h lêer aanlyn beskikbaar vir aflaai. Weer, so dit is die ekstra kode wat ons het. So maak al, per hierdie lyn, maak vind, binêre, borrel seleksie - Maak al drie van hulle en stel in hierdie uitvoerbare kode te vind. So oor die algemeen, ons wil nie reguit te check50. Ons wil 'n paar toetse uit te voer op ons eie. Maar net so kan ons dit 'n bietjie vinniger, check50 2013 pset3.find sal slaag in helpers.c-- my sleg. Ek het nie dat die reg nou. So ons is eintlik gaan hardloop die kode vir die ware. Usage.find /, jy weet wat dit beteken? STUDENT: Jy moet 'n tweede command line op dit. JASON Hirsch: Ek moet 'n tweede opdrag lyn. En per die spesifikasie, ek moet te tree wat ons soek. So laat ons kyk vir 42. Ons sal dit hou in gesorteer omdat ons het nie 'n soort funksie geskryf nie - 42, 43, 44. En beheer D het nie die naald in die hooimied. Dit is sleg. Dit is beslis daar. Kom ons probeer iets anders. Miskien is dit omdat ek dit aan die begin. Kom ons doen 41, 42, 43. Daar gaan ons. Dit het dit gevind. Kom ons sit dit aan die einde nou, net sodat ons kan wees deeglike - 40, 41, 42. Het nie die naald. So Ek het dit vroeër. Ongelukkig het ek geweet dat dit gaan gebeur. Maar vir opvoedkundige doeleindes, dit is goed om dit te verken. Dit werk nie. Vir een of ander rede, kan dit nie vind nie. Ons weet wat is in daar, maar ons is nie om dit te. So een ding wat ons kan doen is om te gaan deur GDB om dit te vind, maar nie almal, sonder om deur GDB, het 'n gevoel van waar ons screwed up? [? Madu? ?] STUDENT: Ek dink dit kan word wanneer eindig is gelyk aan die begin, en dit is net 'n een-element lys. Dan is dit net ignoreer dit plaas van die werklikheid te keur nie. JASON Hirsch: Dis presies reg. Wanneer eindig gelyk begin, ons doen nog 'n element in ons lys? STUDENT: Ja. JASON Hirsch: Ja, in werklikheid, is ons een en slegs een element. En dit sal waarskynlik gebeur wanneer per die kode wat ons getoets het, ons is by die voorkant van die hooiberg of by die einde van die hooiberg. Dit is waar begin en einde gaan gelyke een, met binêre soek. So in daardie twee gevalle het dit nie werk nie, omdat eindig was gelyk aan die begin. Maar as die beëindiging is gelyk aan die begin, beteken dit terwyl lus voer? Dit maak nie. En ons kon nagegaan het wat weer deur GDB. So hoe kan ons dit regmaak kode, omdat toe, terwyl eindig is gelyk aan begin, ons wil ook hierdie while lus om te hardloop. So, wat fix kan ons te reël 18? STUDENT: [onhoorbaar] is groter as of gelyk aan. JASON Hirsch: Presies reg. Terwyl einde is groter as of gelyk aan begin. So nou, maak ons ​​seker dat te kry hoek geval aan die einde. En laat ons sien. Kom ons loop hierdie een meer tyd. Kom ons maak almal. Weer, moet jy net volg saam hier. Vind 41 hierdie tyd. Hou dit net konsekwent. Vind 42. Kom ons sit dit aan die begin - 42, 43, 44. Ons het dit gevind. So dit was inderdaad die verandering ons nodig het om te maak. Dit was 'n baie kodering ons net gedoen het, binêre soek. Het enige iemand enige vrae voor Ek beweeg in lyne wat ons geskryf het in binêre soek of hoe ons gedink uit te vind wat ons het uit te vind? Voordat ons beweeg, Ek wil ook om te wys dat deur en groot, ons gekarteer ons pseudo-kode om een ​​te een op ons kode. Ons het daardie moeilike ding om uit te vind met die begin en eindig. Maar het jy nie gedink dat uit, jy sou pretty much geskryf het die identiese kode, behalwe vir diegene top twee lyne. En dan sal jy besef het wanneer jy het dit in tjeks en gevalle wat moet jy iets anders. So selfs as jy gevolg het om ons pseudo-kode lyn tot lyn, sou jy het gekry almal maar twee lyne van kodeer wat jy nodig het om te skryf. En ek sou bereid wees om te wed dat julle sou al gedink dat uit redelik vinnig, wat jy nodig het om te sit 'n soort van merker in daar te vind uit te vind waar jy was. Dit weer, is die krag om dit te doen pseudo-kode voor die tyd. So kan ons die logika eerste te doen, en dan ons kan bekommerd wees oor die sintaksis. Het ons verward oor die logika terwyl hy probeer om die kode in C te skryf, ons sou gekry het al deurmekaar. En dan wil ons vrae vra oor logika en sintaksis en inkam hulle almal saam. En ons sou verlore geraak het in wat kan vinnig 'n baie moeilik probleem. So laat ons beweeg nou aan keuring soort. Ons het 20 minute oor. So ek het 'n gevoel ons sal nie in staat wees om te kry deur al seleksie soort en borrel soort. Maar laat ons ten minste n poging seleksie soort te voltooi. So implementeer seleksie soort gebruik van die volgende funksie verklaring. Weereens, dit uit die probleem stel spesifikasie. Int waardes is tussen hakies, is 'n skikking van heelgetalle. En int.n is die grootte van die skikking. Seleksie soort gaan hierdie skikking te sorteer. So per ons geestelike model van seleksie soort, ons trek die - eerste, ons gaan deur die lys van die eerste tyd, vind die kleinste getal, sit dit aan die begin, vind die tweede kleinste getal, sit dit in die tweede posisie as ons wil sorteer in stygende orde. Ek is nie dwing om te skryf pseudo-kode nou. Maar voor ons doen die kode as 'n klas in vyf minute, gaan ons om te skryf pseudo-kode, sodat ons 'n sekere sin van waar ons gaan. So probeer pseudo-kode te skryf op jou eie. En dan probeer om dit te draai pseudo-kode in die kode. Ons sal dit doen as 'n groep in vyf minute. En natuurlik, laat weet my as jy enige vrae het. Student: Daar is dit? JASON Hirsch: Sien hoe ver jy kan jy in twee minute. Ek verstaan ​​dat jy nie sal in staat wees om te voltooi. Maar ons gaan oor hierdie as 'n groep. Jy is al so kodering [onhoorbaar], so ek is jammer om te breek wat jy doen. Maar laat ons gaan deur middel van hierdie as 'n groep. En weer, binêre soek, het jy al gee my een indien nie meer reëls van die kode. Dankie vir daardie. Ons gaan dieselfde ding om te doen Hier kode saam as 'n groep. So seleksie soort - Ons skryf 'n paar vinnige pseudo-kode. Per geestelike model, kan iemand my die eerste lyn van pseudo-kode, asseblief? Wat wil ek doen? STUDENT: Terwyl die lys buite werking is. JASON Hirsch: OK, terwyl die lys is buite orde. En wat bedoel jy "buite orde?" STUDENT: Terwyl [onhoorbaar] is nie gesorteer. JASON Hirsch: Terwyl die lys buite werking is, wat doen ons? Gee my die tweede lyn, asseblief, Marcus. STUDENT: vind So die volgende kleinste getal. Dit sal ingekeep word. JASON Hirsch: So vind die volgende kleinste getal. En dan iemand anders? Sodra ons die volgende kleinste nommer, wat doen ons? Ek gaan om te sê vind die kleinste getal. Dit is wat ons wil doen. So vind die kleinste getal. Dan wat doen ons? STUDENT: [onhoorbaar] te begin. JASON Hirsch: Jammer? STUDENT: Plaas dit in die die begin van die lys. JASON Hirsch: So plaas dit in die begin van die lys. En wat doen ons om die ding dit was in die begin van die lys, reg? Ons is die vervang iets. So waar sit ons dit? Ja, Anna? STUDENT: Waar die kleinste getal was? JASON Hirshhorn: So sit die begin van die lys waar die kleinste getal is. Dus, terwyl die lys is buite werking is, vind die kleinste getal, plaas dit in die begin van die lys, sit die die begin van die lys waar die kleinste getal is. Marcus, kan jy herformuleer hierdie lyn terwyl die lys is buite orde? STUDENT: Terwyl die nommers is nie gesorteer? JASON Hirshhorn: OK, so in orde te weet dat die getalle het nie gesorteer, wat moet ons doen? Hoeveel moet ons gaan deur die lys? STUDENT: Ek dink 'n lus vir, of terwyl, terwyl getalle nagegaan is minder as die lengte van die lys? JASON Hirshhorn: OK, dit is goed. Ek dink ek misphrased my vraag swak. Ek het net probeer om te kry by ons gaan hê om te gaan deur die hele lys. Dus, terwyl die lys is buite orde, Vir my is dit moeilik om te kaart op. Maar basies, dit is hoe Ek dink hieroor. Gaan deur die hele lys, vind die kleinste getal, plaas dit in die begin - eintlik, jy is reg. Kom ons sit hulle albei. Dus, terwyl die lys is buite orde, ons nodig het om te gaan deur die hele lys een keer, vind die kleinste getal, plek dit in die begin van die lys, sit die begin van die lys waar die kleinste getal was, en dan as die lys is nog steeds buite werking, het ons het om te gaan deur middel van hierdie proses weer, reg? Dit is waarom seleksie soort, Big-O runtime van seleksie soort, enigiemand? STUDENT: n kwadraat. JASON Hirshhorn: n kwadraat. Want soos ek en Marcus net besef Hier gaan ons te hê gaan deur die lys lys aantal kere. So gaan deur iets van lengte n n aantal kere is in werklikheid n kwadraat. So dit is ons pseudokode. Dit lyk baie goed. Het enige iemand enige vrae oor die pseudokode? Want eintlik behoort seleksie soort waarskynlik kom 12:59, kode van pseudokode. So enige vrae oor die logika van die pseudokode? Vra dit nou. Seleksie soort - terwyl die lys is uit van orde, ons gaan om te gaan deur dit en vind die kleinste elke keer en sit dit in die voorkant. Dus, terwyl die lys is buite werking is, kan iemand gee my dat die lyn van die kode wat het nie, aan my gegee 'n lyn van die kode nie, asseblief? Dit klink soos 'n wat? Student: Daar is 'n lus vir. JASON Hirshhorn: Dit klink graag 'n lus vir. OK, kan jy gee my die lus? Vir - STUDENT: Ek gelyk aan 0. JASON Hirshhorn: i of - wat is ons ontbreek? Wat gaan hier? STUDENT: Int. JASON Hirshhorn: Presies. (Int i = 0; - STUDENT: Ek