JASON HIRSCHHORN: Welkom tot en met week drie, iedereen. We hebben een drukke maar boeiende sectie voor de boeg. Dus eerst, want we hebben een aantal gemaakt Vooruitgang boeken met de cursus, maar toch zijn we hebben veel van leren meer te doen, ik ben ga jullie laten zien wat middelen mocht blijken dat ongelooflijk zijn nuttig zijn als je niet alleen benaderen uw probleem stelt, maar ook verteren alle het materiaal geven we jullie in lezingen en borrels en sectie. Dan gaan we brengen de eerste 20 tot 25 minuten van de sectie gaan over GDB, die je wel of niet kan hebben die op dit punt, maar het is een ongelooflijk handig hulpmiddel dat zal helpen debuggen uw programma's. Veel van jullie hebben gebruikt printf in de midden van je programma te achterhalen wat een variabele geëvenaard. GDB is zelfs beter dan printf en niet verknallen uw code, omdat u draaien op een uitvoerbaar bestand. Dus gaan we over de 10 meest behulpzame opdrachten die u nodig hebt voor GDB, en we zijn ga op een oefening samen, zodat in probleem set drie en daarbuiten, u GDB kunnen gebruiken om te debuggen helpen uw programma's. En tot slot, we gaan gaan over een aantal sorteren en zoeken algoritmen die je zag in college, en we zijn gaat eigenlijk code, niet alleen pseudocode, maar code binair zoeken, bubble sort, en de selectie sorteren. Dus eerst, ik wil gaan over de middelen. Dit is een uitgebreide lijst, en het is kleiner lettertype want ik had een veel te passen op hier. Maar deze zal je niet alleen helpen, opnieuw het probleem sets en verteren informatie die u geleerd, maar zeker, kom quiz tijd, deze zal ongelooflijk nuttig. Dus eerst, de dictaten. Als je naar cs50.net/lectures en blader naar de specifieke week en dag, je zult zien dat er nota's voor elk lezing, die niet alleen een transcript, maar een bewerkte versie van wat in de lezing met code was bedekt fragmenten en andere handige weetjes. Ik beveel gaan over die. En dan ook, er is broncode verkrijgbaar bij elke lezing. En nogmaals, deze dia's ook online beschikbaar op cs50.net/sections deze avond. Dus tweede zijn de korte broek elke week dat worden onderwerpen, meestal 5-15 minuten. En die hopelijk zal u een geven grote primer op verschillende onderwerpen. Derde - en dit is gloednieuw dit jaar - is study.cs50.net. Als u niet uit te hebben ingecheckt, ik raden dat u dit doet. U krijgt om een ​​onderwerp te kiezen. We hebben tientallen onderwerpen op daar. Dus bijvoorbeeld, je kiest functies. Het geeft je een aantal dia's en merkt op functies. Dat zijn eigenlijk de dia's die TFs worden aangemoedigd om te gebruiken tijdens onze presentaties in paragraaf. Er is ook tips en trucs voor het omgaan met functies, en er is praktijk problemen die helpen je werkt met functies. Wij geven u ook links naar de kort op functies en tijden die functioneert hebben zich in collegezaal komen. Dus study.cs50.net, merk deze nieuwe jaar, een fantastische bron. Vervolgens Ik heb man, die de handleiding opdracht die u kunt uitvoeren op de opdrachtregel. Dus als je vragen hebt over een commando, bijvoorbeeld, rand, waarvan we ondervonden vorige week tijdens sectie en je hebt waarschijnlijk ondervonden bij uw probleem stellen wanneer gaan door de het genereren van code, maar als je man typt rand, vindt u de volledige pagina te krijgen dat vertelt je alles over rand. Het geeft je wat er nodig is, de parameters het duurt, evenals het rendement type en een korte beschrijving van die functie. Dus check rand. Het kan een beetje langdradig en verwarrend, dus soms vind ik dat gewoon Googlen wat ik wil weten is de beste manier om het antwoord te vinden. Dus oefen met Google. Krijgen goed in Google. Het zal uw beste vriend worden. Maar ook Google, als je het niet kunt vinden op Google, cs50.net/discuss, het is het discussieforum. De kans is groot als je een vraag hebt, een van uw 700 + collega's heeft ook dat vraag en kunnen hebben gevraagd reeds in het bespreken forums en hebben beantwoord. Dus als je een veel voorkomende vraag of heb je een vraag die je denkt misschien andere mensen misschien tegenkomen, check out cs50.net/discuss. Ten slotte is de laatste twee, als je wilt praten met een echt mens, kantoor Openingstijden Maandag tot en met vrijdag. Er is ook online spreekuur voor uitbreiding studenten. En last but zeker not least, me, uitroepteken. Jullie hebben allemaal mijn contactinformatie. Als je iets nodig hebt, neem dan nooit contact met mij op. Altijd voel vrij dit te doen. Zeer weinigen van jullie hebben me toegevoegd op Gchat, zodat teleurstellend is geweest, maar hopelijk dat zal veranderen tussen deze en de volgende sectie. Eventuele vragen tot nu toe op de middelen? Geweldig. Tot slot, een andere stekker voor feedback, sayat.me/cs50. Kunt u mij anoniem feedback over hoe ik doe. Dat was erg behulpzaam vorige week. Ik heb een paar opmerkingen van jullie direct na sectie, plus uit andere studenten die het schouwen tijdens de week, en het was ontzettend behulpzaam. Ik ga proberen en mijn gebruik van te beperken het woord "lief, 'maar ik zal laten zien mijn enthousiasme en opwinding op andere manieren. Maar er waren andere extra inhoudelijke feedback, zowel plussen en delta. Dus alstublieft, geef ik jullie feedback op uw probleem sets. Voel je vrij om me feedback te geven op mijn lesgeven. Ik ben hier voor jullie. Geweldig. Dat is alles wat ik heb voor het eerste deel. Heeft iemand enig vragen tot nu toe? En ik heb een briefje voor het controlecentrum. Uitbreiding studenten hebben me messaged zeggen dat ze krijgen geen audio, maar dat is niet in mijn macht ligt om te repareren. Dus hopelijk, dat krijgt binnenkort opgelost. Als je online kijkt, hi, maar je kunt me niet horen. Dus eerst gaan we te gaan door GDB. GDB, zoals ik zinspeelde op vroeger, is een debugging hulpmiddel veel beter dan printf. Dus aan de slag met GDB, jongens, als u wilt openen van uw toestel en neem het bestand dat ik naar u gemaild eerder - dit bestand zal ook online beschikbaar in een beetje - en uitvoeren GDB. / de naam van het bestand. De eerste, natuurlijk, je moet compileren file omdat GDB werkt alleen op uitvoerbare bestanden. Maar als je ooit wilt beginnen GDB, het eerste wat je doet, je loopt GDB. / Caesar. Dus dat is de naam van het programma dat we ga met het nu. Dus ik ga schrijven maken Caesar, die me een uitvoerbaar bestand zal geven hier groen gemarkeerd. En dan ga ik naar GDB. / Cesar draaien. En daar ga je. Je ziet hebben we wat tekst vertellen me over de versie van GDB, geeft me enkele garantie-informatie, en dan hebben we hebben het BBP prompt die soort ziet er van zoals onze opdrachtregelprompt, maar je ziet het is geopend Paren, GDB, dicht Paren. Voordat we verder gaan en te debuggen dit bestand dat ik tot u gezonden al, laten we eens kijken naar een aantal nuttige commando's dus hebben we een gevoel van wat we gaan dekken. Deze commando's worden hier vermeld in de volgorde waarin ik ze over het algemeen gebruik. Dus heb ik mijn programma te starten door het uitvoeren van GBD. / Naam van het programma, in dit geval, Caesar. En dan is het eerste wat ik doe 99,9% van de tijd wordt het type breuk betekenen. Dat zet een breakpoint op de belangrijkste. In wezen, wat je daar aan het doen bent wordt het programma gaat stoppen bij belangrijkste zodat u kunt beginnen de behandeling ervan lijn regel, in plaats van lopen de hele de weg door. U kunt op verschillende punten te breken in uw code, maar belangrijkste is over het algemeen een goede plek om te beginnen. Het volgende commando ik run is uitgevoerd. Dat begint het programma lopen en als je nodig hebt om command line in te voeren argumenten, je het uit te voeren die opdracht. Lopen met de argumenten. Dus omdat we gaan over een versie van C, dat is het programma dat jullie schreef voor PSET twee - deze, natuurlijk, heeft een aantal bugs in dat hopelijk vinden - we gaan run lopen met een aantal commando's line argumenten omdat Caesar, zoals jullie weten per het probleem set spec, kost wat command line argumenten. De komende paar commando's, de volgende een heet eigenlijk naast. Die ene neemt je regel voor regel via uw programma. Dus raken n Enter brengt u naar de volgende regel, het uitvoeren de vorige regel. Stap neemt u niet alleen om de volgende regel, maar het brengt u binnen functies. Dus als je een functie in hebben geschreven uw code of als u wilt verkennen een i, bijvoorbeeld, kan je raken s, en in plaats van naar de volgende regel het bestand dat je gaat door rechts nu, je zult daadwerkelijk de stap naar deze functie en bekijk de code. Lijst toont u, in zeer gebruiksvriendelijk formaat, de 10 of zo lijnen rond waar u op dit moment in code dus je kunt eigenlijk zien de file in plaats van terug te wisselen en weer tussen de verschillende weergaven. Print is als printf, zoals de naam impliceert. Dat laat je zien wat een variabele gelijk. Info locals is echt nuttig. Dit is een speciale versie van de prent. Info locals toont u alle lokale variabelen, drukt ze allemaal uit voor u die momenteel beschikbaar zijn. Dus ik over het algemeen, in plaats van te afdruk van de vier variabelen die ik ben nieuwsgierig als ik in een lus, voor Bijvoorbeeld, ik schrijf gewoon info locals, en het zal me wat mijn teller i tonen gelijk, evenals de array die ik werken op gelijken. Tot slot blijven. Typen pauze stopt u op het breekpunt. U kunt door lijn te lopen door overeenstemming met de volgende en stap. Ga verder loopt het programma naar uw volgende breekpunt of tot voltooiing indien er niet meer breekpunten. Disable verwijdert breekpunten als je besloten de rust in main was ongepast, je wilt zet deze ergens anders. En tenslotte q, stoppen, krijgt uit GDB. Dus dit programma. / Caesar, we gaan om te kijken door op dit moment en we gaan GDB gebruiken om te weten de bugs in dit programma. Ik liep dit programma eerder met Controleer 50, en ik heb er een frons. Alles wat het bestond, samengesteld, het langs een groot deel van de testen, maar voor een of andere reden, het niet de vijfde passeren test, draaien BARFOO, hoofdletters, in E-D-U-I-R-R, hoofdletters, met behulp van drie als een sleutel. Ik heb aardig in de buurt. Ik stapte uit een letter. Dus is er een aantal kleine fout in hier. Ik heb gekeken via mijn code. Ik kon er niet uit. Hopelijk kunnen jullie mij helpen erachter te komen wat deze bug is. Dus dat is de fout dat we zoekt. Laten we verhuizen naar GDB. Nogmaals, ik heb run GDB. / Caesar, dus nu zijn we in GDB. En wat is de eerste wat ik moet doen? Ik heb zojuist GDB. Iemand mij een goede commando te voeren. STUDENT: Break belangrijkste. JASON HIRSCHHORN: Break belangrijkste. Fantastisch. Laten we het type dat in Jullie kunnen hier kijken of volg mee op uw computers. Breek belangrijkste, en je ziet een breekpunt werd vastgesteld op - het geeft me een raar geheugen adres, en het geeft me ook het lijnnummer. Als ik terug kijk naar dit bestand, Ik wil dat de belangrijkste te realiseren gebeurde op lijn 21. Wat moet ik lopen langs? Wordt mijn programma draaien? Nee. Dus wat moet ik lopen de volgende stap? STUDENT: Run. JASON HIRSCHHORN: Run. Moet ik gewoon Run Run, of moet Ik een aantal andere dingen toe te voegen in? STUDENT: Run met het argument. JASON HIRSCHHORN: Run with het commando argumenten. En aangezien ik debuggen van een heel specifieke geval is, moet ik invoeren dat command line argument. Dus ik zal doen is het uitvoeren van drie, dat is, nogmaals, de uitgang kreeg ik van Check 50. Vanaf programma. We gaan door een paar regels. Je zult nu zien dat we op lijn 21. Hoe weet ik dat we op lijn 21? Want als je kijkt naar links van mijn terminal venster, er het zegt lijn 21. En dat geeft me, eigenlijk, de code die op lijn 21. Dus ik eerder versprak. Belangrijkste is eigenlijk niet op lijn 21. Belangrijkste is een paar lijnen boven 21. Maar op lijn 21, dat is waar we gaan uit elkaar. Deze regel code heeft nog niet uitgevoerd. Dat is belangrijk. De lijn die je ziet is niet Nog uitgevoerd. Dat is de volgende regel code je staat op het punt om uit te voeren. Dus de volgende regel, als jullie zijn waarschijnlijk bekend met, is dit toestand controleren om te zien of ik ging een command line argument. En een naar ik, wat is de tweede deel van dat te doen? Wat is een i? STUDENT: Veranderen naar een integer. JASON HIRSCHHORN: Sorry? STUDENT: Het verandert de argument naar een integer. JASON HIRSCHHORN: Dus een i verandert arg v1 van een string naar een integer. En wat is dan het controleren? STUDENT: Als er een tweede command line argument terzijde van het uitvoeren van het programma. JASON HIRSCHHORN: En wat is de tweede helft van dit Booleaanse expressie controleren? Dit deel hier, een i? STUDENT: Als het negatief. JASON HIRSCHHORN: Ervoor zorgen dat wat? STUDENT: Ervoor zorgen dat het is in feite positief. JASON HIRSCHHORN: Precies. Dit is te controleren om te zien of het negatief, en als het negatief, I heb het gevoel dat de volgende regel macht worden me schreeuwen tegen de gebruiker. Dus laten we hit einde aan deze lijn uit te voeren. We zien niet dat lijn die jullie misschien verwachtte te zien schreeuwen tegen de gebruiker en vervolgens terug te keren, omdat deze lijn niet uitgevoerd. Ik ging 3. Dus ik heb in feite voer twee commando line argumenten, en 3 is groter dan nul. Dus zagen we die lijn, we uitgevoerd, maar we hebben geen stap binnen het als voorwaarde. Dus nu, naast, ik zie ik ben het instellen int sleutel is gelijk aan een i arg v1. Dus dat is mij het creëren van een variabele sleutel. Dus als print ik sleutel nu, omdat die u toelaat om te zien de waarde binnen de variabele sleutel is gelijk aan 47. Dat is raar, maar natuurlijk, dat komt omdat ik niet nog uitgevoerd die lijn. Dus nu als ik hit n, uit te voeren die lijn, en doe druk toets, zal de sleutel gelijk 3, dat is wat we verwachten dat het gelijk. Dus nogmaals, in GDB, de lijn die u zie je nog niet uitgevoerd. Je moet raken n of s of een aantal andere opdrachten daadwerkelijk uitvoeren die lijn. Print sleutel. Key's op 3. So far, so good. String is platte tekst. Laten we voeren die lijn. Ik krijg een string van de gebruiker. Laten we eens kijken in mijn Controleer 50, I voer BARFOO alle kappen, dus dat is wat ik zal gaan. Als ik nu platte tekst af te drukken. Je zult zien dat het gelijk is aan een string. Het geeft me een aantal andere vreemde hexadecimale getal, maar wel in feit zeggen dat mijn string BARFOO. Als ik wilde zien wat de belangrijkste evenaarde op dit punt, hoe kan ik controleren sleutel? STUDENT: Print-toets. JASON HIRSCHHORN: Print-toets, precies. En eigenlijk is er een snelkoppeling. Als je moe van het typen afdruk te krijgen, je kan ook gewoon p. Dus p toets doet precies hetzelfde. En nogmaals, ik zie het gelijk aan 3. Als ik wilde weten wat zowel sleutel en BARFOO evenaarde tegelijkertijd maar ik was moe van het typen van elke een op individueel, ik info locals kon typen. Dat geeft me sleutel gelijken 3. Plain text gelijk BARFOO. Het geeft me ook deze twee rare dingen boven deze variabele i en deze variabele n. Die zijn werkelijk bestaande in mijn hoofdprogramma. We hebben ze nog niet tegengekomen, maar als een voorbeeld, die bestaan ​​in mijn lus. Dus nu, ze zijn gelijk een paar vreemde nummers omdat ze niet geweest nog geïnitialiseerd, maar ze bestaan ​​nog steeds in het geheugen, dus ze zijn gewoon ingesteld om wat vuilnis waarde. Maar verder zien we de sleutel in plain tekst daar. Dus ik ga deze lijn uit te voeren, lijn 34, de for-lus. We gaan om te springen in de lus door het raken van n. En we zijn in de lus. We zijn bij onze eerste check. En nogmaals, deze moet een soort van kijken u bekend voorkomen, want dit was een Caesar programma dat werd geschreven, maar weer, heeft een soort van bug. En als ik nu doe info locals, want ik ben binnen die voor de loop, zie je dat i gelijk is aan nul, omdat we verwachten. Dat is wat we het aan en geïnitialiseerd erop om in de lus. n gelijk aan 6. Dat is ook logisch, want we stellen het aan de strlen van platte tekst. Dus ik wil info locals of afdrukken doen variabele vaak om ervoor te zorgen dat alles is altijd wat Ik verwacht dat het gelijk. In dit geval, is alles wat ik verwacht dat het gelijk. Dus laten we beginnen met bewegen door deze for-lus. De lijn Ik ben op is lijn 36, als plain tekst i groter is dan een en effen tekst i kleiner is dan of gelijk aan z. Ik weet dat mijn probleem niet bij mijn eerste brief, het is met de tweede letter. Als we terugkijken op controleren 50, B gaat naar E prima. Ik neem de A en het verlaten van het als A, niet veranderen D. So er is iets mis met de tweede letter. Dus ik ga verhuizen er in een seconde. Maar als ik wil wat gewoon controleren tekst die ik geëvenaard in dit specifieke geval, ik denk dat het wat zijn? Wat moet platte tekst ik gelijk in deze eerste ronde door de lus? STUDENT: Zero? JASON HIRSCHHORN: Platte tekst van I? Dus het moet kapitaal B. zijn ik, natuurlijk, gelijk is aan nul, maar platte tekst beugel nul gesloten beugel gelijk aan B omdat strings, zoals we zagen vorige week, zijn array, dus we krijgen de eerste teken van dat. Dus nogmaals, als ik uitgeprint gewone tekst van Ik, ik weet het, in feite, krijgen het karakter B. En dat is netjes, toch? Ik heb niet echt platte tekst I. Dat is niet een van de variabelen I of geïnitialiseerd, maar u kunt afdrukken uit een hele reeks van dingen als je wilt. Maar laten we door gaan. Als platte tekst I is groter dan A en opmaak I kleiner is dan of gelijk aan Z, dat duidelijk is waar, want we hebben een hoofdletter B. Ik ga lopen een aantal commando's op. We zagen dat wiskunde vorige week, dus we zullen neem het voor lief dat het werkt recht volgens Controleer 50. Deze accolades, de eerste bleek dat ik was het verlaten van de als voorwaarde, de tweede toonde dat ik het verlaten van de lus. En dus nu wanneer ik raakte Vervolgens zien we wel zijn we terug bij de lus weer. We gaan door de lus weer. Laten we daadwerkelijk de stap naar de tweede iteratie van de lus en het type info locals. We zijn dus in de tweede iteratie van onze lus. I gelijk is aan 1, waarvan wij verwachten. N gelijk aan 6, waarvan wij verwachten. Sleutel is gelijk aan 3, waarvan wij verwachten. En platte tekst, zie je, gelijk EARFOO nu, niet meer BARFOO omdat in onze vorige iteratie, de B was veranderd in een hoofdletter E. Dus we zijn over het probleem zich voordoet, zodat deze is waar we gaan duik in het debuggen. Maar heeft iemand enig vragen over wat we tot nu toe gedaan? Fantastisch. Dus we gaan dit uitvoeren als staat, platte tekst beugel Ik sloot beugel groter dan A en platte tekst I minder dan of gelijk aan Z. Voordat Ik ga in dat, omdat dit is waar Ik weet dat mijn fout is, wil ik erop wijzen uit gewone tekst van I. So laten we uitprinten. Het doet gelijk het teken A, zodat lijkt zo ver, alles is goed en wel. Dus ik verwacht dat deze lijn per mijn logica, deze lijn moet waar zijn. Het is een hoofdletter. Maar als ik raakte n, we beseffen dat dit lijn, in feite, niet uitgevoerd. Ik sprong naar beneden naar de else if. Waarom gebeurde dat? STUDENT: Omdat je je conditie van platte tekst is groter dan A, niet gelijk aan of groter dan. JASON HIRSCHHORN: Dus ik had mijn platte tekst I groter is dan A, niet meer hoogste. Zo duidelijk, de hoofdstad A niet triggeren dit als voorwaarde, en dat deden we Stap niet in, en we deden de noodzakelijke verschuiving niet. Dus dat is het eigenlijk. Ik dacht dat mijn bug. Ik zou terug gaan in mijn bronbestand, veranderen, en te actualiseren en run Controleer 50 opnieuw. Maar we zullen zien, gewoon voor pedagogiek's sake, als ik ga door. De anders als niet uitvoeren hetzij, maar wat in plaats daarvan gelijk is het commando dat verandert niet. Dus het is helemaal niet veranderd, en als ik drukken hier platte tekst, we zullen zien gaan door die lus niet in feite veranderen dat tweede teken helemaal. Het is nog steeds een grote K Dus nogmaals, we debugged onze fout. We realiseerden ons dat er was enige logica ontbreekt. En we debugged het van tevoren voor daadwerkelijk uitvoeren van die lijn, maar je zou hebben gemerkt hadden we net hit Volgende en naar die anders als, dat betekent dat dat als voorwaarde was niet waar. We hebben niet, in feite, krijgen het resultaat dat we verwacht hadden. Dus dan kunnen we zijn gevraagd, had we niet zo slim geweest, om te kijken naar dat als voorwaarde en controleer of, in feite, onze toestand moeten evalueren om te waar in de huidige context. Dat is alles voor het debuggen van dit programma. Heeft iemand nog vragen? Welk commando zou ik raakte te stoppen GDB? Q. En dan zal ik gevraagd, stoppen eigenlijk? Ja of nee. Ik raakte ja, en ik zal stoppen met GDB. Dus dat was een snelle primer aan GDB. Eigenlijk, in een echte scenario Ik deed dit op kantooruren. Ik GDBed exact dit programma op kantooruren met een student. En als we terug gaan naar de commando's die we zagen vóór, gebruikten we pauze belangrijkste, eerste wat we deden. We gebruikten run met command line argumenten, tweede wat we deden. We gebruikten naast veel te bewegen ons door lijnen. En nogmaals, de korte versie van de volgende is n. Dat is in de tussen haakjes in grijs op de dia. We hadden geen stap te gebruiken, maar we hebben niet noodzakelijkerwijs voor dit geval. Maar we kunnen het later te gebruiken in een beetje op vandaag als we debuggen, voor bijvoorbeeld binair zoeken wanneer binaire zoeken wordt genoemd in een aparte functie, maar er is een fout mee. We gaan willen de stap naar de oproep om binary search en eigenlijk debuggen. Lijst we niet gebruiken, hetzij omdat we hadden een goed gevoel voor onze code, maar als ik wilde wel een gevoel van wat code die ik krijg was rond, kon ik gewoon gebruik maken van de lijst. Print we gebruikten, info locals we gebruikten. Blijven we niet nodig om te gebruiken in deze geval, wij hebben geen behoefte om te gebruiken uitschakelen, maar we hebben gebruik stoppen. Nogmaals, deze 10 commando's, oefen ze. Als u begrijpt deze 10 commando's, moet u worden ingesteld voor het debuggen van elke geven met GDB. Dus we staan ​​op het punt te gaan, opnieuw, aan de crux van sectie vandaag, gaan over deze sorteren en zoeken algoritmen. Voordat we dat doen, nogmaals, nog vragen, commentaar, zorgen voor GDB? Dus is iedereen gaat gebruiken GDB plaats van printf? Dus iedereen, omwille van de eeuwigheid is, iedereen knikt hun hoofd recht nu, dus ik zie je op het kantoor uren en alle TFs zullen u en zien zullen ze zeggen, toon me hoe te gebruiken GDB, en je zult in staat zijn om te laten zien, toch? Soort? Misschien hopelijk. Cool. Dus we gaan verhuizen naar sorteren en zoeken. Je ziet ik heb een lijst al naargelang voor ons, maar dat is niet van plan het geval altijd. Dus in het probleem te stellen specificatie voor probleem set drie, heb je korte broek dat je daadwerkelijk kunt kijken, en het vraagt ​​u om deze korte broek te kijken. Ook in college vorige week, gingen we veel van deze algoritmen, dus ik ben niet van plan om tijd te besteden in de klas te gaan dan deze algoritmen opnieuw of tekening foto's voor hoe deze algoritmen werken. Nogmaals, deze informatie kunt u re-watch lezing, of die informatie is uitstekend gevangen op de korte broek voor deze zoekopdrachten allemaal die beschikbaar zijn op cs50.net. Dus in plaats daarvan, wat we gaan doen is het schrijven van deze programma's. We hebben een gevoel, een mentaal model, hoe ze werken, en dus wat we gaan te doen is de code voor hen echt. We gaan dat mentaal model draaien, dat beeld, zo u wilt, in de eigenlijke code. En als je een beetje in de war of wazige op het mentale model, ben ik het helemaal begrijpen. We zijn eigenlijk niet van plan om spring naar code meteen. Dus terwijl deze prompt in deze dia vraagt u binary search te coderen, en eigenlijk een iteratieve versie binary search, het eerste wat ik echt wil dat je doet is schrijf een aantal pseudocode. Dus je hebt dit mentaal model hoe binary search werkt. Neem een ​​vel papier als u een direct beschikbaar, of het openen van een tekstverwerker, en ik wil graag iedereen om te schrijven. Neem vier minuten om te schrijven de pseudocode voor binaire zoeken. Nogmaals, na te denken over dat mentaal model. Ik zal rond komen als je vragen hebt en we kunnen het beeld trekken uit. Maar eerst, voordat we beginnen programmeren, Ik zou willen schrijven de pseudocode voor binaire zoeken dus toen we duiken, hebben we enkele richting naar waar we moeten het hoofd. STUDENT: Kunnen we aannemen dat de reeks van waarden die we krijgen is al gesorteerd? JASON HIRSCHHORN: Dus voor binary search om te werken - uitstekende vraag - je moeten nemen in een gesorteerde matrix met waarden. Dus neem aan dat het zal werken. We komen terug naar deze dia te gaan. Je ziet in het paars de functie verklaring is bool binary_search int waarde, int waarden, int n. Dit zal geen groot probleem als je hebt al benaderd of gekregen van uw handen vuil met het probleem set. Maar dat is uw functie verklaring. Nogmaals, geen zorgen te maken over dat veel op dit moment. Wat ik echt wil dat je doet is nemen vier minuten pseudocode binaire zoeken, en dan gaan we over die als groep. En ik zal rond te komen. Als u vragen hebt, voel vrij om uw hand op te steken. Waarom ga je niet nog twee minuten duren tot het einde van de pseudocode? Ik weet dat dit lijkt misschien belachelijk dat we zo veel tijd op iets dat niet eens echt in C, maar vooral voor deze meer uitdagend algoritmen en probleem sets die we moeten uitzoeken, te beginnen in pseudocode niet zorgwekkend over de syntaxis, maar zorgen te maken over de logica, is ongelooflijk behulpzaam. En op die manier, je bent niet het oplossen van twee ongelooflijk moeilijke problemen in een keer. Je bent gewoon focussen op de logica en verplaats je in de syntaxis. OK. Laten we beginnen met het doornemen van de pseudocode. Ik heb hier geschreven, binaire zoeken pseudocode. We zullen dit schrijven op de boord samen. Of ik zal het schrijven en je zult geven me de aanwijzingen ik nodig heb. Dus kan iemand mij de eerste lijn van de pseudocode u schreef voor binaire zoeken? Ja, Annie? STUDENT: Terwijl de lengte van de lijst groter is dan nul. JASON HIRSCHHORN: Terwijl lengte Lijst van groter dan nul. En nogmaals, zien we een aantal C-looking syntactische dingen op hier. Maar de meeste van deze is in het Engels. Heeft iemand enig lijn zetten ze voordat deze in hun pseudo-code? STUDENT: Haal een array Uitvoering van het gesorteerde nummers. JASON HIRSCHHORN: Je schreef "krijgt een reeks gesorteerde getallen. "Per de functie verklaring, zullen we overgaan een reeks getallen gesorteerd. STUDENT: [onverstaanbaar]. JASON HIRSCHHORN: Dus zullen we dat. Maar ja, als we niet hebben dat we nodig zou hebben om ons aanbod aan te sorteren aantallen, omdat binary search werkt alleen op gesorteerd arrays. Dus terwijl de lengte van de lijst gelijk is aan nul, ik ben gaat in sommige accolades te zetten zodat het lijkt een beetje meer op C. Maar terwijl, lijkt in kaart op een while loop, dus binnen dit terwijl lus wat hebben we nodig om doen voor binaire zoeken? Iemand anders die heeft mij niet een gegeven nog beantwoorden, maar die dit schreef? STUDENT: Ga naar het midden van de lijst. JASON HIRSCHHORN: Tom. Ga naar het midden van de lijst. En de follow-up vraag, wat doen we als we eenmaal op de midden van de lijst? STUDENT: Doe een check of dat nu het nummer dat u zoekt. JASON HIRSCHHORN: Excellent. Ga het midden van de lijst en controleer als onze waarde is er - fantastisch. Heeft iemand nog iets anders dat was anders dan dit? Zo is het precies. Het eerste wat we doen in binary search is naar het midden van de lijst en controleren om te zien of onze waarde is er. Dus ik neem aan dat als onze waarde is er, wat doen we? STUDENT: We nul [onverstaanbaar] terug. JASON HIRSCHHORN: Ja, als onze waarde is er, we vonden het. Dus we kunnen een of andere manier te vertellen, maar dit functie wordt gedefinieerd, we de gebruiker vertellen we vonden het. Als het er niet is, hoewel, dat is waar dit wordt lastig. Dus als het er niet is, iemand anders die werkte aan binary search of heeft een idee nu, wat doen we? STUDENT: Vraag. JASON HIRSCHHORN: Ja? STUDENT: Is de array al gesorteerd? JASON HIRSCHHORN: Ja, we gaan ervan uit de array is al gesorteerd. STUDENT: Dus dan moet u controleren of de waarde die je ziet is groter dan de waarde die u wilt, kunt u naar naar het midden van de andere helft. JASON HIRSCHHORN: Dus als het midden van de lijst is groter dan wat we zoekt, dan doen we wat? We gaan waar? STUDENT: U wilt verplaatsen naar de helft van de lijst met aantallen lager dan dat. JASON HIRSCHHORN: Dus we noemen links. Dus als middelste groter is, kunnen we zoeken de linker helft van de lijst. En dan met zoeken, wat bedoel ik met zoeken? STUDENT: [onverstaanbaar]. JASON HIRSCHHORN: We gaan naar het midden. We eigenlijk herhaal dit ding. We gaan terug via onze while lus. Ik zal u de laatste te geven - anders, als, midden is minder dan wat we, wat doen we hier doen? STUDENT: Ga naar rechts. JASON HIRSCHHORN: Zoek de juiste. Dit ziet er goed uit, maar heeft iemand iets dat we kunnen ontbreken of iets anders dat je in uw pseudo-code? Dus dit is wat we tot nu toe. Hoewel de lengte van de lijst groter dan nul, we gaan om te gaan naar het midden van de lijst en controleren of onze waarde is er. Als het middelste groter is, gaan we zoeken naar links, anders als het midden is minder, gaan we naar rechts zoeken. Dus we hebben allemaal wel enige vertrouwdheid met de termen die we gebruiken in de informatica en de instrumenten die we hebben. Maar je zult al merken we waren spreken in het Engels, maar we vonden een veel dingen die leek in kaart aan Tools hebben we in onze codering tool kit. Dus recht uit de vleermuis, zijn we niet gaat toch echt te coderen. Wat zien we hier in het Engels dat de kaarten op dingen die we kunnen schrijven in C? STUDENT: Hoewel. JASON HIRSCHHORN: Hoewel. Dus dit terwijl hier kaarten aan wat? STUDENT: Een tijdje lus. JASON HIRSCHHORN: Een tijdje lus? Of misschien meer algemeen een lus. We willen over en iets doen. Dus we gaan om een ​​lus te coderen. En we al weten, want we hebben gedaan dit een paar keer en we hebben genoeg voorbeelden die er zijn, hoe eigenlijk om te schrijven deze index voor een lus. Dus dat zou vrij gemakkelijk zijn. We moeten in staat zijn om dat te krijgen begon vrij snel. Wat hebben we hier? Welke andere structuren syntaxis, dingen dat we kennen in C, doen we al een gevoel van Based af van de woorden die we gebruiken? Ja, Anna? [Onverstaanbaar] just kidding. Anna, ga je gang. STUDENT: Indien en anders. JASON HIRSCHHORN: Indien en anders - hier. Dus wat doen die eruit? STUDENT: Een als else statement. JASON HIRSCHHORN: Ja, omstandigheden, toch? Dus zullen we waarschijnlijk moeten schrijf een aantal voorwaarden. En nogmaals, hoewel misschien verwarrend eerste, we hebben over het algemeen een gevoel nu hoe aan voorwaarden en schrijven de syntaxis voor de voorwaarden. En als we dat niet doen, we kijken net op de syntax voor de voorwaarden, knippen en plakken dat, omdat we weten dat we moet hier een voorwaarde. Iedere andere dingen zien we dat de kaart op dingen die we zouden moeten doen in C? Ja, Aleha? STUDENT: Dit zou duidelijk moeten zijn, door gewoon te controleren of een waarde is gelijk aan iets. JASON HIRSCHHORN: Dus hoe kunnen we controleren en - dus ga naar het midden van de lijst en controleer of onze waarde is er? Hoe doen we dat in C? Wat is de syntax voor dat? STUDENT: evenaart, evenaart. JASON HIRSCHHORN: gelijk, gelijk. Dus deze controle gaat waarschijnlijk een gelijken zijn, gelijken. Dus we weten dat we dat ergens nodig hebben. En eigenlijk, alleen in het schrijven ervan, zien we die andere dingen. We gaan te hebben om wat te doen vergelijkingsoperators daar - fantastisch. Dus het daadwerkelijk uitziet, door en groot, hebben wij niet geschreven woord van C-code nog. Maar we hebben het mentale model naar beneden via lezingen en die korte broek. We schreven pseudo-code als een groep. En al hebben we 80% indien niet 90% van wat we moeten doen. Nu, we hoeven alleen maar te coderen het, die weer is een niet-triviaal probleem op te lossen. Maar we zitten vast op de logica. Ten nu tenminste als we naar de kantooruren, Ik kan zeggen, ik weet wat ik nodig heb te doen, maar kunt u eraan herinneren me van de syntax? Of zelfs als kantooruren zijn overvol, je kan Google voor de syntaxis, in plaats dan vast te zitten op de logica. En nogmaals, in plaats van te proberen op te lossen de logica en de syntaxis van alle problemen tegelijkertijd is het vaak veel beter breken die twee harde problemen af ​​in twee meer beheersbaar enen en doe de pseudo-code en vervolgens code in C. Dus laten we eens kijken wat ik deed voor de pseudo-code van tevoren. Hoewel de lengte van de lijst groter dan nul, kijk naar het midden van de lijst. Als nummer gevonden waar is, anders terug als getal hoger, zoeken links. Anders als nummer lager, zoeken rechts, return false. Dus dat ziet er bijna identiek als niet bijna identiek aan wat we schreven. Eigenlijk, Tom, wat je eerst zei, breken het midden van de lijst en als nummer gevonden in twee uitspraken is eigenlijk wat ik deed. Ik combineerde ze daar. Ik had naar heb geluisterd je de eerste keer. Dus dat is de pseudo-code die we hebben. Als u wilt nu, sorry, ga terug naar onze oorspronkelijke probleem. Laten code binary.c. Dus uitvoering van een iteratieve versie binair zoeken met de volgende functie verklaring. En je hoeft niet te kopiëren het naar beneden gewoon nog niet. Ik ben eigenlijk van plan om te openen up hier binary.c. Dus daar is de functie declaratie in het midden van het scherm. En je zult zien dat ik nam de pseudo-code uit op mijn kanten, maar bijna identiek tot wat wij schreven, en we deze in voor u. Dus nu, laten we eens vijf minuten Om deze functie te coderen. En nogmaals, als je vragen hebt, steek je hand, laat het me weten, ik zal komen rond. STUDENT: [onverstaanbaar]. JASON HIRSCHHORN: Dus nam ik de binaire zoeken definitie bij de top, op lijn 12. Dat is wat ik kreeg voor mijn dia. En dan al die pseudo-code die ik net kopiëren en plakken van de glijbaan, pseudo-code glijbaan. Ik ben nog steeds niet horen van [onverstaanbaar]. Dus als je klaar bent met uw implementatie, Ik wil om het te controleren. Ik e-mailde de helpers.h bestand eerder in deze klasse. En het zal online beschikbaar zijn en om te downloaden voor mensen kijken deze paragraaf tijd vertraagd. En ik gebruikte de generieke distributie code van pset3. Dus nam ik status van huidige map, gebruik mijn helpers.h bestand in plaats van de helpers.h bestand dat is opgenomen in de verdeelsleutel. En ik moest een andere verandering in maken status van huidige map in plaats van te bellen gewoon zoeken, bel binary_search. Dus als u wilt uw code te testen, weten dat dat is hoe het te doen. In feite, wanneer we zullen u deze code nu, ik heb net een kopie van gemaakt mijn pset3 directory, weer, geswapt de helpers bestanden en maakte vervolgens dat verandering in status van huidige map te binary_search bellen in plaats van simpelweg te zoeken. JASON HIRSCHHORN: Ja. U heeft een vraag? STUDENT: Nevermind. JASON HIRSCHHORN: Geen zorgen. Nou, laten we beginnen. We zullen deze code als een groep. Een andere opmerking. Ook dit kan gemakkelijk worden verwisseld voor Probleemverzameling Drie. Ik heb mijn helpers.h bestand dat, in plaats dan de helpers.h ons gegeven, verklaart binary search, bel sorteren en selectie sorteren. En in de status van huidige map zul je merken op de lijn, wat is dat, lijn 68, binaire noemen we zoeken in plaats van zoeken. Dus nogmaals, de code die beschikbaar is online of de code die u bent nu maken kan eenvoudig worden verwisseld voor p set 3 om het te controleren. Maar laten we eerst coderen binary search. Onze functie verklaring, we terug een bool. We nemen een integer genaamd waarde. We nemen een array van gehele getallen genoemd waarden, en we nemen n zijn de grootte van de matrix. Op lijn 10, hier heb ik scherpe omvatten stdbool.h. Weet iemand waarom dat is daar? Dus wat betekent dat regel code doen? STUDENT: Hiermee kunt u een type bool return. JASON HIRSCHHORN: Precies. STUDENT: Of het is een bibliotheek die het mogelijk maakt met een type bool return gebruiken. JASON HIRSCHHORN: Dus de scherpe omvatten stdbool.h lijn geeft me wat definities en verklaringen voor dingen dat ik mag gebruiken in deze bibliotheek. Dus onder hen zegt dat er dergelijke genoemd bool, en het kan waar of onwaar. Dus dat is wat die lijn doet. En als ik niet heb die lijn, zou ik in de problemen voor het schrijven van deze woord hier, bool, daar. Precies goed. Dus ik moet dat in deze code. OK. Dus dit, nogmaals, is een iteratief versie niet recursieve een. Dus laten we aan de slag. Laten we beginnen met deze eerste lijn van pseudo-code. En hopelijk zullen we - of niet hoopvol. We gaan naar de kamer rond. We gaan regel voor regel, en ik zal helpen u achterhalen van de lijn die we nodig hebben om eerst te schrijven. Dus terwijl de lengte van de lijst groter is dan nul. Laten we beginnen aan de voorkant. Welke lijn moet ik schrijven hier, in code? STUDENT: Terwijl haakjes n is groter dan 0. JASON HIRSCHHORN: Terwijl n groot is dan 0. Zo n is de grootte van een lijst en we controleren of - [Onderbreekt hem VOICES] JASON HIRSCHHORN: - sorry? STUDENT: Hoe weten we dat n is de grootte van de lijst? JASON HIRSCHHORN: Sorry. Per de PSET specificatie, het zoeken en soort functies die u nodig hebt om te schrijven, n is de grootte van de lijst. Ik vergat om hier uit te leggen dat. Maar ja. n is de grootte van de lijst, in dit geval. Dus terwijl n groter is dan 0. OK. Dat kan blijken een beetje problematisch hoewel, als de dingen gaan. Omdat we zullen blijven om te weten de grootte van de lijst in deze functie, maar zeggen dat we beginnen met een serie van 5 integers. En we gaan door en we hebben nu deze beperkt tot de een array van 2 gehele getallen. Die 2 getallen is dat? De grootte is 2 nu dat we willen naar te kijken, maar die 2 is dat? Maakt dat gevoel, dat vraag? OK. Ik zal het nog eens vragen. Dus we beginnen met deze serie van 5 gehele getallen, en n gelijk is aan 5, toch? We zullen lopen door hier. we zullen waarschijnlijk de grootte veranderen, recht, zoals de zaken gaan. Dat is wat we zeggen dat we willen doen. We willen niet zoeken opnieuw de volledige ding. Dat zeggen wij veranderen naar 2. We nemen de helft van de lijst die is vreemd. Dus kies gewoon 2. Dus nu n gelijk is aan 2. Ik verontschuldig me voor de armen droog uitwisbare markers. Rechts? En we zoekt in de lijst opnieuw met een lijst van maat 2. Nou, ons aanbod is nog steeds van maat 5. We zeggen dat we alleen maar willen zoeken 2 plekken in het. Dus die 2 plekken zijn dat? Is dat logisch? Zijn ze de linker 2 vlekken? Zijn ze de juiste 2 vlekken? Zijn ze de middelste 2 vlekken? We hebben het probleem afgebroken, maar we eigenlijk niet weten welk deel van het probleem dat we nog steeds op zoek naar, gewoon door het hebben van deze 2 variabelen. Dus hebben we een beetje hebben meer dan, terwijl n groter is dan 0. We moeten weten waar dat n is in onze huidige array. Dus heeft iemand een veranderen met de lijn? De meeste van deze lijn is volkomen juist. Is er een andere toevoeging? Kunnen we iets voor n swappen maken deze lijn een beetje beter? Mm-hm? STUDENT: Kan je een variabele initialiseren zoals lengte n dat dan zal worden gebruikt later in de functie? JASON HIRSCHHORN: Dus initialiseren een variabele lengte n, en we dat later gebruiken? Maar dan zijn we gewoon updaten lengte en we nog tegenkomen dit probleem waar we het kappen van de lengte van ons probleem, maar we weten nooit waar, eigenlijk, die lengte kaarten op. STUDENT: Is dat niet gaat gebeuren later, als je zegt, zoek links, zoeken toch? Je gaat naar een andere gebied van uw - JASON HIRSCHHORN: We gaan om te gaan naar een gebied, maar hoe weten we die moeten gaan? Als we alleen de array en deze n, hoe weten we waar te gaan in de array. In de rug, ja? STUDENT: Hebt u, zoals een lagere gebonden en een bovengrens variabele of zoiets? JASON HIRSCHHORN: OK. Dus dit is een ander idee. In plaats van alleen het bijhouden van de grootte, houden we van de onderste en bovengrens variabele. Dus hoe kunnen we berekenen van de grootte van een ondergrens en bovengrens? [Onderbreekt hem VOICES] JASON HIRSCHHORN: Aftrekken. En ook het bijhouden van de lagere gebonden en bovengrens te laten weten, zoeken we deze twee? Zoeken we deze twee hier? Zoeken we de middelste twee? Waarschijnlijk niet de middelste twee, omdat dit, in feite, is binair zoeken. Maar nu zullen we in staat zijn om de maat te krijgen, maar ook de beperkingen van de array. In essentie, als we onze reus telefoonboek, scheuren we het in tweeën. We weten nu waar dat kleinere telefoonboek is. Maar we zijn niet echt rippen het telefoonboek in de helft. We moeten nog steeds weten waar de nieuwe grenzen van ons probleem is. Heeft iemand enig vragen over dat? Ja? STUDENT: Zou het werken door het creëren van een variabele, ik, dat je dan gewoon verschuiven de positie van i ten opzichte van de huidige positie, en de lengte, n? JASON HIRSCHHORN: En wat is i? STUDENT: Zoals ik het zijn als soort - Zoals je zou initialiseren i om het te middenpositie van de array. En dan, als de waarde op positie i in het midden van de array gevonden lager zijn dan de waarde die u nodig hebt, ik nu wordt de lengte van de array, plus de waarde van i gedeeld door 2. Zoals, zie, je shift i - JASON HIRSCHHORN: Juist. STUDENT: - tot de - JASON HIRSCHHORN: Dus ik ben er bijna positief dat zal werken. Maar het punt is, twee moet u stukjes informatie hier. U kunt dit doen met begin en einde, of je kunt het doen met de grootte, en vervolgens sommige marker. Maar je moet twee stukken van hier informatie. Je kunt niet krijgen door met slechts een. Is dat zinvol? Dus we gaan door te gaan, en we gaan doen [onverstaanbaar] en maak een aantal markers. Wat heb je schrijft in je code? STUDENT: Ik heb net gezegd int gebonden een is gelijk aan 0. JASON HIRSCHHORN: Laten we noemen dat int, te beginnen. STUDENT: OK. JASON HIRSCHHORN: Dat maakt meer zin voor mij. En? STUDENT: Ik zei, denk ik, int einde. JASON HIRSCHHORN: int einde. STUDENT: Ik denk, n minus 1, of iets dergelijks. Zoals, het laatste element. JASON HIRSCHHORN: Dus je schreef, int begin gelijken 0, puntkomma, en int einde is gelijk aan n minus 1, puntkomma. Dus in wezen, wat wij doen hier, 0 de eerste positie. En zoals we weten in arrays, gaan ze niet naar tot n, ze gaan naar n minus 1. Dus hebben we een aantal grenzen van ons aanbod. En deze begingrenzen toevallig de oorspronkelijke grenzen van ons probleem. OK. Dus dat klinkt goed. Dan als we terug gaan naar deze lijn, terwijl lengte van de lijst groter is dan 0, welke plaats van n, moet we hier? STUDENT: Schrijf eind minus begin. JASON HIRSCHHORN: Terwijl eind minus begin groter is dan 0? OK. En we konden, als we wilden maken dat een beetje mooier, wat anders kunnen we doen? Als we wilden schoon deze code een beetje? Hoe kunnen we ons bevrijden van de 0? Dit is slechts een kwestie stijl. Het is nu correct. STUDENT: Ending niet gelijk begin? JASON HIRSCHHORN: Wij kunnen wat doen? [Onderbreekt hem VOICES] STUDENT: Ending is groter? JASON HIRSCHHORN: Yeah. We kunnen gewoon doen terwijl het beëindigen groter dan begin. Rechts. Wij voegden beginnen de overkant van dat, en wij verlost van de 0. Dus dit ziet er gewoon een beetje schoner. OK. Dus, terwijl de lengte van de lijst is 0, we schreven dat, terwijl het beëindigen groter dan beginnen. We gaan in onze noodzakelijke te zetten accolades, en dan is het eerste wat we willen doen is kijken naar ze in een lijstje. U? Kunt u mij de - STUDENT: Indien haakjes waarde vierkante haak - JASON HIRSCHHORN: Indien haakjes waarde vierkant haakje. STUDENT: eerst gedeeld door 2. JASON HIRSCHHORN: Ending? STUDENT: Ik zie een probleem met uw - JASON HIRSCHHORN: OK. Nou, kijk naar het midden. Hoe weten we wat het midden is? Yeah. Dus laat ik die code verwijderen. Hoe weten we wat het midden is? In alles, als je het begin en het einde, hoe vind je het midden? STUDENT: U gemiddeld. STUDENT: U voegt ze samen en dan - JASON HIRSCHHORN: Voeg ze toe samen en dan? STUDENT: En u gemiddeld. Delen door 2. JASON HIRSCHHORN: Voeg ze toe samen en delen door 2. Dus int midden gelijk? Tom, kan je het aan mij? STUDENT: Beginning plus eindigt - JASON HIRSCHHORN: Begin plus eindigen. STUDENT: Alle, beugel, gedeeld door 2. JASON HIRSCHHORN: Alle, tussen haakjes, gedeeld door 2. Dus dat geeft mij het midden van iets, corrigeren? STUDENT: Je moet ook om het te ronden. JASON HIRSCHHORN: Wat doe je bedoel, ik moet het naar boven afronden? [Onderbreekt hem VOICES] STUDENT: want als het een oneven nummer, dan is het net - JASON HIRSCHHORN: Nou, OK. Dus kon ik het naar boven afronden. Maar als het een oneven getal, een 5, ik kan het nemen van 1 weg van het midden. Of als het een even getal, plaats, dat is een betere zaak. Als het 4 hebben we maar 4, kan ik de eerste "midden", citaat, unquote of de tweede "middelste" een. Ofwel zou werken voor een binary search, zodat ik niet echt nodig om het te ronden. Maar er is een ander ding dat ik moeten kijken naar deze lijn. We zouden nog niet beseffen, maar we zullen terug te komen. Omdat deze lijn eigenlijk nog moet een ander ding. Maar tot nu toe, we hebben geschreven vier regels code. We hebben ons begin kreeg en eindigend markers. Wij hebben onze while lus, die kaarten op direct naar onze pseudocode. We kijken naar het midden die kaarten direct op onze pseudocode. Ik zou zeggen dat dit gaat naar het midden van de lijst, deze lijn van code. En dan, een keer gaan we naar het midden van de lijst, het volgende wat we moeten doen is te controleren of onze waarde is er voor de pseudocode we eerder schreven. Dus hoe kunnen we controleren of onze waarde is in het midden van de lijst? Je. Waarom doe je dit niet doen? STUDENT: Als onze waarde is in het midden gelijk aan wat we de - Ik bedoel gelijk gelijk aan - JASON HIRSCHHORN: It - OK. STUDENT: Ik weet niet zeker wat de variabele we zoeken want hoewel, is omdat - [Onderbreekt hem VOICES] STUDENT: [onverstaanbaar]. JASON HIRSCHHORN: Precies. Per de functie declaratie, we zijn op zoek naar een waarde. Dus we zijn op zoek naar een waarde in een reeks van waarden. Dus je hebt helemaal gelijk. Je zal doen, als het open Paren waarde beugel midden gesloten beugel gelijken is gelijk aan de waarde, en binnen is er wat moeten we doen? Als onze waarde is daar, wat moeten we doen? [Onderbreekt hem VOICES] STUDENT: Return nul. JASON HIRSCHHORN: return true. STUDENT: return true. JASON HIRSCHHORN: Michael, wat doet deze lijn doen? STUDENT: [onverstaanbaar] het programma heeft gelopen zijn natuurlijk, en dat is voorbij, en je hebt wat je moet doen? JASON HIRSCHHORN: Het programma of wat? In dit geval? STUDENT: De functie. JASON HIRSCHHORN: De functie. En zo, terug naar wat genoemd het en geef het de waarde, true. Precies goed. Main. Wat is de return type van de belangrijkste, Michael? STUDENT: int, integer? JASON HIRSCHHORN: int, precies. Een geheel getal. Dat was gewoon een kwestie om ervoor te zorgen jullie hebben er bovenop geweest. Wat betekent het meestal terug te keren, indien alle dingen zijn goed werkt? STUDENT: Zero. JASON HIRSCHHORN: Zero. Precies goed. STUDENT: Als dit net geeft true, is er geen informatie wordt gegeven over wat de - Oh, dit is gewoon te zeggen dat dat waarde is in de array. JASON HIRSCHHORN: Precies. Dit programma is niet het geven van informatie waar precies de waarde. Het is alleen te zeggen, ja, vonden we het, of niet, hebben we het niet vinden. Dus als nummer gevonden, return true. Nou, eigenlijk zijn we net deed dat echt snel met die ene regel code. Dus ik zal die lijn van pseudocode bewegen. STUDENT: Niet we nodig om de array te veranderen? Het moet waarden, niet waarde, toch? JASON HIRSCHHORN: Sorry. Dank u. STUDENT: Ja. JASON HIRSCHHORN: Deze lijn moet waarden. Precies goed. OK. Dus we hebben gekeken naar de middelste lijst. Als aantal gevonden return true. Verdergaand met pseudocode, indien midden groter is, zoeken naar links. Dus ik had hier, als het nummer van hoger, zoeken naar links. Constantijn, kunt u me deze regel code? STUDENT: Als de waarde van het midden - JASON HIRSCHHORN: Dus als de waarde - indien geopend Paren waarden beugel middelste haakje sluiten - STUDENT: Is kleiner dan de waarde? JASON HIRSCHHORN: Is minder dan. STUDENT: Minder dan waarde. JASON HIRSCHHORN: Waarde. Nou ja, eigenlijk, je wilt Controleer of het aantal - Sorry. Dit is een beetje verwarrend. Maar anders als het nummer in de midden van de lijst is groter. STUDENT: Oh, OK. JASON HIRSCHHORN: Ik zal dat veranderen. Anders als midden hoger, we wilt zoeken links, OK? En wat doen we binnen doen dit als voorwaarde? STUDENT: Kan ik een kleine wijziging de voorwaarde, verander het naar else if? JASON HIRSCHHORN: Else if? OK. Dus deze code wordt uitgevoerd ongeveer hetzelfde. Maar het leuke van het gebruik indien, anders indien, anders als of indien, anders indien, anders betekent dat slechts een van hen gaat worden gecontroleerd, niet alle drie van hen, potentieel. En dat maakt het een beetje mooier op de computer die is het runnen van uw programma. Dus [? Constantijn,?] we binnen deze lijn, anders als waarden, beugel middelste haakje sluiten groter is dan de waarde. Wat moeten we doen? We moeten naar links zoeken. Hoe doen we dat? Ik ga u een start te geven. We hebben deze twee dingen genoemd begint en eindigt. Dus wat er moet gebeuren naar het begin? Als u aan de linkerkant van het zoeken lijst, krijgen we onze huidige begin. Wat hebben we nodig om het te doen? STUDENT: We zetten het begin te midden plus 1. JASON HIRSCHHORN: Dus als we zoek de linker? STUDENT: Sorry, midden min - dus het einde zou midden zijn minus 1 en het begin - JASON HIRSCHHORN: En wat gebeurt bij het begin? STUDENT: Het blijft hetzelfde. JASON HIRSCHHORN: Dus de betekenis blijft hetzelfde. Als we op zoek bent naar links, we zijn met dezelfde begin - precies goed. En het eindigt? Sorry, wat doet de eindigt weer gelijk? STUDENT: Midden minus 1. JASON HIRSCHHORN: Midden minus 1. Nu, waarom minus 1, niet alleen midden? STUDENT: De middelste is uit de foto al, want we hadden gecontroleerd dat het uit? JASON HIRSCHHORN: Dat is precies goed. De middelste is uit het beeld. We hebben al het midden gecontroleerd. Dus we willen niet dat "het midden" citaat unquote, blijven in de array die we zoeken. Dus dit is fantastisch. Else if waarden beugel midden groter dan waarde eindigend gelijken midden minus 1. Jeff, wat over deze laatste regel? STUDENT: Else. Waarden midden lager is dan de waarde? JASON HIRSCHHORN: We zullen je geeft me anders. Dus als je me niet geven - STUDENT: Dus dan begin zou midden plus 1 zijn. JASON HIRSCHHORN: Beginning gelijken midden plus 1, opnieuw voor dezelfde reden dat Constantijn gaf ons eerder. En aan het eind, heeft die niet gegeven me een regel code nog? Return false, Aleha, wat hebben we hier schrijven? STUDENT: return false. JASON HIRSCHHORN: return false. En we moeten dat doen, want als we vind het niet, we moeten zeggen dat we vond het niet. En we zeiden we gaan terug een bool, dus we hebben zeker om terug te keren een bool ergens. Dus laten we lopen deze code. Ik ben eigenlijk van plan om - dus we zijn in de terminal. We zullen ons raam te wissen. Let's Make All. We vonden er een fout. Er is een fout op lijn 15, verwacht puntkomma aan het einde van de verklaring. Dus wat heb ik vergeten? STUDENT: Puntkomma. JASON HIRSCHHORN: Puntkomma hier naar boven. Volgens mij was dat Tom code. Dus Tom, [onverstaanbaar]. Grapje. Let's Do Make All opnieuw. STUDENT: Wat Dropbox directory moeten we voor dit? JASON HIRSCHHORN: Dus je kunt gewoon kijken voor dit stukje. Maar nogmaals, als je wilde om deze te verplaatsen code in uw pset3 directory te proberen het uit, dat is wat ik deed. Als je hier zult merken - sorry, goede vraag. [? LS,?] Ik heb hier de status van huidige map code van deze week distro code. Ik heb helpers.h. Ik heb een Make-bestand dat ik eigenlijk bewerkt een beetje om deze nieuwe omvatten bestanden die we aan het schrijven bent. Dat alles code zal beschikbaar zijn, niet de verdeling code, maar de nieuwe Maak bestand, de nieuwe helpers.h bestand zal zijn online beschikbaar om te downloaden. Weer, dus dat zijn de extra codes hebben we. Dus al maken, per deze lijn, maakt vinden, binair, bel selectie - merken alledrie en stelt in dit uitvoerbare code vondst. Dus over het algemeen, willen we niet om rechtstreeks naar check50. We willen een aantal tests uit te voeren op onze eigen. Maar gewoon zo kunnen we dit een beetje te bespoedigen, check50 2013 pset3.find zal passeren in helpers.c-- my bad. Ik denk niet dat recht nu. Dus we daadwerkelijk gaat voer de code voor de echte. Usage.find /, weet je wat dat betekent? STUDENT: U hebt een tweede opdrachtregel op. JASON HIRSCHHORN: ik nodig een tweede opdrachtregel. En volgens de specificatie, moet ik te gaan wat we zoeken. Dus laten we eens kijken naar 42. We zullen het in gesorteerde houden, omdat we hebben een soort functie nog niet geschreven - 42, 43, 44. En Controle D vond de naald in de hooiberg. Dat is slecht. Het is zeker daar. Laten we iets anders proberen. Misschien is het omdat ik bij het begin. Laten we 41, 42, 43. Daar gaan we. Hij vond het. Laten we het op het einde nu, net dus we kunnen grondig worden - 40, 41, 42. Heeft de naald niet vinden. Dus ik dit al eerder gezegd. Helaas, dit wist ik ging gebeuren. Maar voor pedagogische doeleinden, het is goed om het te verkennen. Het werkt niet. Om een ​​of andere reden, kan het niet vinden. We weten wat er in zit, maar we zijn niet te vinden. Dus een ding dat we kunnen doen is gaan door GDB om het te vinden, maar doet iedereen, zonder tussenkomst van GDB, hebben een besef van waar we verpest? [? Madu? ?] STUDENT: Ik denk dat het zou kunnen worden wanneer eindigend gelijk aan het begin en het slechts een element lijst. Dan negeert het gewoon plaats daadwerkelijk controleren van het. JASON HIRSCHHORN: Dat is precies goed. Wanneer einde gelijk begin, doen we hebben nog steeds een element in onze lijst? STUDENT: Ja. JASON HIRSCHHORN: Ja, in feite hebben we hebben een en slechts een element. En dat zal waarschijnlijk gebeuren wanneer, per de code die we hebben getest, we zijn op de Voor de hooiberg of het einde van de hooiberg. Dat is waar begin en einde gaat gelijk een, met binaire zoeken. Dus in deze twee zaken dat het niet werkte, omdat eindigend was gelijk aan begin. Maar als eindigend gelijk is aan het begin, gaat deze while lus te voeren? Het maakt niet. En we konden hebben gecontroleerd dat weer door GDB. Dus hoe kunnen we dit oplossen code, omdat wanneer terwijl het beëindigen is gelijk aan begin, dit willen we ook while lus te lopen. Dus wat fix kunnen we op lijn 18? STUDENT: [onverstaanbaar] groter hoogste. JASON HIRSCHHORN: Precies goed. Terwijl einde is groter dan of gelijk begin. Dus nu, zorgen wij ervoor om dat te krijgen corner geval eind. En laten we eens kijken. Laten we lopen nog een keer. Laten we allemaal. Nogmaals, moet je gewoon volgen langs hier. Vind 41 dit keer. Hou het consistent. Vinden 42. Laten we het in het begin - 42, 43, 44. We vonden het. Dat inderdaad de verandering we moesten maken. Dat was veel codering we net deed, binary search. Heeft iemand nog vragen voordat Ik ga verder in regels schreven we in binary search of hoe we dachten wat we niet achterhalen? Voordat we verder gaan, wil ik ook wijzen dat over het algemeen, we in kaart gebracht onze pseudo-code een tot een op onze code. We hadden dat lastig ding om erachter te komen met de begint en eindigt. Maar had je niet bedacht dat uit, je zou vrij veel hebben geschreven de identieke code, met uitzondering van die bovenste twee regels. En dan zou je hebben gerealiseerd wanneer je maakte het in controles en gevallen die je iets anders nodig. Dus zelfs als je had gevolgd onze pseudo-code regel naar regel, zou je hebt gekregen op twee na alle lijnen van Code die u nodig om te schrijven. En ik durf te wedden dat jullie zou alles hebben bedacht dat uit vrij snel, dat je nodig had om te zetten een soort marker daar te achterhalen uit waar je was. Dat weer, is de kracht van het doen pseudo-code van tevoren. Dus we kunnen de logica eerst doen, en dan we kunnen zorgen over de syntaxis. Hadden we in de war over de logica terwijl het proberen om deze code schrijven in C, we zouden hebben gekregen in de war. En dan zouden we moeten vragen vragen over logica en syntaxis en meshing ze allemaal samen. En we zouden gekregen hebben verloren in wat kan snel een worden zeer moeilijk probleem. Dus laten we nu naar op om de selectie te sorteren. We hebben 20 minuten over. Dus ik heb het gevoel dat we niet in staat zijn om krijgen door alle selectie sorteren en bubble sort. Maar laten we in ieder geval proberen om de selectie te sorteren afmaken. Dus implementeren selectie sorteren met behulp van de volgende functie verklaring. Nogmaals, dit is afkomstig van de probleem set specificatie. Int waarden tussen haakjes is een array van integers. En int.n is de grootte van die array. Selectie soort gaat deze matrix sorteren. Dus per ons mentale model van de selectie sorteren, we trekken de - eerst gaan we door de lijst de eerste tijd, vind het kleinste getal, zet het in het begin, vinden de tweede kleinste getal, zet het in de tweede positie als we willen sorteren in oplopende volgorde. Ik ben niet dwingen je om te schrijven pseudo-code op dit moment. Maar voordat we dat doen de code als een klasse in vijf minuten, gaan we schrijven pseudo-code, zodat we enkele zin van waar we heen gaan. Dus proberen om pseudo-code te schrijven op uw eigen. En dan proberen te draaien dat pseudo-code in code. We zullen dat doen als een groep in vijf minuten. En natuurlijk, laat het me weten als je vragen hebt. STUDENT: Dat het? JASON HIRSCHHORN: Zie hoe ver je kan krijgen in twee minuten. Ik begrijp u niet kunnen afmaken. Maar we gaan over deze als een groep. Jullie zijn allemaal codering dus [onverstaanbaar], dus ik ben sorry te onderbreken wat je doet. Maar laten we gaan door dit als een groep. En nogmaals, binary search, je alles te geven mij een, zo niet meer regels code. Bedankt voor dat. We gaan hetzelfde doen hier, code samen als groep. Dus selectie sorteren - laten we schrijven aantal snelle pseudo-code. Per mentaal model, kan iemand mij geven de eerste regel van pseudo-code, alstublieft? Wat wil ik doen? STUDENT: Terwijl de lijst niet in orde is. JASON HIRSCHHORN: OK, terwijl de lijst is niet in orde. En wat bedoel je "out of order?" STUDENT: Terwijl [onverstaanbaar] niet gesorteerd. JASON HIRSCHHORN: Terwijl de lijst niet in orde is, wat doen we? Geef me de tweede lijn, alsjeblieft, Marcus. STUDENT: Dus vinden de volgende kleinste getal. Dit zal worden ingesprongen. JASON HIRSCHHORN: Dus vinden de volgende kleinste getal. En dan iemand anders? Eens vinden we de volgende kleinste nummer, wat doen we? Ik ga zeggen vinden het kleinste getal. Dat is wat we willen doen. Dus zoek het kleinste getal. Wat moeten we dan doen? STUDENT: [onverstaanbaar] naar het begin. JASON HIRSCHHORN: Sorry? STUDENT: Plaats het in de het begin van de lijst. JASON HIRSCHHORN: Dus plaats deze in het begin van de lijst. En wat doen we om het ding dat was in het begin van de lijst, toch? We overschrijven iets. Dus waar we dat? Ja, Anna? STUDENT: Indien de kleinste nummer was? JASON Hirshhorn: Dus zet het begin van de lijst waar de kleinste getal was. Dus terwijl de lijst is niet in orde, vinden het kleinste getal, plaats deze in het begin van de lijst, zet de het begin van de lijst waar de kleinste getal was. Marcus, kunt u deze lijn herformuleren terwijl de lijst is niet in orde? STUDENT: Terwijl de nummers niet zijn gesorteerd? JASON Hirshhorn: OK, dus om weten dat de nummers zijn niet gesorteerd, wat moeten we doen? Hoeveel hebben we nodig om gaan door in dit overzicht? STUDENT: Dus ik denk dat een lus, of terwijl, terwijl de getallen gecontroleerd minder dan de lengte van de lijst? JASON Hirshhorn: OK, dat is goed. Ik denk dat ik misphrased mijn vraag slecht. Ik probeerde op te krijgen we zullen moeten gaan door de hele lijst. Dus terwijl de lijst is niet in orde, voor mij, is moeilijk in kaart op. Maar in principe, dat is hoe Ik denk dat over dit. Ga door de hele lijst, vinden de kleinste getal, plaats hem in de begin - in feite, je hebt gelijk. Laten we ze allebei. Dus terwijl de lijst is niet in orde, we moeten gaan door de hele lijst eens, vind het kleinste getal, plaats in het begin van de lijst gezet het begin van de lijst waar de kleinste getal was, en dan als de lijst nog steeds niet in orde, we hebben kreeg om te gaan door deze proces opnieuw, toch? Daarom selectie sorteren, Big-O runtime van selectie sorteren, anyone? STUDENT: n kwadraat. JASON Hirshhorn: n kwadraat. Want net als Marcus en ik besefte hier, we zullen moeten gaan door de lijst Lijst aantal keren. Dus gaan door iets van lengte n n aantal keren is in feite n kwadraat. Dus dit is onze pseudocode. Dit ziet er erg goed. Heeft iemand enig vragen over de pseudocode? Want eigenlijk selectie sorteren moet waarschijnlijk komen 1-1, code van pseudocode. Dus vragen over de logica van de pseudocode? Vraag het nu. Selectie sorteren - terwijl de lijst is uit van orde, gaan we er doorheen en vind de kleinste telkens en zet het in de voorkant. Dus terwijl de lijst niet in orde is, kan iemand mij die regel code die heeft mij niet gegeven een lijn van de code nog, alstublieft? Het klinkt als een wat? STUDENT: Dat is een lus. JASON Hirshhorn: Het klinkt graag een lus. OK, kunt u mij de lus? Voor - STUDENT: i gelijk aan 0. JASON Hirshhorn: i of - wat missen we? Wat gaat er hier? STUDENT: Int. JASON Hirshhorn: Precies. (Int i = 0; - STUDENT: i