>> 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 <n; i + +).
>> JASON Hirshhorn: Nailed het, Jeff.
We gaan door de lijst, toch?
We hebben die code eerder gezien.
Perfect.
Dus laten we onze accolades hier.
Ik ga wat zetten accolades hier.
>> Dus terwijl het is 0, we moeten gaan de hele lijst.
Dus elke keer als we door de lijst, wat willen we bij te houden?
>> STUDENT: Als een swaps worden aangegaan.
>> JASON Hirshhorn: zoeken het kleinste getal.
Dus moeten we waarschijnlijk bijhouden het kleinste getal elke keer.
Dus lijn kan ik doen om bij te houden van het kleinste getal?
Aleha, hoe kan ik houden spoor van iets?
>> STUDENT: Start een nieuwe variabele.
>> JASON Hirshhorn: Start een nieuwe variabele.
Dus laten we maken een variabele.
Welk type?
>> STUDENT: Int.
>> JASON Hirshhorn: Int.
Laten we noemen het de kleinste.
En wat doet het gelijk wanneer we net beginnen?
We zijn nog niet door de lijst verdwenen.
We zijn in het eerste deel van de Lijst van onze eerste keer door.
Wat doet het gelijk, de kleinste getal?
>> STUDENT: Waarden i.
>> JASON Hirshhorn: Waarden i.
Dat klinkt precies goed, toch?
Het kleinste getal aan het begin is waar we zijn.
Dus nu hebben we onze kleinste, en we moeten om te gaan door de hele lijst en
vergelijk deze kleinste al het andere.
Dus gaan we weer door de lijst?
Michael?
>> STUDENT: Je moet ervoor andere voor lus.
>> JASON Hirshhorn: Nog een lus.
Laten we het doen.
Geef me wat code.
>> STUDENT: For-lus -
voor de kleinste -
gewoon int j, zou je kunnen zeggen?
= 0, zodat -
>> JASON Hirshhorn: Nou, als we willen om te gaan door de hele lijst -
>> STUDENT: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
We gaan door te gaan de lus opnieuw.
En hoe vinden we de kleinste getal?
Tom?
We hebben de huidige kleinste getal, dus hoe vinden we de nieuwe kleinste?
>> STUDENT: We kunnen controleren of de kleinste nummer dat we hebben is groter dan
waarden beugel j.
>> JASON Hirshhorn: Dus als kleinste is groter dan waarden beugel j.
Dus als onze huidige kleinste groter dan -
Ik ga deze twee lijnen te verplaatsen van code die er voor een tweede.
Want voordat we doen elke swapping, we moeten gaan door de hele lijst.
Dus dit pseudocode zou eigenlijk buiten die innerlijke lus.
Dus ga de hele lijst.
Als kleinste groter is dan waarden j dan wat?
>> STUDENT: Dan kleinste is gelijk aan de waarden j.
>> JASON Hirshhorn: Fantastic.
Een snelle vraag -
de eerste keer dat we door deze lus, i gaat gelijk 0, is j gaat
evenaren 0 zodra we in hier.
Dus we gaan te vergelijken een nummer aan zichzelf.
Is dat efficiënt?
Nee, het is niet echt efficiënt.
Dus heeft onze j moeten gaan van 0 tot n telkens?
Moeten we altijd te controleren de hele lijst?
[Onverstaanbaar]?
>> STUDENT: Begin met i plaats.
>> JASON Hirshhorn: j blikje beginnen met wat?
>> STUDENT: i.
>> JASON Hirshhorn: j kan beginnen met i.
Dus nu we vergelijken starten met de ene we op.
Maar zelfs dan, dat als efficiënt mogelijk?
>> STUDENT: i + 1.
>> JASON Hirshhorn: i + 1 lijkt te zijn de meest efficiënte, omdat we
Heb ik al gedaan.
We stellen dat als de kleinst in lijn 15.
We gaan beginnen met de volgende automatisch.
Dus gaan we door de lus.
We gaan door elke keer.
We gaan door een aantal keren.
Nu hebben we gekregen door deze innerlijke lus.
We hebben de kleinste waarde bespaart.
We moeten om het te plaatsen op de het begin van de lijst.
Dus hoe kan ik plaats het op de het begin van de lijst?
Wat is de variabele die verwijst aan het begin van de lijst?
We zijn in dit buiten lus, dus wat betreft de
het begin van de lijst?
>> STUDENT: Waarden i.
>> JASON Hirshhorn: Precies goed.
Waarden i is het begin van de -
of sorry, niet het begin.
Dat was verwarrend.
Het is waar we in het begin van het ongesorteerde deel van de lijst.
Dus waarden i.
En wat doet dat gelijk?
>> STUDENT: Kleinste.
>> JASON Hirshhorn: Waarden i is gelijk aan wat?
>> STUDENT: Kleinste.
>> JASON Hirshhorn: Kleinste.
Precies goed.
Dus we het plaatsen van bij het begin van de lijst, en nu moeten we zetten
het begin van de lijst waar het kleinste getal was.
Dus hoe kan ik schrijven waar de kleinste getal was?
Waarden van wat?
>> STUDENT: 0.
>> JASON Hirshhorn: De kleine nummer staat op 0?
>> STUDENT: Ja.
>> JASON Hirshhorn: Wat als de kleinste nummer was eind
deze ongesorteerde lijst?
>> STUDENT: Sorry, wat was de vraag?
>> JASON Hirshhorn: Waar is het kleinste getal?
We namen de kleinste en zet het op de beginnen, met deze lijn hier.
>> STUDENT: Het moet opgeslagen in sommige -
>> STUDENT: Waarden j.
>> JASON Hirshhorn: Nou, het is niet noodzakelijkerwijs waarden j.
Het bestaat niet eens op dit punt.
>> STUDENT: U moet verklaren een variabele eerder en
vervolgens toewijzen aan -
als je merkt dat het kleinste getal, toewijzen de index van dat aantal te
enkele variabele of iets dergelijks.
>> JASON Hirshhorn: Dus kan je wel zeggen?
>> STUDENT: Dus waar u verklaard int kleinste, moet u ook aangeven int
kleinste index = i, of zoiets.
>> JASON Hirshhorn: Dus waar ik int kleinste, ik moet niet alleen bij te houden
van de waarde, maar de locatie.
int smallest_location = in dit geval is, zullen we gewoon doen i.
We moeten weten waar het is.
We kwamen aan bij het einde van de code, en we beseften we hadden geen idee waar het was.
En dus nogmaals, we zijn het in kaart brengen Deze op 00:59.
Jullie codering dit op je eigen wil waarschijnlijk aan het zelfde probleem.
Hoe de heck kan ik deze vinden?
En dan besef je, wacht, ik moeten bijhouden van die te houden.
>> Als kleinste groter dan waarden j.
We stellen kleinste gelijk aan waarden j.
Wat hebben we nodig om te veranderen?
Constantin, wat anders doen we moeten veranderen?
>> STUDENT: De locatie.
>> JASON Hirshhorn: Precies.
Dus geef me die lijn in de code.
>> STUDENT: smallest_location = j.
>> JASON Hirshhorn: Precies.
En dan aan het eind, als we willen zet het begin van de lijst waar
het kleinste getal was, hoe wij verwijzen waar de
kleinste getal was?
Marcus?
>> STUDENT: Het kleinste getal was gelegen bij de kleinste locatie.
>> JASON Hirshhorn: Dus op waarden smallest_location.
En wat hebben we daar te zetten?
Het begin van de lijst, wat is dat?
>> STUDENT: Nou, we weten niet echt meer, omdat we overschreven.
Dus het is een geruild locaties van deze twee lijnen?
Als je die twee lijnen rond te schakelen.
>> JASON Hirshhorn: OK, dus doen we niet meer, want we hebben de lijn te resetten
voor waarden i om kleinst.
Dus we verloren dat beginwaarde.
Dat zei je swap deze twee lijnen.
Dus nu zet het begin van de lijst waar het kleinste getal was.
Dus smallest_location gelijk waarden i.
Dat is het verplaatsen van het begin van deze ongesorteerde deel van de lijst om de
kleinste locatie.
En dan in waarden i we bewegen dat kleinste getal.
>> Is dat zinvol waarom we moest dat swap te maken?
We zouden hebben overschreven die waarde - een ander wat je waarschijnlijk zou hebben
bedacht en vond in het BBP.
Dus we hebben gezorgd alle pseudocode.
Is er iets anders hebben we nodig hebben om hier te schrijven?
Kan iemand nog iets?
>> STUDENT: Hoe weet je dat als je klaar bent?
>> JASON Hirshhorn: Hoe doen we weten wanneer we klaar zijn?
Goede vraag.
Dus hoe weten we wanneer we klaar zijn.
>> STUDENT: Maak een variabele telling houden van als er een swap gedaan of niet
en gaan door een pass.
>> JASON Hirshhorn: OK.
Dat zou werken in bubble sort.
Maar voor de selectie sorteren, als we niet maak een swap, zou dat gewoon
omdat de kleinste waarde in deze van haar locatie.
We zouden een lijst 1, 2, 4, 3 hebben.
De tweede keer dat we door middel van zal geen swaps maken.
We zullen op de nummer 2, maar we zullen moeten nog door te gaan.
Dus moeten we bij wanneer houden wij worden gedaan, of doen we gewoon willen gaan
totdat dit klaar is?
>> STUDENT: We kunnen gewoon gaan totdat het klaar is.
>> JASON Hirshhorn: We kunnen gewoon gaan tot dit klaar is.
In bubble sort, je hebt helemaal gelijk, Jeff en Aleha, met uw oplossing -
het is geweldig om bij te houden hoeveel swaps die u hebt gemaakt, want in bubble
soort, als je in feite doen geen swaps, je klaar bent en je kunt misschien knippen uw
probleem een ​​beetje.
Maar voor de selectie sorteren, je hebt echt moet doorlopen om het einde van de
lijst elke keer rond.
>> Dus dit is dat.
We hebben twee minuten over.
Laten we allemaal.
Laat me gewoon geopend Vind hier en maak zeker dat ik in feite te roepen -
Ik bel niet bubble sort.
Laten we dit veranderen in selectie sorteren.
maak alle. / vinden.
Laten we 42.
Deze keer gaan we een pas ongesorteerde lijst, omdat het zou moeten sorteren
eerst, per de vondst code - dient te sorteren eerste gebruik van onze sorteerfunctie en vervolgens
op zoek naar iets.
Vingers gekruist iedereen.
>> Oh mijn god.
Whoa, mijn hart klopte.
Dus dat is correct.
In feite, als we liepen dit meer uitgebreid, de code, voor zover ik kan
vertellen, is volkomen juist.
Er zijn een aantal suggesties Ik zou voor jou.
Bijvoorbeeld, 15 en 16 lijken een beetje overbodig.
Het lijkt alsof je per se niet moeten beide slaan.
Als je de kleinste locatie, u U kunt eenvoudig de kleinste waarde door
gewoon te typen waarden van i.
>> Dus als ik zou worden indeling uw code, die ik zal in feite, zou ik
waarschijnlijk opstijgen een punt als je Inclusief beide, want je
hoeven niet beide.
Als u de locatie, kunt u heel gemakkelijk de waarde.
En het lijkt een beetje raar beiden te slaan.
Misschien niet eens een punt, maar zeker opmerken dat dat misschien
niet een stilistische keuze u moet maken.
Natuurlijk, de code nog steeds loopt heel goed.
>> Dus helaas hebben we niet krijgen bubble sort.
Het spijt me dat.
We deden afwerking selectie sorteren.
Heeft iemand enig laatste vragen over selectie sorteren?
>> OK, voordat we het hoofd uit, ik wil dat je open te stellen uw Chrome-browser.
Sorry, dat was gewoon een schaamteloze plug voor een type internet browser.
U kan openen elk type browser, maar het zal waarschijnlijk Chrome.
En ga naar de volgende website -
sayat.me/cs50.
Als je niet typen in de computer nu, je duidelijk bent
het niet te doen, Tom.
>> En doe het met de rechtermuisknop nu of in de komende uur -
geef me wat feedback.
Dit is slechts deel twee.
Wij hebben veel meer samen, dus ik hebben veel ruimte om te verbeteren.
Ik hopelijk ook deed wat dingen goed.
Dus je kunt me allemaal slecht, maar als je wilt ook mij een smiley geven
gezicht, ik zou het waarderen dat ook.
Vul dat in
>> En met een minuut links, dat was week drie.
Ik ben buiten staan ​​voor een beetje als u vragen hebt.
Ik zal jullie zien in lezing morgen.