>> JASON HIRSCHHORN: Welcome til uge tre, alle sammen.
Vi har en travl men spændende sektion foran os.
Så det første, fordi vi har gjort nogle fremskridt med kurset, men vi har stadig
har en masse at lære tilbage at gøre, er jeg kommer til at vise jer nogle ressourcer
der skulle vise sig at være utrolig nyttigt, da du ikke kun nærmer dig din
Problemet sætter, men også fordøje alle det materiale, vi giver jer i
foredrag og shorts og afsnit.
>> Så vi kommer til at tilbringe de første 20 til 25 minutters afsnit går over
GDB, som du måske eller måske ikke har anvendes på dette tidspunkt, men det er en
utroligt nyttigt værktøj, der vil hjælpe dig debug dine programmer.
En masse af jer måske har brugt printf i midten af ​​dit program til at regne
ud af, hvad en variabel umådeholdent.
GDB er endnu bedre end printf og ikke skrue op din kode, fordi du
køre det på en eksekverbar fil.
Så vi vil gå over de 10 mest nyttige kommandoer, du har brug for GDB, og vi er
kommer til at gå på en øvelse sammen, så i problemet sæt tre og videre, du
kan bruge GDB at hjælpe debug dine programmer.
Og endelig, vi kommer til at gå over nogle sortering og søgning algoritmer
at du så i foredrag, og vi er vil faktisk kode, ikke blot
pseudokode, men kode binær søgning, boble sortere, og udvælgelse slags.
>> Så det første, jeg ønsker at gå over ressourcerne.
Dette er en omfattende liste, og det er mindre skrift, fordi jeg havde en masse at
passe på her.
Men disse vil ikke kun hjælpe dig, igen, med problemet sæt og
fordøje de oplysninger, du har lært, men afgjort, kom quiz tid, vil disse
være utrolig nyttigt.
Så det første, foredraget noter.
Hvis du går til cs50.net/lectures og rulle til den pågældende uge og dag,
vil du se at der er bemærkninger til de enkelte foredrag, der er ikke blot en
transkript, men en redigeret version af hvad der blev dækket i foredrag med kode
snippets og andre nyttige godbidder.
Jeg kan varmt anbefale at gå over dem.
Og så så godt, er der kildekode tilgængelig fra hver forelæsning.
Og igen, vil disse dias også være tilgængelig online på cs50.net/sections
denne aften.
>> Så sekund er de shorts hver uge, dækker emner, som regel 5 til 15
minutter i længden.
Og dem, forhåbentlig vil give dig en stor primer på forskellige emner.
Tredje -
og det er helt nyt denne år - er study.cs50.net.
Hvis du ikke har tjekket det ud, jeg varmt anbefale, at du gør det.
Du kommer til at vælge et emne.
Vi har dusinvis af emner på der.
Så du for eksempel vælge Funktioner.
Det giver dig nogle dias og noter om funktioner.
Det er faktisk de dias, TFs opfordres til at bruge under vores
præsentationer i afsnit.
Der er også tips og tricks til at håndtere med funktioner, og der er
praksis problemer, der hjælper du arbejder med funktioner.
Vi giver dig også links til kort på funktioner og de tidspunkter, der fungerer
er kommet op i foredraget.
Så study.cs50.net Nybygget dette år, en fantastisk ressource.
>> Dernæst har jeg mand, som er den manuelle kommando, som du kan køre på
kommandolinjen.
Så hvis du har spørgsmål om en kommando for eksempel rand, som vi
stødte i sidste uge under sektion og du har sandsynligvis stødt på
dit problem sæt, når der går gennem generere kode, men hvis du skriver mand
rand, får du den side, fortæller dig alt om rand.
Det giver dig, hvad det tager, det parametre, det tager, samt afkast
type og en kort beskrivelse af denne funktion.
>> Så tjek rand.
Det kan være lidt ordrige og forvirrende, så nogle gange finder jeg, at
simpelthen at google, hvad jeg ønsker at vide er den bedste måde at finde svaret.
Så praksis med Google.
Få gode hos Google.
Det vil blive din bedste ven.
>> Samt Google, hvis du ikke kan finde det på Google, cs50.net/discuss, det er
diskussionsforum.
Chancerne er, hvis du har et spørgsmål, en dine 700 + peers har også at
spørgsmål og kan have bedt allerede i diskutere
fora og har det besvaret.
Så hvis du har et almindeligt spørgsmål eller du har et spørgsmål som du mener
måske andre mennesker måske har kørt ind, tjek cs50.net/discuss.
>> Endelig er den sidste to, hvis du vil tale med en virkelig menneske, kontor
timer mandag til fredag.
Der er også online kontortid for udvidelse studerende.
Og sidst men bestemt ikke mindst, mig, udråbstegn.
Du har alle mine kontaktoplysninger.
Hvis du har brug for noget, bedes du aldrig velkommen til at kontakte mig.
Altid velkommen til at gøre det.
Meget få af jer har tilføjet mig på Gchat, så der har været skuffende,
men forhåbentlig, der vil skifte mellem dette og næste afsnit.
Eventuelle spørgsmål, så langt på ressourcerne?
Store.
>> Endelig et andet stik til feedback, sayat.me/cs50.
Du kan give mig anonym tilbagemelding om, hvordan jeg gør.
Det var virkelig nyttige i sidste uge.
Jeg fik et par kommentarer fra jer lige efter sektion, plus fra
andre studerende, der så det i løbet af ugen, og det
var utroligt hjælpsomme.
Jeg vil forsøge at begrænse min brug af ordet "sød", men jeg vil vise min
entusiasme og begejstring på andre måder.
Men der var andre yderligere materielle feedbacks,
både plusser og Delta.
Så please, jeg giver jer tilbagemeldinger på dit problem sæt.
Du er velkommen til at give mig feedback på min undervisning.
Jeg er her for jer.
>> Store.
Det er alt jeg har for den første sektion.
Er der nogen har nogen spørgsmål indtil videre?
Og jeg har en note til vagtcentralen.
Extension studerende har messaged mig siger, at de får ikke nogen lyd,
men der er ude af min magt at fastsætte.
Så forhåbentlig, der får løst inden længe.
Hvis du ser online, hej, men du kan ikke høre mig.
>> Så først skal vi at gå gennem GDB.
GDB, som jeg antydede tidligere, er et fejlfindingsværktøj
meget bedre end printf.
Så for at komme i gang med GDB, gutter, hvis du ønsker at åbne op dit apparat
og tage den fil, jeg sendt til dig tidligere - denne fil vil også være
tilgængelig online i en bit -
og køre GDB. / navnet på filen.
Først, selvfølgelig, er du nødt til at kompilere fil fordi GDB fungerer kun på
eksekverbare filer.
>> Men hvis du nogensinde ønsker at starte GDB, den første ting du gør,
du kører GDB. / Cæsar.
Så det er navnet på det program, vi er kommer til at gå med det lige nu.
Så jeg har tænkt mig at skrive gøre Cæsar, som vil give mig en eksekverbar fil
her markeret med grønt.
Og så har jeg tænkt mig at køre GDB. / Cesar.
>> Og der du går.
Du kan se vi har noget tekst fortæller mig om den version af GDB, giver mig
nogle oplysninger om garanti, og så vi har BNP prompt, som ser slags
ligesom vores kommandolinje prompt, men du kan se det er åbent
paren, GDB, tæt paren.
Før vi fortsætter, og debug denne fil som jeg sendte til jer alle, lad os se på
nogle nyttige kommandoer, så vi har en fornemmelse af det, vi kommer til at dække.
>> Disse kommandoer er vist her i rækkefølge, som jeg normalt bruger dem.
Så jeg starter mit program ved at køre GBD. / Navnet på det program,
i dette tilfælde, Cæsar.
Og så den første ting jeg gør 99,9% af tiden er typen pause betyder.
Det sætter en pause punkt på main.
Væsentlige, hvad du laver der er programmet vil stoppe ved
vigtigste, så du kan begynde at undersøge det linie linje, snarere end at køre alle
vejen igennem.
Du kan bryde på forskellige din kode, men vigtigste er generelt en
godt sted at starte.
>> Den næste kommando jeg kører køres.
Det starter programmet kører, og hvis du har brug for at indtaste kommandolinjen
argumenter, du kører det på den kommando.
Løb med argumenterne.
Så da vi skal over en version af C, som er det program, du fyre
skrev for PSET to -
denne ene, selvfølgelig, har nogle bugs i det, som forhåbentlig finder vi -
vi kommer til at køre løb med en kommando line argumenter fordi Cæsar,
som du fyre vide per problemet sæt spec, tager nogle
kommandolinjeargumenter.
>> De næste par kommandoer, den næste man faktisk kaldes næste.
At man tager dig linje for linje gennem dit program.
Så rammer n derefter på Enter tager dig til næste linje, udførelse
den foregående linje.
Step tager du ikke kun til den næste linje, men det
tager dig inde funktioner.
Så hvis du har skrevet en funktion i din kode, eller hvis du ønsker at udforske en
til i, for eksempel, kan du hit s, og snarere end at gå til den næste linje
den fil, du går igennem lige nu, vil du faktisk træde ind
denne funktion, og se sin kode.
>> Listen viser dig, i meget brugervenlig format, de 10 eller deromkring linjer omkring
hvor du i øjeblikket er i din kode så du kan faktisk se filen
snarere end at skulle skifte tilbage og tilbage mellem forskellige synspunkter.
Print er ligesom printf, som navnet antyder.
Det viser dig, hvad en variabel lig.
>> Info lokale er virkelig nyttige.
Dette er en særlig udgave af print.
Info lokale viser dig alle de lokale variabler, udskriver dem alle ud for dig
der findes i øjeblikket.
Så jeg generelt, snarere end at skulle udskrive de fire variable, som jeg er
nysgerrig, hvis jeg er i en for-løkke, for eksempel, jeg bare skrive info lokalbefolkningen,
og det vil vise mig, hvad min counter i lig, samt array, at jeg er
arbejder på ligemænd.
>> Endelig fortsætter.
Typing pause stopper dig ved knækpunkt.
Du kan gå igennem linje linje med næste og trin.
Fortsæt kører programmet til din næste knækpunkt eller indtil afslutningen, hvis
der ikke er flere break point.
Disable fjerner break point, hvis du besluttede pause på vigtigste var
upassende, du ønsker at sætte den et andet sted.
Og endelig q, holde op, får ud af GDB.
>> Så dette program,. / Cæsar, vi at se igennem lige nu, og vi
vil bruge GDB at finde bugs i dette program.
Jeg kørte dette program tidligere med Check 50, og jeg fik en panderynken.
Alt det eksisterede, er det kompileret, det bestået en masse af prøverne, men for
eller anden grund, var det ikke passere den femte test, drejning BARFOO alle caps, i
E-D-U-I-R-R, alle kasketter, bruge tre som en nøgle.
Jeg fik temmelig tæt på.
Jeg slap med et bogstav.
Så der er nogle små fejl i her.
Jeg har kigget igennem min kode.
Jeg kunne ikke regne det ud.
Forhåbentlig kan du fyre hjælpe mig regne ud, hvad denne fejl er.
>> Så det er den fejl, vi er søger efter.
Lad os flytte ind GDB.
Igen, jeg har kørt GDB. / Cæsar, så nu er vi i GDB.
Og hvad er den første ting jeg skal gøre?
Jeg har netop indgået GDB.
Nogen give mig en god kommando til at komme ind.
>> STUDENT: Break main.
>> JASON HIRSCHHORN: Break main.
Fantastic.
Lad os skrive det i.
Du fyre kan se op her, eller følg sammen på dine computere.
Break vigtigste, og du vil se en break point blev sat til -
det giver mig nogle underlige hukommelse adresse, og det giver mig også den linje nummer.
Hvis jeg skulle se tilbage på denne fil, Jeg ville indse, at main
skete på linie 21.
Hvad skal jeg køre næste?
Er mit program kører?
Nej.
Så hvad skal jeg køre næste?
>> STUDENT: Kør.
>> JASON HIRSCHHORN: Kør.
Skal jeg bare køre løb, eller skal Jeg tilføje nogle andre ting i?
>> STUDENT: Løb med argumentet.
>> JASON HIRSCHHORN: Løb med kommandoen argumenter.
Og da jeg debugging en meget specifik tilfælde, skal jeg indtaste det
kommandolinje argument.
Så jeg vil løber tre, der er, igen, output jeg fik fra Check 50.
Start program.
Vi går gennem et par linjer.
Du vil nu se, at vi er på linie 21.
Hvordan kan jeg vide, at vi er på linje 21?
Fordi hvis man ser til venstre af min terminal vindue, der
det siger linie 21.
Og det giver mig, faktisk, det kode, der er på linie 21.
Så jeg misspoke tidligere.
Main er faktisk ikke på linie 21.
Main er et par linjer over 21..
Men på linje 21, der er hvor vi bryder.
Denne linje kode har endnu ikke udført.
Det er vigtigt.
Den linje, du ser ikke har blevet henrettet endnu.
Det er den næste linje kode du er ved at udføre.
>> Så den næste linje, som du fyre er sikkert bekendt med, er dette
tilstand kontrol for at se, om jeg har indtastet en kommandolinje argument.
Og et til i, hvad der er den anden en del af, at gøre?
Hvad er en til i?
>> STUDENT: at ændre det til et heltal.
>> JASON HIRSCHHORN: Undskyld?
>> STUDENT: Det ændrer den argument til et heltal.
>> JASON HIRSCHHORN: Så en til i skifter arg v1 fra en streng til et heltal.
Og hvad er det kontrol?
>> STUDENT: Hvis der er en anden kommandolinjeargument, bortset
fra at køre programmet.
>> JASON HIRSCHHORN: Og hvad er i anden halvdel af dette
Boolsk udtryk kontrol?
Denne del herovre, en for jeg?
>> STUDENT: Hvis det er negativt.
>> JASON HIRSCHHORN: Making sikker på hvad?
>> STUDENT: At sikre det er i virkeligheden positivt.
>> JASON HIRSCHHORN: Præcis.
Dette er kontrol for at se, om det er negativ, og hvis den er negativ, jeg
har en fornemmelse af den næste linje magt være mig råben på brugeren.
Så lad os ramte ende at udføre denne linje.
Vi kan ikke se, at linje, som du fyre måske forventet at se råben på
bruger og derefter vender tilbage, fordi denne linje ikke udføre.
Jeg trådte 3.
Så jeg havde faktisk indtaste to kommando line argumenter, og 3 er
større end nul.
Så vi så, at linje, vi henrettet, men vi havde ikke træde
inde i hvis betingelse.
>> Så nu, næste, jeg ser jeg indstilling int nøgle svarer til en til i arg v1.
Så det er mig skabe en variabel nøgle.
Så hvis jeg udskrive nøgle lige nu, fordi der giver dig mulighed for at se den
værdien inden variablen, nøgle er lig 47..
Det er underligt, men selvfølgelig, det er fordi jeg ikke har
henrettet denne linje endnu.
Så nu, hvis jeg ramte n, udføre denne linje, og gøre print nøgle, vil nøgle lig 3,
hvilket er, hvad vi forventer, at lig.
>> Så igen i GDB, den linje, du se, du ikke har udført endnu.
Du er nødt til at slå n eller s eller et nummer af andre kommandoer til faktisk
udføre den pågældende linje.
Print nøgle.
Keys ved 3.
Så langt, så godt.
String er almindelig tekst.
Lad os udføre denne linje.
Jeg får en snor fra brugeren.
>> Lad os se i min Check 50, jeg indtaste BARFOO alle caps, så
det er, hvad jeg vil komme ind.
Hvis jeg nu udskrive almindelig tekst.
Du vil se det er lig en streng.
Det giver mig nogle andre underlige hexadecimal nummer, men det gør i
Faktisk sige, at min streng er BARFOO.
Hvis jeg ønskede at se, hvad nøglen svarede på dette punkt, hvordan kunne jeg tjekke nøgle?
>> STUDENT: Print nøgle.
>> JASON HIRSCHHORN: Print nøgle, nøjagtigt.
Og faktisk, der er en genvej.
Hvis du bliver træt af at skrive print, du kan bare skrive p.
Så p nøgle gør nøjagtig de samme ting.
Og igen, jeg ser det er lig 3.
>> Hvis jeg ønskede at finde ud af, hvad både nøgle og BARFOO svarede samtidig
men jeg var træt af at skrive hver én ud enkeltvis, I
kunne skrive info lokalbefolkningen.
Det giver mig vigtige ligemænd 3.
Almindelig tekst lig BARFOO.
Det giver mig også disse to underlige ting i toppen, denne variabel i og
denne variabel n..
>> De er faktisk eksisterende i min hovedprogrammet.
Vi har ikke mødt dem endnu, men som et eksempel, der
eksistere i min for-løkke.
Så lige nu, de lige nogle underlige tal, fordi de ikke har været
initialiseret endnu, men de findes stadig i hukommelsen, så de er bare sat
nogle skrald værdi.
Men vi kan se nøglen i almindelig tekst lige der.
>> Så jeg har tænkt mig at udføre denne linje, linie 34, for-løkken.
Vi kommer til at springe i for loop ved at trykke n.
Og vi er inde i for-løkken.
Vi er på vores første check.
Og igen, bør disse slags kigge velkendt for dig, fordi det var en
Cæsar-program, der blev skrevet, men igen, har en slags bug.
>> Og nu, hvis jeg gør info lokalbefolkningen, fordi jeg er indeni, der for-løkke, vil du se
at jeg er lig med nul, som vi forventer.
Det er, hvad vi satte det til og initialiseres det i for-løkken.
n er lig med 6.
Det giver også mening, fordi vi har sat det til strlen almindelig tekst.
Så jeg kan lide at gøre info locals eller udskrive til variabel ofte for at sikre, at
alt er altid hvad Jeg forventer, at det lige.
I dette tilfælde, er alt hvad jeg forventer, at det lige.
>> Så lad os begynde at bevæge sig gennem dette for løkke.
Den linje jeg er på er linie 36, hvis almindelig Teksten i er større end en og almindelig
Teksten i er mindre end eller lig med z.
Jeg kender mit problem er ikke med min første brev, er det med det andet bogstav.
Hvis vi ser tilbage på Check 50 B går til E fint.
Jeg tager A og lade det som en A, ikke ændrer det til D. Så
noget er galt med det andet bogstav.
Så jeg har tænkt mig at flytte der i en anden.
>> Men hvis jeg havde lyst til at kontrollere, hvad almindelig tekst, jeg svarede i dette særlige
tilfælde, jeg mener, det bør være, hvad?
Hvad skal almindelig tekst jeg lige i dette første runde gennem for-løkken?
>> STUDENT: Zero?
>> JASON HIRSCHHORN: Almindelig tekst af I?
Så det bør være hovedstad B. Jeg, selvfølgelig, lig med nul, men almindelig tekst
beslag nul lukket beslag lig B fordi strenge, som vi så i sidste uge,
er array, så vi får den første tegn fra det.
Så igen, hvis jeg udskrives almindelig tekst af Jeg, jeg gør i virkeligheden, får karakter
B. Og det er pæn, ikke?
Jeg har faktisk ikke almindelig tekst I. Det er ikke en af ​​de variabler, jeg sat
eller initialiseret, men du kan udskrive ud af en hel række ting
hvis du gerne vil.
>> Men lad os komme igennem.
Hvis almindelig tekst I er større end A og klartekst I er mindre end eller lig med
Z, der klart er sandt, fordi vi har en kapital B. Jeg har tænkt mig at køre
en kommando på den.
Vi så, at matematik i sidste uge, så vi vil tager det for givet, at det virker
ret i henhold til check 50 år.
>> Disse krøllede parenteser, den første viste, at jeg var afslutter hvis
tilstand, den anden viste at jeg forlader for-løkken.
Og så nu når jeg ramte Dernæst vil vi se Vi er tilbage på for-løkken igen.
Vi går gennem for loop igen.
Lad os faktisk træde ind i anden iteration af for-løkken og type
info lokale.
>> Så vi er i den anden iteration vores for loop.
Jeg er lig med 1, som vi forventer.
N er lig med 6, som vi forventer.
Key lig 3, som vi forventer.
Og almindelig tekst, vil du se, lig EARFOO nu, ikke BARFOO længere, fordi
i vores tidligere iteration, B var ændret til et stort E. Så vi er ved
at støde på problemet, så det er, hvor vi kommer til at
dykke ned i debugging.
Men nogen har nogen spørgsmål om, hvad vi har gjort hidtil?
Fantastic.
>> Så vi er ved at udføre dette, hvis betingelse, almindelig tekst beslag jeg lukkede
beslag større end A og almindelig tekst I mindre end eller lig med Z. Men før
Jeg går ind i det, fordi det er her Jeg kender min fejl er, vil jeg påpege
ud almindelig tekst af I. Så lad os sætte udskrive.
Det gør lig tegnet A, således at synes så langt, alt er godt og rigtigt.
>> Så jeg forventer, at denne linje pr min logik, denne linje skal være sandt.
Det er et stort bogstav.
Men hvis jeg ramte n, vi indse, at dette linje, i virkeligheden, ikke udføre.
Jeg sprang ned til andet, hvis.
Hvorfor skete det?
>> STUDENT: Fordi du har din tilstand af almindelig tekst er større
end A, ikke lig med eller større end.
>> JASON HIRSCHHORN: Så jeg havde min almindelig tekst I er større end A, ikke er større
end eller lig med.
Så klart, hovedstaden A ikke gjorde udløser dette, hvis tilstand, og det gjorde vi
ikke træde ind i det, og det gjorde vi ikke gøre det nødvendige skift.
Så det er det, faktisk.
Jeg regnede ud af min bug.
Jeg kunne gå tilbage i min kildefil, ændre det, og opdatere den og
køre Tjek 50 igen.
>> Men vi vil se, bare for pædagogik s skyld, hvis jeg holde.
Det andet, hvis ikke udfører enten, men hvad stedet lig er kommandoen
der ikke ændrer sig.
Så det er ikke ændret på alle, og hvis jeg udskrive almindelig tekst her, vil vi se at gå
ved at for-løkken ikke i virkeligheden, ændre det andet tegn på alle.
Det er stadig en kapital A.
>> Så igen, vi fejlrettet vores fejl.
Vi indså, at der var vis logik mangler.
Og vi fejlrettet det forud for tid, før faktisk udfører denne linje,
men du ville have bemærket havde vi bare hit Next og hoppe til det andet, hvis
det betyder, at at hvis betingelse var ikke sandt.
Vi havde ikke i virkeligheden, får det resultat, vi havde forventet.
Så vi kunne have været bedt om det, havde vi ikke været så klog, at se på
at hvis tilstand og kontrollere, om i virkeligheden, vores tilstand bør evaluere på
sandt i den aktuelle kontekst.
>> Det er alt for debugging dette program.
Er der nogen, der har nogen spørgsmål?
Hvad kommando kunne jeg ramt at afslutte GDB?
Q. Og så vil jeg blive bedt om, Afslut alligevel?
Ja eller nej.
Jeg får ramt ja, og jeg er holdt op GDB.
>> Så det var en hurtig primer til GDB.
Faktisk, i en virkelig situation, Jeg gjorde det på kontortid.
Jeg GDBed netop dette program på kontortid med en elev.
Og hvis vi går tilbage til de kommandoer, vi så før, vi brugte pause vigtigste først
ting vi gjorde.
Vi brugte køre med kommandolinjeargumenter, anden ting, vi gjorde.
Vi brugte næste en masse at flytte os gennem linjer.
Og igen, den korte version næste er n.
Det er i parentes gråt på diaset.
>> Vi brugte ikke skridt, men det gjorde vi ikke nødvendigvis i denne sag.
Men vi kan bruge det i en lidt senere på i dag, hvis vi debugging for
eksempel binær søgning, når binær søgning kaldes i en separat
funktion, men der er nogle fejl med det.
Vi kommer til at ønsker at træde ind i opkaldet til binær søgning og
faktisk debug det.
Liste vi ikke bruge enten fordi vi havde en god fornemmelse af vores kode, men hvis jeg
ønskede at få en fornemmelse af, hvad kode jeg var omkring, kunne jeg bare bruge listen.
>> Udskriv vi brugte, info locals vi brugt.
Fortsæt vi ikke behøver at bruge i denne tilfælde heller ikke vi skal bruge
deaktivere, men vi gjorde brug afslutte.
Igen, disse 10 kommandoer, praktisere dem.
Hvis du forstår disse 10 kommandoer, du skal være indstillet til debugging enhver
Problem med GDB.
>> Så vi er ved at gå på igen, til det springende punkt i dag, at gå over
disse sortering og søgning algoritmer.
Før vi gør det, igen, spørgsmål, kommentarer, bekymringer for GDB?
Så er alle kommer til at bruge GDB snarere end printf?
Så alle, for evighed skyld, alle nikker deres hoved ret
nu, så jeg vil se dig på kontortid og alle TFS vil se dig og
de vil sige, vise mig, hvordan man bruger GDB, og du vil være i stand
at vise dem, right?
Slags?
Måske forhåbentlig.
Fedt.
>> Så vi kommer til at flytte ind sortering og søgning.
Du vil se, at jeg har en liste allerede sorteres for os, men det vil ikke
at være tilfældet altid.
Så i det problem indstillet specifikation for problem sæt tre, du har shorts
at du kan se, og det faktisk beder dig om at se disse shorts.
Også i foredrag i sidste uge, gik vi over en masse af disse algoritmer, så jeg er
ikke kommer til at tilbringe tid i klassen går i løbet af disse algoritmer igen eller tegning
billeder til hvordan disse algoritmer virker.
Igen, at oplysninger, kan du re-watch foredrag, eller at oplysninger
er fanget fremragende på shorts for disse søgninger, som alle
som er tilgængelige på cs50.net.
>> Så i stedet for, hvad vi vil gøre, er at skrive disse programmer.
Vi har en følelse, en mental model af, hvordan de arbejder, og så hvad vi vil
at gøre, er at kode dem for alvor.
Vi kommer til at dreje, at mental model, det billede, hvis du vil, i det
faktiske kode.
Og hvis du var lidt forvirret eller diset på det mentale model, jeg er helt
forstå.
>> Vi er faktisk ikke kommer til at springe til kode samme.
Så mens denne prompt i dette dias spørger du at kode binær søgning, og
faktisk en iterativ version af binær søgning, den første ting jeg
virkelig ønsker dig at gøre, er skrive nogle pseudokode.
Så du har denne mentale model hvordan binær søgning værker.
Tag et ark papir, hvis du har en let tilgængelig, eller åbne en
tekst editor, og jeg vil gerne alle til at skrive.
Tage fire minutter til at skrive pseudokode for binær søgning.
>> Igen, så tænk på, at mental model.
Jeg kommer rundt, hvis du har spørgsmål og vi kan tegne billedet ud.
Men først, før vi begynder at programmering, Jeg vil gerne skrive
pseudokode for binær søgning, så når vi dykke i, har vi nogle retning som
til, hvor vi skal lede.
>> STUDENT: Kan vi antage den vifte af værdier, vi får, er allerede sorteres?
>> JASON HIRSCHHORN: Så for binær søgning at arbejde - glimrende spørgsmål - du
nødt til at tage i en sorteret matrix af værdier.
Så antager det vil virke.
Vi vil gå tilbage til dette dias.
Du vil se i lilla funktionen erklæringen er bool binary_search int
værdi, int værdier, int n.
Dette bør ser bekendt, hvis du har allerede nærmede sig eller fået din
hænder beskidte med problemet sæt.
>> Men det er din funktion erklæring.
Igen, ikke skulle have behov for at bekymre sig om at meget i dette øjeblik.
Hvad jeg virkelig ønsker dig at gøre er at tage fire minutter til pseudokoden binær
søge, og så vil vi gå over det som en gruppe.
Og jeg vil komme rundt.
Hvis du har spørgsmål, er du velkommen fri til at hæve din hånd.
>> Hvorfor tager du ikke tage to minutter mere at slutte op pseudokoden?
Jeg ved, at dette kan virke latterligt, at vi bruger så meget tid på
noget, der er ikke engang faktisk i C, men især for disse mere
udfordrende algoritmer og problem sæt, som vi er nødt til at regne ud,
starter i pseudokode ikke bekymre om syntaksen, bare bekymre sig om
logik, er utroligt hjælpsomme.
Og på den måde, du er ikke at løse to utroligt vanskelige problemer på én gang.
Du er bare fokusere på logik, og så du flytter ind i syntaks.
>> OK.
Lad os begynde at gå igennem pseudokode.
Jeg har skrevet op her, binær søg pseudokode.
Vi skriver dette på bord sammen.
Eller jeg vil skrive det, og du vil give mig anvisningerne, jeg har brug for.
Så kan nogen give mig den første linje i pseudokode du
skrev for binær søgning?
Ja, Annie?
>> STUDENT: Mens længden af listen er større end nul.
>> JASON HIRSCHHORN: Mens længden af listen er større end nul.
Og igen ser vi nogle C-leder syntaktiske ting på her.
Men det meste af dette er på engelsk.
Har nogen har nogen linje de lægger før dette i deres pseudo-kode?
>> STUDENT: Få et array af sorteret numre.
>> JASON HIRSCHHORN: Du skrev "får en vifte af sorterede numre. "Per den
funktion erklæring, vil vi passerer et array af sorteret numre.
>> STUDENT: [uhørligt].
>> JASON HIRSCHHORN: So vi vil have det.
Men ja, hvis vi ikke har det, vi vil være nødvendigt at sortere vores udvalg af
tal, fordi binær søgning kun virker på sorteret arrays.
Så mens længden af ​​listen er lig med nul, er jeg kommer til at sætte nogle krøllede parenteser
at gøre det ser lidt mere ligesom C. Men mens synes at kortlægge på en
mens loop, så inde i dette, mens loop hvad skal vi
gøre for binær søgning?
>> Nogen andre, der ikke har givet mig en svar endnu, men der skrev dette?
>> STUDENT: Gå til midten af ​​listen.
>> JASON HIRSCHHORN: Tom.
Gå til midten af ​​listen.
Og opfølgende spørgsmål, hvad gør vi, når vi er på
midt på listen?
>> STUDENT: Har en check, om der er det nummer, du leder efter.
>> JASON HIRSCHHORN: Excellent.
Gå midt på listen, og tjek hvis vores værdi er der -
fantastisk.
Har nogen har noget andet der var anderledes end dette?
Det er helt rigtigt.
>> Det første, vi gør i binær søgning er at gå til midten af ​​listen og
at se, om vores værdi er der.
Så jeg antager, hvis vores værdi er der, hvad gør vi?
>> STUDENT: Vi vender tilbage nul [uhørligt].
>> JASON HIRSCHHORN: Ja, hvis vores værdien er der, vi fandt det.
Så vi kan fortælle en eller anden måde, men dette funktion er defineret, vi fortælle brugeren
vi fandt det.
Hvis det ikke er der, selvom, det er hvor det bliver tricky.
Så hvis det ikke er der, en anden, der arbejdede på binær søgning eller
har en idé nu, hvad gør vi?
>> STUDENT: Spørgsmål.
>> JASON HIRSCHHORN: Ja?
>> STUDENT: Er array allerede sorteres?
>> JASON HIRSCHHORN: Ja, vi antager array allerede sorteret.
>> STUDENT: Så du er nødt til at kontrollere, om den værdi, du ser, er større end
den værdi, du ønsker, kan du flytte til midten af ​​den anden halvdel.
>> JASON HIRSCHHORN: Så hvis midten af listen er større end hvad vi
søger, så vi hvad?
Vi bevæger hvor?
>> STUDENT: Du ønsker at flytte til den halvdel af listen med
lavere antal end det.
>> JASON HIRSCHHORN: Så vi vil kalde det venstre.
Så hvis midten er større, kan vi søge venstre halvdel af listen.
Og derefter ved søgning, hvad mener jeg med søgning?
>> STUDENT: [uhørligt].
>> JASON HIRSCHHORN: Vi går til midten.
Vi har faktisk gentage denne ting.
Vi går tilbage gennem vores while-løkke.
Jeg vil give dig den sidste -
andet, hvis midten er mindre end hvad vi gør, hvad gør vi her?
>> STUDENT: Gå til højre.
>> JASON HIRSCHHORN: Søg til højre.
Det ser godt ud, men nogen har noget, som vi kan mangle eller
noget andet, som du sætter i din pseudo-kode?
Så dette er hvad vi har hidtil.
Mens længden af ​​listen er større end nul, vi kommer til at gå
til midten af ​​listen og kontrollere, om vores værdi er der.
>> Hvis den midterste er større, vil vi søg venstre, ellers hvis midten er
mindre, vi kommer til at søge mod højre.
Så vi har alle haft et vist kendskab til de vilkår, vi bruger i datalogi
og de værktøjer, vi har.
Men du vil allerede mærke at vi var tale på engelsk, men vi fandt en
masse ting, som syntes at kortlægge på redskaber, vi har i vores kodning værktøjskasse.
Så ret off the bat, vi er ikke vil faktisk kode endnu.
>> Hvad ser vi her på engelsk, at kortene på ting, vi kan skrive i C?
>> STUDENT: Mens.
>> JASON HIRSCHHORN: Mens.
Så dette, mens lige her kort på hvad?
>> STUDENT: En while-løkke.
>> JASON HIRSCHHORN: Et stykke loop?
Eller sandsynligvis mere generelt en løkke.
Vi ønsker at gøre noget igen og igen.
Så vi kommer til at kode en løkke.
Og vi allerede kender, fordi vi har gjort dette et par gange, og vi
har masser af eksempler derude, hvor faktisk at skrive
dette indeks til en sløjfe.
Så det bør være temmelig nemt.
Vi bør være i stand til at få det startede temmelig hurtigt.
>> Hvad ser vi her?
Hvilke andre strukturer grammatikker, tingene at vi er bekendt med i C, så gør vi
allerede har en følelse af baseret off af de ord, vi har brugt?
Ja, Anna?
[Uhørligt]
just kidding.
Anna, gå videre.
>> STUDENT: Hvis og andet.
>> JASON HIRSCHHORN: Hvis og andet - lige her.
Så hvad gør de ud?
>> STUDENT: An hvis ellers erklæring.
>> JASON HIRSCHHORN: Ja, betingelser, right?
Så vi vil sandsynligvis nødt til at skrive nogle betingelser.
Og igen, selvom måske forvirrende ved første, vi generelt har en mening nu
af hvordan man skriver betingelser og syntaksen for forhold.
Og hvis vi ikke gør det, vi bare kigge op syntaks for forhold, klippe og indsætte
at fordi vi ved, at vi brug for en betingelse her.
Alle andre ting, vi ser, at kortet på ting, vi måske nødt til at gøre i C?
Ja, Aleha?
>> STUDENT: Det kan være indlysende, ved blot at kontrollere, hvis en
værdi er lig med noget.
>> JASON HIRSCHHORN: Så hvordan kan vi kontrollere og - så gå til midten af ​​listen
og kontrollere, hvis vores værdi er der?
Hvordan gør vi det i C?
Hvad er syntaksen for det?
>> STUDENT: Lig, lig.
>> JASON HIRSCHHORN: Lig, lig.
Så denne kontrol er sandsynligvis kommer at være et lighedstegn, lig.
Så vi vil vide, at vi har brug for, at et eller andet sted.
Og faktisk, bare i at skrive det, vi ser de andre ting.
Vi er nødt til at gøre nogle sammenligning operatører derinde -
fantastisk.
Så det faktisk ser ud, ved og stor, har vi ikke skrevet en
ord af C-kode endnu.
Men vi fik den mentale model ned via foredrag og disse shorts.
>> Vi skrev pseudo-kode som en gruppe.
Og allerede, vi har 80%, hvis ikke 90% af, hvad vi skal gøre.
Nu er vi bare nødt til at kode det, som igen er en
ikke-trivielt problem at løse.
Men i det mindste er vi fast på logik.
Mindst nu når vi går til kontortid, Jeg kan sige, jeg ved hvad jeg har brug for
at gøre, men du kan minde mig af syntaksen?
Eller selv om der overfyldt kontortid, du kan google for syntaks, snarere
end at blive hængende på logik.
>> Og igen, snarere end at forsøge at løse logik og syntaks problemer alle
på én gang, er det ofte meget bedre at bryde disse to vanskelige problemer ud i
to mere håndterbare dem og gøre det pseudokode først og derefter kode i C.
Så lad os se, hvad jeg gjorde for pseudo-kode i forvejen.
>> Mens længden af ​​listen er større end nul, se på den midterste
af listen.
Hvis antallet fundet returnerede sandt, ellers hvis tal højere, søg venstre.
Else hvis antallet er lavere, søg højre, return false.
Så ser næsten identiske, hvis ikke næsten identisk med, hvad vi skrev.
Faktisk, Tom, hvad du sagde først, bryde midten af ​​listen, og hvis
nummer findes i to erklæringer er faktisk, hvad jeg gjorde.
>> Jeg kombinerede dem der.
Jeg skulle have lyttet til du første gang.
Så det er pseudo-kode, vi har.
Hvis du ønsker at nu, undskyld, gå tilbage til vores oprindelige problem.
Lad os kode binary.c.
Så implementere en iterativ udgave af binær søgning ved hjælp af følgende
funktion erklæring.
>> Og du behøver ikke at kopiere det ned endnu.
Jeg er faktisk kommer til at åbne op lige her binary.c.
Så der er den funktion erklæring i midten af ​​skærmen.
Og du vil se, at jeg tog pseudo-kode fra på mine sider, men næsten identiske
til, hvad vi skrev, og sætte det i for dig.
Så nu, lad os tage fem minutter at kode denne funktion.
>> Og igen, hvis du har spørgsmål, hæve din hånd, lad mig vide, vil jeg
kommer rundt.
>> STUDENT: [uhørligt].
>> JASON HIRSCHHORN: Så jeg tog den binære søg definition på
top, på linje 12.
Det er, hvad jeg fik for mine dias.
Og så alt dette pseudo-kode jeg lige kopieres og indsættes fra dias,
pseudo-kode dias.
Jeg er stadig ikke høre [uhørligt].
>> Så hvis du er færdig med din implementering, vil jeg tjekke det.
Jeg mailede dig helpers.h fil tidligere i denne klasse.
Og det vil være tilgængelige online såvel til download for mennesker ser
denne sektion tid forsinket.
Og jeg brugte bare den generiske fordeling kode fra pset3.
Så jeg tog find.C, bruge min helpers.h fil snarere end helpers.h fil
der er givet i fordelingen kode.
>> Og jeg havde at gøre en anden ændring i find.C snarere end at ringe simpelthen
søg, ring binary_search.
Så hvis du ønsker at teste din kode, vide, at det er sådan, man gør det.
I virkeligheden, når vi skal køre denne kode lige nu, jeg har lige lavet en kopi af
min pset3 mappe, igen, byttet ud de hjælpere filer og derefter foretaget, at
ændre i find.C at kalde binary_search snarere end blot at søge.
>> JASON HIRSCHHORN: Ja.
Har du spørgsmål?
>> STUDENT: Nevermind.
>> JASON HIRSCHHORN: Ingen bekymringer.
Nå, lad os komme i gang.
Vi vil kode det som en gruppe.
En anden tone.
Igen, dette er, kan nemt byttes i for Problem Set Tre.
Jeg har min helpers.h fil, som snarere end helpers.h vi er givet,
erklærer binær søgning, boble sortere og udvælgelse slags.
Og i find.c du vil opdage på linje, hvad er det, linje 68, vi kalder binær
søg snarere end søgning.
Så igen, den kode, der er til rådighed online eller den kode, du er
skaber lige nu let kan byttes i for p sæt 3 til at tjekke det.
>> Men først, lad os kode binær søgning.
Vores funktion erklæring, vi returnere en bool.
Vi tager et heltal kaldet værdi.
Vi tager et array af heltal kaldet værdier, og vi tager n være
størrelsen af ​​matrixen.
På linje 10, lige her, jeg har skarp omfatter stdbool.h.
Er der nogen vide, hvorfor det er der?
Så hvad betyder det linje kode gøre?
>> STUDENT: Det giver dig mulighed for at bruge en bool returtype.
>> JASON HIRSCHHORN: Præcis.
>> STUDENT: Eller det er et bibliotek, der giver mulighed at anvende en bool returtype.
>> JASON HIRSCHHORN: Så den skarpe omfatte stdbool.h linje giver mig nogle
definitioner og erklæringer for ting at jeg får lov til at bruge i
dette bibliotek.
Så blandt dem siger, at der er denne type kaldes bool, og det kan være
sandt eller falsk.
Så det er hvad denne linje gør.
Og hvis jeg ikke havde denne linje, jeg ville komme i problemer for at skrive dette
ord lige her, bool, lige der.
Præcis højre.
Så jeg har brug for, at der i denne kode.
OK.
Så dette igen, er en iterativ version, der ikke en rekursiv én.
Så lad os komme i gang.
>> Lad os starte med denne første linje pseudokode.
Og forhåbentlig vil vi - eller ikke forhåbentlig.
Vi kommer til at gå rundt i lokalet.
Vi vil gå linje for linje, og jeg vil hjælpe du regne ud den linje, vi har brug for
skrive først.
Så mens længden af ​​listen er større end nul.
Lad os starte i front.
Hvilken linje skal jeg skrive her, i koden?
>> STUDENT: Mens parentes n er større end 0.
>> JASON HIRSCHHORN: Mens n er stor end 0.
Så n er størrelsen af ​​en liste, og vi tjekker, om -
>> [indskyde STEMMER]
>> JASON HIRSCHHORN: - undskyld?
>> STUDENT: Hvordan kan vi vide, at n er størrelsen på listen?
>> JASON HIRSCHHORN: Undskyld.
Per PSET specifikationen søgningen og sortere funktioner du har brug for at skrive,
n er størrelsen på listen.
Jeg glemte at forklare det her.
Men ja. n er størrelsen af listen, i dette tilfælde.
Så mens n er større end 0.
OK.
Det kan vise sig lidt problematisk selv, hvis tingene går videre.
Fordi vi vil fortsætte med at kende størrelsen på listen i denne
funktion, men siger vi starter med en vifte af 5 heltal.
Og vi går igennem, og vi har nu indsnævret det ned til
et array af to heltal.
Hvilket 2 heltal er det?
Størrelsen er 2 nu, at vi ønsker at se på, men som 2 er, at?
Giver det mening, det spørgsmål?
>> OK.
Jeg spørger igen.
Så vi starter med denne række af 5 heltal, og n er lig med 5, right?
Vi kører igennem her.
vi sandsynligvis ændre størrelsen, ret, da tingene går videre.
Hvilket er, hvad vi siger, vi ønsker at gøre.
Vi ønsker ikke at søge fuld ting igen.
Så siger vi ændre det til 2..
Vi tager halvdelen af ​​den liste, der er mærkeligt.
Så bare vælge 2.
Så nu n er 2.
Jeg undskylder for de fattige tør slette markører.
Right?
Og vi søger gennem listen igen med en liste over str. 2.
Tja, vores array er stadig af str. 5.
Vi siger, at vi kun ønsker at søg 2 pletter i det.
Så der 2 spots er dem?
>> Giver det mening?
Er de venstre 2 spots?
Er det de rigtige 2 spots?
Er de de 2 midterste spots?
Vi har brudt problemet ned, men vi faktisk ikke ved, hvilken del af
det problem, vi stadig kigger på, bare ved at have disse to variable.
Så vi har brug for lidt mere derefter, mens n er større end 0.
Vi har brug for at vide, hvor der n er i vores faktiske array.
>> Så nogen har en skifte til denne linje?
Det meste af denne linje er helt korrekt.
Er der en anden tilføjelse?
Kan vi bytte noget ud for n til gøre denne linje en smule bedre?
Mm-hm?
>> STUDENT: Kan du initialisere en variabel såsom længde til n, der vil så blive brugt
senere i funktion?
>> JASON HIRSCHHORN: Så initialisere en variabel længde n,
og vi bruger det senere?
Men så har vi bare opdatere længde og vi stadig løbe ind i dette problem, hvor vi
skære ned på længden af ​​vores problem, men vi ved aldrig, hvor, faktisk,
denne længde kort på.
>> STUDENT: Er det ikke kommer til at ske senere, når du siger, søg venstre,
søg ret?
Du kommer til at gå til en anden område af dit -
>> JASON HIRSCHHORN: Vi kommer til at gå til et område, men hvordan kan vi vide
der er til at gå til?
Hvis vi kun har array, og dette n, hvordan kan vi vide, hvor man
gå i arrayet.
I ryggen, ja?
>> STUDENT: Har du, ligesom, en lavere grænse og en øvre grænse variabel eller
sådan noget?
>> JASON HIRSCHHORN: OK.
Så dette er en anden idé.
Snarere end blot at holde styr på størrelse, vi holde styr på den nedre og
øvre grænse variabel.
Så hvordan kan vi beregne størrelsen fra en nedre grænse og øvre grænse?
>> [indskyde STEMMER]
>> JASON HIRSCHHORN: subtraktion.
Og også at holde styr på den nederste bundet og øvre grænse at lade os vide,
Vi søger disse to?
Er vi søger disse to herovre?
Er vi søge på to midten?
Sandsynligvis ikke de to midterste, fordi dette i virkeligheden er binær søgning.
Men nu vil vi være i stand til at få den størrelse, men også for rammerne af arrayet.
I det væsentlige, hvis vi har vores kæmpe telefonbog, vi rippe den i halve.
Vi ved nu, hvor der er mindre telefonbog er.
Men vi er faktisk ikke rippe telefonbogen i halve.
Vi har stadig brug for at vide, hvor nye grænser for vores problem er.
Er der nogen har nogen spørgsmål om det?
Ja?
>> STUDENT: Ville det fungere ved at skabe en variabel, i, at man så bare flytte
stilling i forhold til dens aktuelle position, og længden, n?
>> JASON HIRSCHHORN: Og hvad er jeg?
>> STUDENT: Ligesom jeg er ligesom en slags -
Ligesom du ville initialisere jeg at være den midterstilling af matrixen.
Og derefter, hvis værdien på position i i midten af ​​arrayet i fundet
være mindre end den værdi, du har brug for, jeg nu bliver længden af ​​array plus
værdien af ​​i divideres med 2.
Ligesom, se du skifte i -
>> JASON HIRSCHHORN: Right.
>> STUDENT: - op til -
>> JASON HIRSCHHORN: Så jeg er næsten positive, der vil arbejde.
Men pointen væsen, skal du to stykker af information her.
Du kan gøre det med begyndelsen og slutningen, eller du kan gøre det med størrelse, og derefter
nogle markør.
Men du behøver to stykker af information her.
Du kan ikke komme af med blot én.
Betyder det giver mening?
>> Så vi kommer til at gå igennem, og vi kommer til at gøre [uhørligt]
og skabe nogle markører.
Hvad lavede du skriver i din kode?
>> STUDENT: Jeg sagde bare int bundet en er lig med 0.
>> JASON HIRSCHHORN: Lad os kalde at int, begynder.
>> STUDENT: OK.
>> JASON HIRSCHHORN: Det gør mere mening for mig.
Og?
>> STUDENT: Jeg sagde, jeg gætte, int slutter.
>> JASON HIRSCHHORN: int slutter.
>> STUDENT: Jeg gætter på, n minus 1, eller noget lignende.
Ligesom, det sidste element.
>> JASON HIRSCHHORN: Så du skrev, int begynder lig 0 semikolon og int
slutning er lig n minus 1, semikolon.
Så det væsentlige, hvad vi gør her, 0 den første position.
Og som vi ved i arrays, de ikke går op til n, de går op til n minus 1.
Så vi har nogle grænser i vores array.
Og disse indledende grænser tilfældigvis de oprindelige grænser for vores problem.
OK.
Så det lyder godt.
Så hvis vi går tilbage til denne linje, mens længden af ​​listen er større end 0,
hvad stedet for n, bør vi sætter i her?
>> STUDENT: Skriv slutter minus begyndelsen.
>> JASON HIRSCHHORN: Mens slutter minus begynder er større end 0?
OK.
Og vi kunne, hvis vi ønskede at gøre, at en lidt pænere, hvad
ellers kunne vi gøre?
Hvis vi ønskede at rense denne kode lidt op?
Hvordan kan vi slippe af med 0?
Dette er blot en stil spørgsmål.
Det er korrekt, lige nu.
>> STUDENT: Afslutning ikke lige begyndelse?
>> JASON HIRSCHHORN: Vi kan gøre hvad?
>> [indskyde STEMMER]
>> STUDENT: Ending er større?
>> JASON HIRSCHHORN: Ja.
Vi kan bare gøre, mens slutter er større end begyndelsen.
Right.
Vi har tilføjet begyndt til den anden side af det, og vi sluppet af 0.
Så dette ser bare en lidt renere.
OK.
Så mens længden af ​​listen er 0, skrev vi at mens slutter, er større
end begyndelsen.
Vi kommer til at sætte i vores nødvendig krøllede parenteser, og derefter den første ting
vi ønsker at gøre, er at se på dem i en lille liste.
Dig?
Kan du give mig det -
>> STUDENT: Hvis parentes værdi firkantet beslag -
>> JASON HIRSCHHORN: Hvis parentes værdi firkantet beslag.
>> STUDENT: Ending divideres med 2.
>> JASON HIRSCHHORN: Ending?
>> STUDENT: Jeg ser et problem med din -
>> JASON HIRSCHHORN: OK.
Tja, se på midten.
Hvordan kan vi vide, hvad den midterste er?
Ja.
Så lad mig slette denne kode.
Hvordan kan vi vide, hvad den midterste er?
I noget, når du har begyndelsen og enden, hvordan kan du finde
midten?
>> STUDENT: Du gennemsnittet.
>> STUDENT: Du tilføjer dem sammen og derefter -
>> JASON HIRSCHHORN: Tilføj dem sammen og derefter?
>> STUDENT: Og du gennemsnittet.
Dividere det med 2..
>> JASON HIRSCHHORN: Tilføj dem sammen og dividere med 2..
Så int midterste lig?
Tom, kan du give mig det?
>> STUDENT: Begyndelsen plus slutter -
>> JASON HIRSCHHORN: Begyndelsen plus slutter.
>> STUDENT: Alle, beslag, divideret med 2..
>> JASON HIRSCHHORN: Alle, i parentes, divideret med to.
Så det giver mig den midterste af noget, korrekt?
>> STUDENT: Du skal også til at runde det op.
>> JASON HIRSCHHORN: Hvad gør du mener, jeg har brug for at runde det op?
>> [indskyde STEMMER]
>> STUDENT: Fordi hvis det er et ulige nummer, så er det ligesom -
>> JASON HIRSCHHORN: Nå, OK.
Så jeg kunne runde det op.
Men hvis det er et ulige antal, 5, kan jeg idet 1 væk fra midten.
Eller hvis det er et lige tal, snarere der er en bedre sag.
Hvis det er 4, har vi kun 4, kan jeg tage den første "midten", citat, citat slut eller
den anden "midten" en.
Enten ville arbejde for en binær søgning, så jeg behøver faktisk ikke at runde det.
Men der er en anden ting, jeg nødt til at se på denne linje.
Vi er måske ikke klar over det endnu, men vi vil vende tilbage til det.
Da denne linje faktisk stadig brug en anden ting.
>> Men indtil videre har vi skrevet fire linjer kode.
Vi har fået vores start og slutter markører.
Vi har vores while-løkke, der kortlægger på direkte til vores pseudokode.
Vi kigger på midten, der kortlægger direkte på vores pseudokode.
Jeg vil sige dette går til midten af listen, denne linje kode.
Og så, når vi går til midten af listen, den næste ting, vi skal gøre
er kontrollere, om vores værdi er der for pseudokoden vi skrev tidligere.
>> Så hvordan kan vi kontrollere, om vores værdi er midten af ​​listen?
Dig.
Hvorfor kan du ikke gøre det?
>> STUDENT: Hvis vores værdi er er på midten er lig med
hvad vi indstiller -
Jeg mener lige lig -
>> JASON HIRSCHHORN: It -
OK.
>> STUDENT: Jeg er ikke sikker på, hvad variabel vi leder
for selv om, er, fordi -
>> [indskyde STEMMER]
>> STUDENT: [uhørligt].
>> JASON HIRSCHHORN: Præcis.
Per funktionen erklæring, vi leder efter en værdi.
Så vi søger efter en værdi i en vifte af værdier.
Så du er helt rigtigt.
Du vil gøre, hvis den er åben parentes værdi beslag midten lukket beslag ligemænd
lig værdi, og inde er der hvad skal vi gøre?
Hvis vores værdi er der, hvad skal vi gøre?
>> [indskyde STEMMER]
>> STUDENT: Tilbage nul.
>> JASON HIRSCHHORN: Return sandt.
>> STUDENT: Return sandt.
>> JASON HIRSCHHORN: Michael, hvad betyder denne linje gøre?
>> STUDENT: [uhørligt] programmet har kørt dens forløb, og der er over, og
du har, hvad du skal gøre?
>> JASON HIRSCHHORN: Programmet eller hvad?
I dette tilfælde?
>> STUDENT: Den funktion.
>> JASON HIRSCHHORN: Den funktion.
Og så for at vende tilbage til, hvad der kaldes det og give det den værdi, sandt.
Præcis højre.
Main.
Hvad er returtypen af hoved, Michael?
>> STUDENT: int, heltal?
>> JASON HIRSCHHORN: int, nøjagtigt.
Et heltal.
Det var bare et spørgsmål for at sikre, du fyre har været på toppen af ​​det.
Hvad betyder det normalt vender tilbage, hvis alle tingene fungerer godt?
>> STUDENT: Zero.
>> JASON HIRSCHHORN: Zero.
Præcis højre.
>> STUDENT: Hvis det bare returnerer true, der er ingen oplysninger bliver givet
om hvad -
Åh, er det bare at sige, at der værdi der er inde i array.
>> JASON HIRSCHHORN: Præcis.
Dette program er ikke at give oplysninger hvor nøjagtig værdi.
Det er kun at sige, ja, vi fandt det, eller nej, vi ikke finde det.
Så hvis nummer findes, returnere sandt.
Tja, faktisk vi bare gjorde det rigtig hurtigt med at en linje kode.
Så jeg vil flytte denne linje af pseudokode.
>> STUDENT: Har vi ikke brug for at ændre array?
Det bør være værdier, ikke værdi, right?
>> JASON HIRSCHHORN: Undskyld.
Tak.
>> STUDENT: Ja.
>> JASON HIRSCHHORN: Denne linje bør være værdier.
Præcis højre.
OK.
Så vi har kigget på den midterste liste.
Hvis antallet fundet afkast sandt.
Fortsætter med vores pseudokode, hvis midten er større, søg venstre.
Så jeg havde i her, hvis nummer højere, søg venstre.
Konstantin, kan du give mig denne linje kode?
>> STUDENT: Hvis værdien af ​​midten -
>> JASON HIRSCHHORN: Så hvis værdi -
hvis åben parantes værdier beslag midterste close beslag -
>> STUDENT: Er mindre end værdi?
>> JASON HIRSCHHORN: Er mindre end.
>> STUDENT: Mindre end værdi.
>> JASON HIRSCHHORN: Værdi.
Tja, faktisk, du ønsker at kontrollere, om nummeret -
Undskyld.
Det er lidt forvirrende.
Men ellers hvis antallet i midten af ​​listen er større.
>> STUDENT: Åh, OK.
>> JASON HIRSCHHORN: Jeg vil ændre det.
Else hvis midten er højere, vi vil søge venstre, OK?
Og hvad gør vi inde dette, hvis tilstand?
>> STUDENT: Kan jeg lave en lille ændring i den tilstand, ændre det til andet, hvis?
>> JASON HIRSCHHORN: Else nu hvis?
OK.
Så denne kode vil køre om det samme.
Men det gode ved at bruge, hvis ellers hvis ellers hvis eller hvis ellers hvis ellers
betyder, at kun en af ​​dem kommer til at skal kontrolleres, ikke alle tre af dem,
potentielt.
Og det gør det en lille smule pænere på den computer, der er
kører dit program.
>> Så [? Konstantin,?]
Vi er inde i denne linje, ellers hvis værdier beslag midten luk beslag
er større end værdi.
Hvad skal vi gøre?
Vi har brug for at søge venstre.
Hvordan gør vi det?
Jeg har tænkt mig at give dig en start.
>> Vi har disse to ting kaldet begynder og slutter.
Så hvad der skal ske til begyndelsen?
Hvis du ønsker at søge venstre for liste, vi får vores nuværende begyndelsen.
Hvad skal vi gøre det?
>> STUDENT: Vi sætter begyndelsen til midten plus 1.
>> JASON HIRSCHHORN: Så hvis vi er søge på venstre?
>> STUDENT: Beklager, midterste minus -
så slutningen ville være midten minus 1 og begyndelsen -
>> JASON HIRSCHHORN: Og hvad sker til begyndelsen?
>> STUDENT: Det forbliver den samme.
>> JASON HIRSCHHORN: Så betydning forbliver den samme.
Hvis vi søger til venstre, er vi anvendelse af den samme begyndelse -
helt rigtigt.
Og det slutter?
Undskyld, hvad gør slutter lige igen?
>> STUDENT: Middle minus 1.
>> JASON HIRSCHHORN: Middle minus 1.
Nu, hvorfor minus 1, ikke bare midten?
>> STUDENT: Den midterste er ude af billedet allerede, fordi vi havde
kontrolleret, at det er ude?
>> JASON HIRSCHHORN: Det er helt rigtigt.
Midten er ude af billedet.
Vi har allerede tjekket midten.
Så vi ønsker ikke "i midten", citat citat slut, at fortsætte med at være i
array, vi leder.
Så det er fantastisk.
>> Else hvis værdier beslag midten er større end værdien slutter ligemænd
midterste minus 1.
Jeff, hvad med denne sidste linje?
>> STUDENT: Else.
Værdier midten er mindre end værdi?
>> JASON HIRSCHHORN: Vi vil du giver mig andet.
Så hvis du ikke giver mig -
>> STUDENT: Så begynder ville være midten plus 1.
>> JASON Hirschhorn: Begyndelsen ligemænd midten plus 1 igen for den samme
grunden til, at Constantine gav os tidligere.
Og til sidst, er der ikke givet mig en linje kode endnu?
Return false, Aleha, hvad vi skriver her?
>> STUDENT: Tilbage falsk.
>> JASON HIRSCHHORN: Tilbage falsk.
Og vi har brug for at gøre det, for hvis vi finder det ikke, er vi nødt til at sige, at vi
kunne ikke finde det.
Og vi sagde, at vi kommer til at returnere en bool, så vi helt sikkert nødt til at vende tilbage
en bool et eller andet sted.
>> Så lad os køre denne kode.
Jeg er faktisk at gå til -
så vi er i terminalen.
Vi vil rydde vores vindue.
Lad os gøre hele.
Vi fandt der er en fejl.
Der er en fejl på linje 15, der forventes semikolon ved udgangen af
erklæring.
Så hvad gjorde jeg glemme?
>> STUDENT: semikolon.
>> JASON HIRSCHHORN: Semikolon lige heroppe.
Jeg tror, ​​det var Toms kode.
Så Tom, [uhørligt].
Just kidding.
Lad os gør alt igen.
>> STUDENT: Hvad Dropbox mappe bør vi være i til dette?
>> JASON HIRSCHHORN: Så du kan bare se for denne bit.
Men igen, hvis du ønsker at flytte denne kode i din pset3 mappe til prøve
det ud, det er, hvad jeg gjorde.
Hvis du lægger mærke til her - undskyld, godt spørgsmål.
>> [? LS,?]
Jeg har i her find.c kode fra denne uges distro kode.
Jeg har helpers.h.
Jeg har en Make-fil, som jeg faktisk redigeret en smule til også at omfatte disse nye
filer, vi skriver.
Alt dette kodeks vil være til rådighed, ikke fordelingen kode, men den nye
Gør fil, den nye helpers.h filen være tilgængelige online til download.
Igen, så det er de ekstra koder, vi har.
>> Så gør alt, pr denne linie gør finde, binær, boble valg - gør
alle tre af dem og samler ind denne eksekverbar kode fund.
Så generelt, ønsker vi ikke til lige til check50.
Vi ønsker at køre nogle tests på vores egen.
Men lige så vi kan fremskynde det en smule, check50 2013 pset3.find vil passere
i helpers.c-- mit dårlige.
>> Jeg har ikke lige nu.
Så vi faktisk kommer til at køre koden for alvor.
Usage.find /, ved du hvad det betyder?
>> STUDENT: Du har brug for en anden kommandolinjen på det.
>> JASON HIRSCHHORN: Jeg har brug for en anden kommandolinje.
Og pr specifikationen, jeg har brug for at indtaste, hvad vi leder efter.
Så lad os se efter 42.
Vi vil holde det i sorterede, fordi vi har ikke skrevet en slags funktion endnu -
42, 43, 44.
>> Og Kontrol D ikke fandt nål i en høstak.
Det er dårlige.
Det er helt sikkert der.
Lad os prøve noget andet.
Måske er det fordi jeg sætter det i begyndelsen.
>> Lad os gøre 41, 42, 43.
Der vi går.
Den fandt det.
Lad os sætte det i slutningen nu, bare så vi kan være grundig -
40, 41, 42.
Fandt du ikke finde nålen.
Så jeg nævnte dette tidligere.
Desværre, jeg vidste dette skulle ske.
>> Men for pædagogiske formål, det er godt at udforske det.
Det fungerer ikke.
Af en eller anden grund, kan den ikke finde den.
Vi ved, hvad der er derinde, men vi ikke finde det.
Så én ting, vi kan gøre, er at gå igennem GDB at finde det, men gør nogen,
uden at gå gennem GDB, har en fornemmelse af, hvor vi skruet op?
[? Madu? ?]
>> STUDENT: Jeg tror, ​​det kan være, når slutter er lig med begyndelsen, og det er
blot en en-element listen.
Så er det bare ignorerer det i stedet for faktisk at kontrollere det.
>> JASON HIRSCHHORN: Det er helt rigtigt.
Når slutning lig begyndelsen, gør vi stadig har et element i vores liste?
>> STUDENT: Ja.
>> JASON HIRSCHHORN: Ja, i virkeligheden, vi har én og kun ét element.
Og det vil sandsynligvis ske, når, per den kode, vi testede, vi er ved
foran høstak eller slutningen af ​​høstak.
Det er, hvor begyndelsen og slutning kommer til at lige
en, med binær søgning.
Så i disse to tilfælde er det ikke virkede, fordi slutter var lig med begyndelsen.
>> Men hvis slutter er lig med starten betyder dette, mens løkken udføre?
Det gør det ikke.
Og vi kunne have kontrolleret der igen gennem GDB.
Så hvordan kan vi løse denne kode, fordi når mens slutter er lig med
begynder, vil vi også dette mens løkken til at køre.
>> Så hvad fix kan vi gøre til linje 18?
>> STUDENT: [uhørligt] er større end eller lig med.
>> JASON HIRSCHHORN: Præcis højre.
Mens slutningen er større end eller lig med begyndelsen.
Så nu, vi sørge for at få det hjørne tilfældet i slutningen.
Og lad os se.
Lad os køre dette endnu en gang.
>> Lad os gøre alle.
Igen, er du nødt til bare følge med her.
Find 41 denne gang.
Bare holde det konsekvent.
>> Find 42.
Lad os sige det i starten -
42, 43, 44.
Vi fandt det.
Så det var faktisk ændringen vi skulle gøre.
>> Det var en masse kodning vi lige gjorde, binær søgning.
Er der nogen har nogen spørgsmål, før Jeg flytter på i linjer, vi skrev i
binær søgning eller hvordan vi regnede ud af, hvad vi regne ud?
Før vi går videre, vil jeg også gerne påpege ud af, at store og hele, vi kortlagt
vores pseudokode en til én på vores kode.
>> Vi havde det tricky ting at finde ud af med det
begynder og slutter.
Men havde du ikke regnet det ud, du ville have skrevet temmelig
identisk kode, bortset disse top to linjer.
Og så ville du have indset, når du gjorde det i kontrol og sager,
du har brug for noget andet.
Så selv hvis du havde fulgt vores pseudo-kode linje for linje, ville du har
fået alle men to linjer af kode, du havde brug for at skrive.
>> Og jeg ville være villig til at vædde på, at du fyre ville have alt regnet det ud
temmelig hurtigt, at du havde brug for at sætte en slags markør i der at regne
ud af, hvor du var.
Det igen, er kraften i at gøre pseudo-kode i forvejen.
Så vi kan gøre logikken først, og derefter vi kan bekymre sig om syntaks.
>> Havde vi været forvirret over logikken mens du prøver at skrive denne kode i C,
vi ville have fået alle rodet op.
Og så ville vi være stille spørgsmål om logik og syntaks og meshing
dem alle sammen.
Og vi ville have fået tabt i, hvad der kan hurtigt blive en
meget vanskeligt problem.
Så lad os gå videre nu til valg slags.
>> Vi har 20 minutter tilbage.
Så jeg har en fornemmelse af, vi vil ikke være i stand til at komme igennem alle valg slags
og boble slags.
Men lad os i det mindste forsøg for at afslutte valget slags.
Så gennemføre valget sortere ved hjælp af følgende funktion erklæring.
>> Også denne taget fra problem sæt specifikationer.
Int værdier parenteser, er et array af heltal.
Og int.n er størrelsen af ​​denne array.
Valg slags går at sortere dette array.
>> Så per vores mentale model for udvælgelse sortere, vi trækker -
første, vi går gennem listen den første tid, finde det mindste tal,
sætte det i starten, finde den anden mindste tal, sætte det i
anden position, hvis vi ønsker at sortere i stigende rækkefølge.
Jeg er ikke tvinger dig til at skrive pseudo-kode lige nu.
>> Men før vi gør koden som en klasse i fem minutter, vi kommer til at skrive
pseudo-kode, så vi har nogle fornuft af hvor vi skal hen.
Så forsøge at skrive pseudo-kode på din egen.
Og derefter forsøge at slå denne pseudo-kode i kode.
Vi vil gøre det som en gruppe fem minutter.
>> Og selvfølgelig, så lad mig vide, hvis du har spørgsmål.
>> STUDENT: At det?
>> JASON HIRSCHHORN: Se hvor langt du kan komme i yderligere to minutter.
Jeg forstår dig ikke vil være i stand til at afslutte.
Men vi vil gå over dette som en gruppe.
>> Du er al kodning så [uhørligt], så jeg er ked af at holde pause, hvad du laver.
Men lad os gå igennem dette som en gruppe.
Og igen, binær søgning, du alle give mig en, hvis ikke flere linjer kode.
Tak for det.
Vi kommer til at gøre det samme her, kode sammen som en gruppe.
>> Så valg slags - lad os skrive nogle hurtige pseudo-kode.
Per mental model, kan nogen give mig den første linje i pseudo-kode, tak?
Hvad ønsker jeg at gøre?
>> STUDENT: Mens listen er ude af drift.
>> JASON HIRSCHHORN: OK, mens listen er ude af drift.
Og hvad mener du med "ude af drift?"
>> STUDENT: Mens [uhørligt]
ikke er sorteret.
>> JASON HIRSCHHORN: Mens listen er ude af drift, hvad gør vi?
Giv mig den anden linje, please, Marcus.
>> STUDENT: Så find den næste mindste tal.
Dette vil blive indrykket.
>> JASON HIRSCHHORN: Så find det næstmindste antal.
Og så en anden?
Når vi finder den næstmindste nummer, hvad gør vi?
Jeg har tænkt mig at sige finde det mindste antal.
Det er, hvad vi ønsker at gøre.
>> Så find det mindste antal.
Så hvad gør vi?
>> STUDENT: [uhørligt] til begyndelsen.
>> JASON HIRSCHHORN: Undskyld?
>> STUDENT: Placer den i begyndelsen af ​​listen.
>> JASON HIRSCHHORN: Så placere den i begyndelsen af ​​listen.
Og hvad gør vi for at de ting der var i begyndelsen
af listen, right?
Vi overskrive noget.
Så hvor skal vi sætte det?
Ja, Anna?
>> STUDENT: Hvor den mindste nummer var?
>> JASON Hirshhorn: Så læg begyndelsen af den liste, hvor
mindste tal var.
Så mens listen er ude af drift, finder det mindste antal, som anbringes i
begyndelsen af ​​listen, satte begyndelsen af ​​den liste, hvor
mindste tal var.
Marcus, kan du omformulere denne linje mens listen er i orden?
>> STUDENT: Selvom tallene ikke er sorteret?
>> JASON Hirshhorn: OK, så for at ved, at tallene ikke har været
sorteret, hvad skal vi gøre?
Hvor meget har vi brug for at gå gennem denne liste?
>> STUDENT: Så jeg gætte en for-løkke, eller mens mens cifrene kontrolleret er mindre
end længden af ​​listen?
>> JASON Hirshhorn: OK, det er godt.
Jeg tror, ​​jeg misphrased mit spørgsmål dårligt.
Jeg prøvede bare at komme på vi er nødt til at gå
gennem hele listen.
Så mens listen er ude af drift, for mig, er svært at kortlægge på.
Men dybest set, det er hvordan Jeg mener om dette.
Gå gennem hele listen, skal du finde mindste tal, placer den i
begyndelse - faktisk, du har ret.
Lad os sætte dem begge.
>> Så mens listen er ude af drift, vi nødt til at gå igennem hele listen
én gang, finde det mindste tal, sted det i starten af ​​listen, sætte
begyndelsen af ​​den liste, hvor mindste tal var og derefter, hvis det
Listen er stadig ude af drift, vi har kom til at gå gennem denne
processen igen, ikke sandt?
Det er derfor, udvælgelse sortere, Big-O runtime udvælgelse slags, anyone?
>> STUDENT: n potens.
>> JASON Hirshhorn: n potens.
Fordi ligesom Marcus og jeg har lige indset her, vi nødt til at
gå gennem listen liste antal gange.
Så går gennem noget af længde n n antal gange
er faktisk n potens.
>> Så dette er vores pseudokode.
Det ser meget godt ud.
Er der nogen har nogen spørgsmål om pseudokode?
Fordi faktisk udvælgelse slags bør sandsynligvis kommer den ene til en, kode fra
pseudokode.
Så spørgsmål om logik pseudokode?
Spørg det nu.
>> Valg slags - mens listen er ude af orden, vi kommer til at gå igennem det
og finde den mindste hver gang og sætte det i front.
Så mens listen er i orden, kan nogen give mig den linje kode, der
har ikke givet mig en linje kode endnu, please?
Det lyder som en hvad?
>> STUDENT: Det er en for-løkke.
>> JASON Hirshhorn: Det lyder gerne en for-løkke.
OK, kan du give mig for-løkken?
For -
>> STUDENT: Jeg lig 0.
>> JASON Hirshhorn: I eller -
hvad mangler vi?
Hvad går lige her?
>> STUDENT: Int.
>> JASON Hirshhorn: Præcis.
(Int i = 0; -
>> STUDENT: i <n, jeg + +).
>> JASON Hirshhorn: Nailed det, Jeff.
Vi går gennem listen, right?
Vi har set, at kode før.
Perfect.
Så lad os sætte vores krøllede parenteser her.
Jeg har tænkt mig at sætte nogle krøllede parenteser her.
>> Så mens det er 0, er vi nødt til at gå gennem hele listen.
Så hver gang vi gå gennem listen, Hvad ønsker vi at holde styr på?
>> STUDENT: Hvis nogle swaps foretages.
>> JASON Hirshhorn: Find det mindste antal.
Så vi skal nok holde styr på det mindste antal hver gang.
Så linje kan jeg gøre for at holde styr af det mindste tal?
Aleha, hvordan kan jeg beholde styr på noget?
>> STUDENT: Start en ny variabel.
>> JASON Hirshhorn: Start en ny variabel.
Så lad os oprette en variabel.
Hvilken type?
>> STUDENT: Int.
>> JASON Hirshhorn: Int.
Lad os kalde det det mindste.
Og hvad betyder det lige, når vi er lige begyndt?
Vi har ikke gået gennem listen endnu.
Vi er ved første del af liste vores første gang igennem.
Hvad gør det lige, mindste tal?
>> STUDENT: værdier, jeg.
>> JASON Hirshhorn: værdier, jeg.
Det lyder helt rigtigt, ikke?
Det mindste antal i begyndelsen er, hvor vi er.
Så nu har vi vores mindste, og vi har brug for at gå gennem hele listen og
sammenligne dette mindste til alt andet.
Så går vi hen gennem listen igen?
Michael?
>> STUDENT: Du er nødt til at gøre anden for løkke.
>> JASON Hirshhorn: Endnu for loop.
Lad os gøre det.
Giv mig noget kode.
>> STUDENT: For loop -
for de mindste -
bare int j, kan man sige?
= 0, således at -
>> JASON Hirshhorn: Jamen, hvis vi ønsker at gå igennem hele listen -
>> STUDENT: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
Vi kommer til at gå igennem for-løkken igen.
Og hvordan finder vi den mindste tal?
Tom?
Vi har den nuværende mindste tal, så hvordan finder vi den nye mindste?
>> STUDENT: Vi kan kontrollere, om den mindste tal, vi har, er større end
værdier beslag j.
>> JASON Hirshhorn: Så hvis mindste er større end værdier beslag j.
Så hvis vores nuværende mindste er større end -
Jeg har tænkt mig at flytte disse to linjer kode derude for et sekund.
Fordi før vi gør noget swapping, vi nødt til at gå igennem hele listen.
Så dette pseudokode burde faktisk være uden for den indre for-løkke.
Så gå igennem hele listen.
Hvis mindste er større end værdier j hvad så?
>> STUDENT: Så mindste lig værdierne j.
>> JASON Hirshhorn: Fantastic.
Et hurtigt spørgsmål -
første gang vi går gennem denne løkke, Jeg kommer til at være lig med 0, er j går
til lig med 0, når vi kommer her.
Så vi kommer til at sammenligne et nummer til sig selv.
Er det effektivt?
Nej, det er ikke rigtig effektiv.
Så gør vores j nødt til at gå fra 0 til n hver gang?
Har vi altid nødt til at tjekke gennem hele listen?
[Uhørligt]?
>> STUDENT: Start med i stedet for.
>> JASON Hirshhorn: j dåse starte med hvad?
>> STUDENT: i.
>> JASON Hirshhorn: j kan starte med jeg.
Så nu er vi sammenligne starter med den, vi er på.
Men selv da, er det som effektiv som muligt?
>> STUDENT: i + 1.
>> JASON Hirshhorn: i + 1 synes at være de mest effektive, fordi vi
allerede har jeg.
Vi angiver, at da mindste i linie 15.
Vi kommer til at starte med næste automatisk.
Så vi går igennem for-løkken.
Vi vil gå igennem hver gang.
Vi vil gå igennem et antal gange.
Nu har vi fået gennem denne indre for-løkke.
Vi har den mindste værdi sparer.
Vi har brug for at placere det på det begyndelsen af ​​listen.
Så hvordan skal jeg placere det i begyndelsen af ​​listen?
Hvad er den variabel, der refererer til begyndelsen af ​​listen?
Vi er i denne uden for loop, så hvad refererer til
begyndelsen af ​​listen?
>> STUDENT: værdier, jeg.
>> JASON Hirshhorn: Præcis højre.
Værdier i er begyndelsen af ​​-
eller ked af det, ikke begyndelsen.
Det var forvirrende.
Det er, hvor vi er i starten af usorteret del af listen.
Så værdier, jeg.
Og hvad betyder det lige?
>> STUDENT: Mindst.
>> JASON Hirshhorn: Værdier i lig hvad?
>> STUDENT: Mindst.
>> JASON Hirshhorn: Mindst.
Præcis højre.
Så vi placerer det i begyndelsen af listen, og nu er vi nødt til at sætte
begyndelsen af ​​den liste, hvor det mindste antal var.
Så hvordan skriver jeg, hvor mindste tal var?
Værdier for hvad?
>> STUDENT: 0.
>> JASON Hirshhorn: Den lille nummer er på 0?
>> STUDENT: Ja.
>> JASON Hirshhorn: Hvad hvis de mindste antal var ved udgangen af
denne usorteret liste?
>> STUDENT: Undskyld, hvad var spørgsmålet?
>> JASON Hirshhorn: Hvor er det mindste tal?
Vi tog den mindste og sætte det på begynder med denne linje lige her.
>> STUDENT: Det burde have været opbevaret i nogle -
>> STUDENT: Værdier j.
>> JASON Hirshhorn: Jamen, det er ikke nødvendigvis værdier j.
Det behøver ikke engang eksisterer på dette punkt.
>> STUDENT: Du er nødt til at erklære en variabel tidligere og
derefter tildele den til -
når du finder det mindste tal, tildele indekset for dette tal til
nogle variabel eller noget lignende.
>> JASON Hirshhorn: Så kan du sige det igen?
>> STUDENT: Så hvor du erklærede int mindste, bør du også erklære int
mindste indeks = i, eller noget lignende.
>> JASON Hirshhorn: Så hvor jeg int mindste, skal jeg ikke kun holde styr
af værdien, men placeringen.
int smallest_location = i dette tilfælde, vil vi bare gør jeg.
Vi har brug for at vide, hvor det er.
Vi fik til slutningen af ​​koden, og vi indså vi havde ingen idé om, hvor det var.
Og så igen, vi er kortlægning dette på én til én.
Du fyre kodning dette på din egen vilje sandsynligvis komme til det samme problem.
Hvordan dælen finder jeg det?
Og så skal du indse, vent, jeg nødt til at holde styr på det.
>> Så hvis mindste er større end værdierne j.
Vi satte mindste svarer til værdier j.
Hvad har vi brug for at ændre?
Constantin, hvad ellers gøre vi nødt til at ændre?
>> STUDENT: Den placering.
>> JASON Hirshhorn: Præcis.
Så giv mig denne linje i koden.
>> STUDENT: smallest_location = j.
>> JASON Hirshhorn: Præcis.
Og derefter ned i slutningen, hvis vi ønsker at sætte starten af ​​listen, hvor
det mindste antal var, hvor vi henviser til, hvor
mindste tal var?
Marcus?
>> STUDENT: Den mindste tal var placeret på mindste placering.
>> JASON Hirshhorn: Så på værdier smallest_location.
Og hvad skal vi sætte der?
Begyndelsen af liste, hvad er det?
>> STUDENT: Jamen, vi ikke rigtig ved, længere, fordi vi har overskrevet.
Så det er en byttet placeringer af disse to linjer?
Hvis du skifter de to linjer rundt.
>> JASON Hirshhorn: OK, så vi ikke længere, fordi vi har nulstillet den linje
før værdier I til mindste.
Så vi mistet denne oprindelige værdi.
Så du siger swap disse to linjer.
Så nu sætte starten af ​​listen hvor det mindste antal var.
Så smallest_location lig værdier, jeg.
Det bevæger sig i begyndelsen af ​​dette usorteret del af listen til
mindste placering.
Og derefter i værdier, jeg vi flytter at mindste tal.
>> Giver det mening, hvorfor vi havde at gøre at bytte?
Vi ville have overskrevet denne værdi - en anden ting du sandsynligvis ville have
regnet ud og fandt i BNP.
Så vi har taget sig af alle pseudokode.
Er der noget andet, vi nødt til at skrive her?
Kan nogen tænke på noget?
>> STUDENT: Hvordan kan du vide når du er færdig?
>> JASON Hirshhorn: Hvordan kan vi vide, hvornår vi er færdige?
Godt spørgsmål.
Så hvordan kan vi vide, når vi er færdige.
>> STUDENT: Opret en variabel til at holde tal af hvis der er en swap lavet eller ikke
og gå gennem et pass.
>> JASON Hirshhorn: OK.
Det ville fungere i boble slags.
Men for udvælgelse slags, hvis vi ikke gør lave en swap, kan det bare være
fordi den mindste værdi er i det sin rette placering.
Vi kunne have en liste 1, 2, 4, 3.
Anden gang gennem vi vil ikke gøre nogen swaps.
Vi vil være på nummer 2, men vi vil stadig nødt til at holde ud.
Så har vi brug for at holde styr på, når vi er færdig, eller skal vi bare ønsker at gå
indtil dette er færdig?
>> STUDENT: Vi kan bare gå indtil den er færdig.
>> JASON Hirshhorn: Vi kan bare gå, indtil dette er afsluttet.
I boble sortere, er du helt rigtigt, Jeff og Aleha, med din løsning -
det er dejligt at holde styr på, hvor mange swaps du har lavet, fordi der i boble
sortere, hvis du gør i virkeligheden gør ingen swaps, du er færdig, og du kan måske klippe din
problem lidt ned.
Men for udvælgelse slags, har du virkelig kom til at gå igennem til slutningen af
liste hver gang.
>> Så det er det.
Vi har to minutter tilbage.
Lad os gøre alle.
Lad mig bare åbne Find her og gøre sikker på at jeg faktisk ringer op -
Jeg ringer ikke til boble slags.
Lad os ændre dette til udvælgelse slags.
gøre alt. / finde.
Lad os finde 42.
Denne gang vi kommer til at bestå en usorteret liste, fordi det skulle sortere
første, pr find koden - skal sortere først ved hjælp af vores slags funktion og derefter
kigge efter noget.
Fingrene krydsede alle.
>> Åh min godhed.
Whoa, mit hjerte bankede.
Så det er korrekt.
Faktisk, hvis vi løb dette mere udførligt, koden, så vidt jeg kan
fortælle, er helt korrekt.
Der er nogle forslag Jeg ville have for dig.
For eksempel, 15 og 16 synes lidt overflødigt.
Det virker som om du ikke nødvendigvis nødt til at spare både dem.
Hvis du har den mindste placering, du kan nemt finde den mindste værdi af
bare at skrive værdier af I.
>> Så hvis jeg skulle klassificering din kode, som jeg vil faktisk være, jeg ville
sandsynligvis tage et punkt, hvis du omfattede både af disse, fordi du
behøver ikke begge disse.
Hvis du har den placering, kan du meget let få værdien.
Og det virker lidt underligt at gemme dem begge.
Måske ikke engang tage et punkt, men sikkert kommentere, at der er måske
ikke et stilistisk valg du behøver at gøre.
Selvfølgelig koden stadig kører udmærket.
>> Så desværre ikke gjorde vi komme til boble slags.
Jeg er ked af det.
Vi gjorde slut udvælgelse slags.
Er der nogen, der har nogen endelige spørgsmål om udvælgelse slags?
>> OK, før vi hovedet ud, jeg vil have dig at åbne din Chrome-browser.
Undskyld, det var bare en åbenlys stik for en type af internet browser.
Du kan åbne op enhver type browser, men det vil sandsynligvis være Chrome.
Og gå til denne følgende websted -
sayat.me/cs50.
Hvis du ikke skriver i din computer lige nu, er du tydeligt
ikke gør det, Tom.
>> Og du gøre det enten højre nu eller i den næste time -
give mig nogle tilbagemeldinger.
Dette er kun punkt to.
Vi har mange flere sammen, så jeg har en masse plads til at forbedre.
Jeg forhåbentlig også gjorde nogle ting godt.
Så du kan gøre mig alle dårlige, men hvis du også ønsker at give mig en smiley
ansigt, ville jeg sætte pris på, at så godt.
Fyld det i.
>> Og med et minut tilbage, der var uge tre.
Jeg vil stå uden for en smule hvis du har spørgsmål.
Jeg vil se jer i foredrag i morgen.