>> JASON Hirschhorn: Velkommen til uke tre, alle sammen.
Vi har en travel, men spennende seksjonen foran oss.
Så først, fordi vi har gjort noen framskritt med kurset, men vi har fortsatt
har mye læring igjen å gjøre, jeg er kommer til å vise noen ressurser dere
som skulle vise seg å være utrolig nyttig som du ikke bare nærmer deg
Problemet sett, men også fordøye alle materialet vi gi dere i
forelesninger og shorts og seksjon.
>> Så får vi kommer til å tilbringe de første 20 25 minutters avsnitt gå over
GDB, som du kan eller ikke kan ha anvendes på dette punkt, men det er en
utrolig nyttig verktøy som vil hjelpe deg å feilsøke programmene dine.
Mange av dere har kanskje brukt printf i midten av programmet for å finne
ut hva en variabel tangert.
GDB er enda bedre enn printf og ikke skru opp koden din fordi du
kjøre den på en kjørbar fil.
Så går vi over 10 mest nyttig kommandoer du trenger for GDB, og vi er
kommer til å gå på en øvelse sammen så i oppgavesettet tre og utover, du
kan bruke GDB å hjelpe debug programmene dine.
Og til slutt, kommer vi til å gå over noen sortering og søking algoritmer
at du så på forelesning, og vi er kommer til å faktisk kode, ikke bare
pseudo, men kode binære søk, boble sortere og valg liksom.
>> Så først, ønsker jeg å gå over ressursene.
Dette er en omfattende liste, og det er mindre skrift fordi jeg hadde mye å
passe på her.
Men disse vil ikke bare hjelpe deg, igjen, med problemet sett og
fordøye informasjonen du har lært, men definitivt, kommer quiz tid, disse vil
være utrolig nyttig.
Så først, bemerker forelesningen.
Hvis du går til cs50.net/lectures og bla til den ønskede uke og dag,
vil du se at det er notater for hver forelese, noe som ikke er rett og slett en
avskrift, men en redigert versjon av hva som ble dekket i foredrag med kode
snutter og andre nyttige ting.
Jeg anbefaler å gå over dem.
Og da også, det er kildekoden tilgjengelig fra hver forelesning.
Og igjen, vil disse lysbildene også være tilgjengelig online på cs50.net/sections
denne kvelden.
>> Så andre er de shorts hver uke som dekker temaer, vanligvis 5 til 15
minutter i lengde.
Og de som forhåpentligvis vil gi deg en stor primer på forskjellige emner.
Tredje -
og dette er helt nytt denne år - er study.cs50.net.
Hvis du ikke har sjekket det ut, jeg anbefaler at du gjør det.
Du får velge et tema.
Vi har dusinvis av emner på det.
Så for eksempel, plukker du funksjoner.
Det gir deg noen lysbilder og notater på funksjoner.
De er faktisk de lysbildene som TFs oppfordres til å bruke under
presentasjoner i seksjonen.
Det er også tips og triks for å håndtere med funksjoner, og det er
praksis problemer som hjelper du arbeider med funksjoner.
Vi gir deg også lenker til kort på funksjoner og de gangene som fungerer
har kommet opp i foredrag.
Så study.cs50.net, splitter nytt dette år, en fantastisk ressurs.
>> Deretter har jeg menneske, som er den manuelle kommando som du kan kjøre på
kommandolinjen.
Så hvis du har noen spørsmål om en kommando, for eksempel, rand, som vi
møtte forrige uke under avsnittet og du har sannsynligvis oppstått i
problemet satt når du går gjennom generere kode, men hvis du skriver mann
rand, får du den siden som forteller deg alt om rand.
Det gir deg det som trengs, det parametere det tar, samt retur
type og en kort beskrivelse av denne funksjon.
>> Så sjekk ut rand.
Det kan være litt ordrike og forvirrende, så noen ganger finner jeg at
bare Googling hva jeg ønsker å vite er den beste måten å finne svaret.
Så øve med Google.
Få gode på Google.
Det vil bli din beste venn.
>> I tillegg til Google, hvis du ikke kan finne det på Google, cs50.net/discuss, er det
diskusjonsforum.
Sjansene er hvis du har et spørsmål, en av dine 700 + jevnaldrende har også som
spørsmål og kan ha spurt det allerede i diskuterer
fora og har svart på det.
Så hvis du har et vanlig spørsmål eller du har et spørsmål som du tror
kanskje andre mennesker kan ha kjørt inn, sjekk ut cs50.net/discuss.
>> Til slutt, de to siste, hvis du ønsker å snakke med et ekte menneske, kontor
timer mandag til fredag.
Det er også online kontortid for forlengelse studenter.
Og sist, men absolutt ikke minst, meg, utropstegn.
Dere har min kontaktinformasjon.
Hvis du trenger noe, må du aldri nøl med å kontakte meg.
Alltid gjerne gjøre det.
Svært få av dere har lagt meg på Gchat, slik som har vært skuffende,
men forhåpentligvis som vil veksle mellom dette og neste avsnitt.
Eventuelle spørsmål så langt på ressursene?
Flott.
>> Til slutt, en annen plugg for tilbakemeldinger, sayat.me/cs50.
Du kan gi meg anonym tilbakemelding på hvordan jeg gjør.
Det var virkelig nyttig i forrige uke.
Jeg fikk et par kommentarer fra dere rett etter delen, pluss fra
andre studenter som så den i løpet av uken, og det
var utrolig nyttig.
Jeg kommer til å prøve og begrense min bruk av ordet "søt", men jeg vil vise min
entusiasme og spenning på annen måte.
Men det var andre tilleggs substansielle tilbakemeldinger,
både positive og Delta.
Så vær så snill, jeg gir dere tilbakemelding på oppgavesett.
Føl deg fri til å gi meg tilbakemelding på min undervisning.
Jeg er her for dere.
>> Flott.
Det er alt jeg har for den første delen.
Er det noen som har noen spørsmål så langt?
Og jeg har et notat for kontrollsenteret.
Skjøte studenter har messaged meg sier at de ikke får noen lyd,
men det er ute av min makt for å fikse.
Så forhåpentligvis blir det løst innen kort tid.
Hvis du ser på nettet, hi, men du kan ikke høre meg.
>> Så først skal vi å gå gjennom GDB.
GDB, som jeg antydet tidligere, er et feilsøkingsverktøy
mye bedre enn printf.
Så for å komme i gang med GDB, dere, hvis du ønsker å åpne opp apparatet
og ta den filen som jeg mailet til deg tidligere - denne filen vil også være
tilgjengelig på nettet i en bit -
og kjøre GDB. / navnet på filen.
Først, naturligvis, må du kompilere filen fordi GDB fungerer bare på
kjørbare filer.
>> Men hvis du noen gang ønsker å starte GDB, er det første du gjør,
du kjører GDB. / Caesar.
Så det er navnet på programmet vi er kommer til å gå med det akkurat nå.
Så jeg kommer til å skrive gjøre Caesar, som vil gi meg en kjørbar fil
her uthevet i grønt.
Og så kommer jeg til å kjøre GDB. / Cesar.
>> Og der du går.
Du skjønner vi har litt tekst som forteller meg om hvilken versjon av GDB, gi meg
noen garantiinformasjon, og da vi har BNP teksten, som ser liksom
av som vår kommandolinjen, men du ser det er åpent
paren, GDB, nære paren.
Før vi fortsetter og feilsøke denne filen som jeg sendte til dere alle, la oss se på
noen nyttige kommandoer, slik at vi har en følelse av hva vi kommer til å dekke.
>> Disse kommandoene er listet her i rekkefølgen som jeg vanligvis bruker dem.
Så jeg starter programmet ved å kjøre GBD. / Navnet på programmet,
i dette tilfellet, Caesar.
Og så er det første jeg gjør 99,9% av tiden er typen pause mener.
Som setter en pause punkt på hoved.
Hovedsak, hva du gjør det er programmet kommer til å stoppe på
Hoved slik at du kan begynne å undersøke det linjen etter linjen, i stedet for å kjøre all
veien gjennom.
Du kan bryte på forskjellige punkter i koden din, men hoved er generelt en
godt sted å begynne.
>> Den neste kommando jeg kjører er løp.
Det starter programmet kjører, og Hvis du trenger å skrive inn kommandolinjen
argumenter, kjører du det som kommando.
Kjør med argumentene.
Så siden vi kommer over en versjon av C, som er det programmet dere
skrev for PSett to -
denne, selvfølgelig, har noen insekter i det som forhåpentligvis vil vi finne -
vi kommer til å kjøre løp med en kommando argumenter fordi Caesar,
som dere vet per problemet satt spec, tar litt
kommandolinjeargumentene.
>> Det neste par av kommandoer, den neste man blir faktisk kalt neste.
At man tar du linje for linje gjennom programmet.
Så treffer n deretter Enter tar deg til den neste linje, utføring
forrige linje.
Trinn tar ikke bare deg til neste linje, men
tar du inne funksjoner.
Så hvis du har skrevet en funksjon i koden din, eller hvis du ønsker å utforske et
til i, for eksempel, kan du treffer s, og stedet for å gå til den neste linje i
filen som du går gjennom akkurat nå, vil du faktisk gå inn
denne funksjonen og se sin kode.
>> Listen viser, i svært brukervennlig format, de 10 eller så linjer rundt
hvor du befinner deg i koden så du kan faktisk se filen
snarere enn å måtte bytte tilbake og tilbake mellom ulike visninger.
Utskriften er som printf, som navnet tilsier.
Som viser deg hva en variabel er lik.
>> Info lokalbefolkningen er veldig nyttig.
Dette er en spesiell versjon av print.
Info lokalbefolkningen viser deg alle de lokale variabler, skriver dem ut for deg
som er tilgjengelig for øyeblikket.
Så jeg generelt, heller enn å måtte skrive ut de fire variabler som jeg er
nysgjerrig på om jeg er i en for loop, for eksempel, jeg bare skrive info lokalbefolkningen,
og det skal vise meg hva mitt teller jeg er lik, så vel som den matrise som er jeg
arbeider med likemenn.
>> Til slutt, fortsetter.
Skrive pause stopper deg Stillingen ved pause punktet.
Du kan gå gjennom linjen ved tråd med neste og trinn.
Fortsett kjører programmet til din neste bryte punkt eller til den er ferdig hvis
er det ingen flere brytepunkter.
Deaktiver fjerner pause poeng hvis du besluttet pause på hoved var
upassende, vil du sette den et annet sted.
Og til slutt q, avslutte, kommer ut av GDB.
>> Så dette programmet,. / Caesar, vi skal å se gjennom akkurat nå, og vi
skal bruke GDB å finne bugs i dette programmet.
Jeg kjørte dette programmet tidligere med Sjekk 50, og jeg fikk en rynke.
Alt det eksisterte, det kompilert, det passerte en rekke av testene, men for
noen grunn, gjorde det ikke passere den femte test, snu BARFOO, alle caps, inn
E-D-E-I-R-R-, bokstaver, ved hjelp av tre som en nøkkel.
Jeg fikk ganske nær.
Jeg gikk av med én bokstav.
Så det er noen små feil her.
Jeg har sett gjennom min kode.
Jeg kunne ikke finne ut av det.
Forhåpentligvis kan dere hjelpe meg finne ut hva denne feilen er.
>> Så det er feilen vi er søker etter.
La oss flytte inn GDB.
Igjen, jeg har kjørt GDB. / Caesar, så nå er vi i GDB.
Og hva er det første ting jeg bør gjøre?
Jeg har akkurat kommet inn GDB.
Noen gi meg en god kommando for å gå inn.
>> STUDENT: Bryt hoved.
>> JASON Hirschhorn: Bryt hoved.
Fantastisk.
La oss skrive at i.
Dere kan se deg her eller følg sammen på datamaskinene.
Bryt hoved, og du vil se en break point ble satt til -
det gir meg noen rare minneadresse, og det gir meg også linjenummer.
Hvis jeg var å se tilbake på denne filen, Jeg ville innse at hoved
skjedde på linje 21.
Hva bør jeg kjøre neste?
Er min program som kjører?
Nei.
Så hva bør jeg kjøre neste?
>> STUDENT: Kjør.
>> JASON Hirschhorn: Kjør.
Skal jeg bare kjøre løp, eller skal Jeg legger til noen andre ting i?
>> STUDENT: Kjør med argumentet.
>> JASON Hirschhorn: Kjør med kommandoen argumenter.
Og siden jeg feilsøker i en veldig spesifikk tilfelle, skal jeg gå inn for at
Argumentet for kommandolinjen.
Så jeg skal ikke kjøre tre, som er, igjen, output jeg fikk fra Check 50.
Starte programmet.
Vi går gjennom et par linjer.
Du vil nå se at vi er på linje 21.
Hvordan vet jeg at vi er på linje 21?
Fordi hvis du ser til venstre av min terminalvindu, der
det sier Line 21.
Og det gir meg, faktisk, den kode som er i linje 21..
Så jeg misspoke tidligere.
Hoved er faktisk ikke på linje 21.
Main er et par linjer over 21.
Men på linje 21, er at hvor vi bryte.
Dette kodelinje har ennå ikke utført.
Det er viktig.
Linjen du ser har ikke blitt utført ennå.
Det er den neste linje med kode du er i ferd med å gjennomføre.
>> Så neste linje, som dere er sannsynligvis kjent med, er dette
tilstand sjekke for å se om jeg har gikk inn i en kommandolinje argument.
Og en til jeg, hva er den andre en del av det å gjøre?
Hva er en til jeg?
>> STUDENT: Endre det til et heltall.
>> JASON Hirschhorn: Sorry?
>> STUDENT: Det er å endre argumentet til et helt tall.
>> JASON Hirschhorn: Så en til jeg endrer arg v1 fra en streng til et heltall.
Og hva er det å sjekke?
>> STUDENT: Hvis det er en andre kommandolinje argument, bortsett
fra å kjøre programmet.
>> JASON Hirschhorn: Og hva er den andre halvparten av dette
Boolsk uttrykk sjekke?
Denne delen over her, en til jeg?
>> STUDENT: Hvis det er negativt.
>> JASON Hirschhorn: Å sørge for hva?
>> STUDENT: Sørge for at det er, faktisk, positive.
>> JASON Hirschhorn: Nettopp.
Dette er å sjekke for å se om det er negativ, og hvis den er negativ, I
har en følelse av neste linje makt være meg roping på brukeren.
Så la oss treffer enden for å utføre denne linjen.
Vi kan ikke se at linjen som dere kanskje ventet å se roping på
brukeren, og deretter retur, fordi denne linjen ikke kjøre.
Jeg kom inn tre.
Så jeg gjorde, faktisk, skriv to kommando argumenter, og tre er
er større enn null.
Så vi så den linjen, henrettet vi, men vi fikk ikke gå
inne hvis betingelsen.
>> Så nå, neste, jeg ser Jeg setter int nøkkel tilsvarer en til jeg arg v1.
Så det er meg du oppretter en variabel nøkkel.
Så hvis jeg skriver ut nøkkelen akkurat nå, fordi som lar deg se
verdi inne i variabelen, Nøkkelen er lik 47.
Det er rart, men selvfølgelig, det er fordi jeg har ikke
henrettet den linjen ennå.
Så nå hvis jeg treffer n, kjøre den linjen, og gjøre print nøkkel, vil nøkkelen lik 3,
som er hva vi forventer at det skal være lik.
>> Så igjen, i GDB, linjen du ser du ikke har utført ennå.
Du må treffe n eller s eller et nummer av andre kommandoer til faktisk
kjøre den linjen.
Skriv ut nøkkelen.
Keys på tre.
Så langt, så bra.
String er ren tekst.
La oss kjøre den linjen.
Jeg får en streng fra brukeren.
>> La oss se i min Sjekk 50, jeg skriv BARFOO alle caps, så
det er det jeg skal gå inn.
Hvis jeg nå skrive ren tekst.
Du vil se det tilsvarer en streng.
Det gir meg noen rare heksadesimale tall, men det gjør i
Faktisk si at min strengen er BARFOO.
Hvis jeg ønsket å se hvilken tast tangert på dette punktet, hvordan kunne jeg sjekke nøkkelen?
>> STUDENT: Skriv ut nøkkelen.
>> JASON Hirschhorn: Skriv ut nøkkelen, akkurat.
Og faktisk, det er en snarvei.
Hvis du blir lei av å skrive print, du kan bare skrive s..
Så p-tasten gjør de samme ting.
Og igjen, jeg ser det er lik tre.
>> Hvis jeg ønsket å finne ut hva både nøkkel og BARFOO tangert samtidig
men jeg var lei av å skrive hver en ut individuelt, jeg
kunne skrive info lokalbefolkningen.
Det gir meg viktige likhets tre.
Ren tekst er lik BARFOO.
Det gir meg også disse to rare ting på toppen, variabelen og
denne variabelen n.
>> De er faktisk eksisterende i min hovedprogrammet.
Vi har ikke møtt dem ennå, men som en forhåndsvisning, de
eksistere i min for loop.
Så akkurat nå, de like noen rare tall, fordi de ikke har vært
initialisert ennå, men de har fortsatt eksisterer i minnet, slik at de bare satt
til noen søppel verdi.
Men vi ser nøkkelen i ren tekst rett der.
>> Så jeg kommer til å kjøre denne linjen, linje 34, for loop.
Vi kommer til å hoppe i for loop ved å treffe n.
Og vi er inne i for loop.
Vi er på vår første sjekk.
Og igjen, disse skal liksom se kjent for deg, fordi dette var en
Cæsar-programmet som ble skrevet, men igjen, har en slags insekt.
>> Og nå hvis jeg gjør info lokalbefolkningen, fordi jeg er innsiden som for loop, vil du se
at jeg er lik null, som vi forventer.
Det er det vi setter den til og initialisert det å i for loop.
n er lik seks.
Det gjør også fornuftig fordi vi satt det til strlen av ren tekst.
Så jeg liker å gjøre info lokalbefolkningen eller print til variable ofte å sørge for at
alt er alltid hva Jeg forventer at det skal være lik.
I dette tilfellet er alt hva jeg forventer at det skal være lik.
>> Så la oss begynne å bevege seg gjennom dette for loop.
Linjen jeg er på det linje 36, hvis det er vanlig Teksten i er større enn en og vanlig
Teksten i er mindre enn eller lik z.
Jeg vet mitt problem er ikke med min første brev, er det med den andre bokstaven.
Hvis vi ser tilbake på Check 50, B går til E fint.
Jeg tar en og forlate det som en A, ikke endre det til D. Så
noe er galt med den andre bokstaven.
Så jeg kommer til å flytte det i et sekund.
>> Men hvis jeg hadde lyst til å sjekke hva vanlig Teksten jeg tangert i denne spesielle
Da tror jeg det skal være hva?
Hva bør ren tekst jeg like i dette første runde gjennom for loop?
>> STUDENT: Zero?
>> JASON Hirschhorn: Ren tekst av jeg?
Slik det skal være stor B. I naturligvis lik null, men ren tekst
brakett null lukket vinkelen er B fordi strenger, som vi så i forrige uke,
er array, så vi får den første tegnet fra det.
Så igjen, hvis jeg printet ut ren tekst av I, I do i virkeligheten få tegnet
B. Og det er ryddig, ikke sant?
Jeg har ikke egentlig ren tekst I. Det er ikke en av de variablene jeg satt
eller initialisert, men du kan skrive ut ut en hel rekke ting
hvis du ønsker det.
>> Men la oss gå gjennom.
Hvis ren tekst jeg er større enn A og ren tekst I er mindre enn eller lik
Z, som tydelig er sant fordi vi har en kapital B. Jeg kommer til å kjøre
noen kommando på den.
Vi så at matematikk i forrige uke, så vi får ta det for gitt at det fungerer
retten ifølge Sjekk 50.
>> Disse klammeparentes, den første viste at jeg var spennende hvis
stand, viste det andre en at jeg avslutter for loop.
Og så nå da jeg traff Neste, vi får se vi er tilbake på for-løkken igjen.
Vi går gjennom for loop igjen.
La oss faktisk gå inn i andre iterasjon av for løkke og type
info lokalbefolkningen.
>> Så vi er i den andre iterasjon av vår for loop.
Jeg er lik 1, som vi forventer.
N er lik 6, som vi forventer.
Key er lik 3, som vi forventer.
Og ren tekst, vil du se, lik EARFOO nå, ikke BARFOO lenger fordi
i vår forrige iterasjon, B var endret til en kapital E. Så vi er i ferd med
å møte problemet, så dette er der vi kommer til å
dykke inn i debugging.
Men er det noen som har noen spørsmål om hva vi har gjort så langt?
Fantastisk.
>> Så vi er i ferd med å gjennomføre dette hvis tilstand, ren tekst brakett jeg lukket
brakett større enn A og ren tekst jeg mindre enn eller lik Z. Men før
Jeg går inn på det, fordi det er der Jeg vet at min feil er at jeg ønsker å påpeke
ut ren tekst av I. Så la oss sette print ut.
Det gjør det tilsvare tegnet A, slik at virker så langt, er alt vel og bra.
>> Så jeg forventer at denne linjen per min logikk, Denne linjen skal være sant.
Det er en stor bokstav.
Men hvis jeg treffer n, innser vi at dette linje, faktisk, ikke utføre.
Jeg hoppet ned til annet hvis.
Hvorfor skjedde det?
>> STUDENT: Fordi du har din tilstand av ren tekst er større
enn A, ikke er lik eller større enn.
>> JASON Hirschhorn: Så jeg hadde min ren tekst I er større enn A, som ikke er større
enn eller lik.
Så klart, gjorde ikke hovedstaden A utløse dette hvis tilstanden, og vi gjorde
ikke gå inn i det, og vi gjorde ikke gjør de nødvendige skift.
Så det er det, faktisk.
Jeg fant ut min feil.
Jeg kunne gå tilbake i min kildefilen, endre det, og oppdatere det og
kjøre Sjekk 50 igjen.
>> Men vi får se, bare for pedagogikk er skyld, hvis jeg holde det gående.
Annet hvis ikke kjøre heller, men hva stedet lik er kommandoen
som ikke endres.
Så det er ikke endret i det hele tatt, og hvis jeg skrive ren tekst her, vi får se kommer
gjennom at for loopen ikke gjorde det, faktisk, endre det andre tegn i det hele tatt.
Det er fortsatt en kapital A.
>> Så igjen, vi feilsøkt vår feil.
Vi innså at det var noen logikk mangler.
Og vi feilsøkt det på forhånd før faktisk utfører den linjen,
men du ville ha lagt merke hadde vi bare rammet Neste og gå til det annet hvis,
det betyr at at hvis tilstanden var ikke sant.
Vi gjorde ikke, faktisk, får resultatet vi forventet.
Så da kunne vi ha blitt bedt om det, hadde vi ikke vært så slu, for å se på
at hvis tilstand og sjekke om, faktisk, vår tilstand bør vurdere å
sant i den aktuelle konteksten.
>> Det er alt for debugging dette programmet.
Er det noen som har noen spørsmål?
Hvilken kommando kan jeg treffer å slutte GDB?
Q. Og så skal jeg bli bedt om, slutte likevel?
Ja eller nei.
Jeg vil treffe ja, og jeg skal ha sluttet GDB.
>> Så det var en rask primer til GDB.
Egentlig, i en reell situasjon, Jeg gjorde dette i kontortiden.
Jeg GDBed denne eksakte programmet på kontortid med en student.
Og hvis vi går tilbake til kommandoene vi så før, brukte vi pause hoved, først
ting vi gjorde.
Vi brukte kjøre med kommandolinjeargumenter, andre ting vi gjorde.
Vi brukte neste mye å flytte oss gjennom linjene.
Og igjen, den korte versjonen neste er n.
Det er i parentes i grått på lysbildet.
>> Vi brukte ikke trinn, men vi gjorde ikke nødvendigvis må for dette tilfellet.
Men vi kan bruke den i en litt senere på i dag hvis vi feilsøker, for
eksempel binære søk når binær søk kalles i et eget
funksjon, men det er noen feil med den.
Vi kommer til å ønske å gå inn kallet til binære søk og
faktisk feilsøke det.
Lister vi fikk ikke bruke enten fordi vi hadde en god følelse av vår kode, men hvis jeg
hadde lyst til å få en følelse av hva kode jeg var rundt, kunne jeg bare bruke listen.
>> Skriv ut vi brukte, info lokalbefolkningen vi brukte.
Fortsett vi ikke trenger å bruke i dette tilfelle, heller ikke vi trenger å bruke
deaktivere, men vi gjorde bruk slutte.
Igjen, disse 10 kommandoer, praktisere dem.
Hvis du forstår disse 10 kommandoer, du bør settes for debugging noen
utstede med GDB.
>> Så vi er i ferd med å gå på, igjen, til crux av seksjonen i dag, gå over
disse sortering og søking algoritmer.
Før vi gjør det, igjen, noen spørsmål, kommentarer, bekymringer for GDB?
Så er alle kommer til å bruke GDB snarere enn printf?
Så alle, for all fremtid skyld, alle nikker hodet rett
nå, så jeg vil se deg på kontortid og alle TFs vil se deg og
de vil si, vis meg hvordan du bruker GDB, og du vil kunne
å vise dem, ikke sant?
Slags?
Kanskje forhåpentligvis.
Cool.
>> Så vi kommer til å flytte inn sortering og søking.
Du vil se jeg har en liste som allerede er sortert for oss, men som ikke kommer
å være tilfelle alltid.
Så i oppgavesettet spesifikasjon for Problemet satt tre, har du shorts
som du kan se, og det faktisk ber deg om å se disse shorts.
Også i foredrag i forrige uke, gikk vi over mange av disse algoritmene, så jeg er
ikke kommer til å tilbringe tid i klassen går over disse algoritmene igjen eller tegning
bilder for hvordan disse algoritmer fungerer.
Igjen, at informasjon du kan re-watch forelesning, eller at informasjon
fanges used på shorts for disse søk, alle
som er tilgjengelig på cs50.net.
>> Så i stedet, hva vi skal gjøre er å skrive disse programmene.
Vi har en følelse, en mental modell, av hvordan de fungerer, og så hva vi skal
å gjøre er å kode dem på ordentlig.
Vi kommer til å slå den mentale modellen, det bildet, hvis du vil, inn i
selve koden.
Og hvis du var litt forvirret eller disig på mental modell, jeg helt
forstå.
>> Vi er faktisk ikke kommer til å hoppe til kode straks.
Så mens denne meldingen i denne lysbilde spør du å kode binære søk, og
faktisk, en iterativ versjon av binære søk, det første jeg
virkelig ønsker at du skal gjøre er skrive noen pseudo.
Så du har denne mentale modellen av hvordan binære søke fungerer.
Ta ut et ark hvis du har en lett tilgjengelig, eller åpne en
tekstredigeringsprogram, og jeg vil gjerne alle til å skrive.
Ta fire minutter på å skrive pseudo for binære søk.
>> Igjen, tenk på at mental modell.
Jeg kommer rundt hvis du har spørsmål og vi kan trekke bildet ut.
Men først, før vi starter programmeringen, Jeg vil gjerne skrive
pseudo for binære søk så når vi dykke i, har vi noen retning som
til hvor vi bør dra.
>> STUDENT: Kan vi anta rekken av verdiene vi får er allerede sortert?
>> JASON Hirschhorn: Så for binære søk å jobbe - utmerket spørsmål - du
nødt til å ta i en sortert matrise av verdier.
Så antar det vil fungere.
Vi vil gå tilbake til dette lysbildet.
Du vil se i lilla funksjonen Erklæringen er bool binary_search int
verdi, int verdier, int n.
Dette bør være kjent hvis du har allerede kontaktet eller fått din
hendene skitne med problemet sett.
>> Men det er din funksjon erklæring.
Igjen, ikke skulle trenge å bekymre seg for at mye i dette øyeblikk.
Det jeg egentlig vil at du skal gjøre er å ta fire minutter til pseudo binære
søke, og deretter vil vi gå over det som en gruppe.
Og jeg vil komme rundt.
Hvis du har spørsmål, føler fritt til å heve hånden.
>> Hvorfor ikke ta to minutter til slutt opp pseudo?
Jeg vet dette kan virke latterlig at vi tilbringer så mye tid på
noe som ikke engang faktisk i C, men spesielt for disse mer
utfordrende algoritmer og problem sett som vi må finne ut,
starter i pseudo ikke bekymre om syntaksen, bare å bekymre seg
logikken, er utrolig nyttig.
Og på den måten, du er ikke løse to utrolig vanskelige problemer på en gang.
Du bare fokuserer på logikk, og så du flytte inn i syntaks.
>> OK.
La oss begynne å gå gjennom den pseudo.
Jeg har skrevet opp her, binære søk pseudo.
Vi skal skrive dette på borde sammen.
Eller jeg skal skrive det, og du vil gi meg instruksjonene jeg trenger.
Så kan noen gi meg den første linjen i pseudo du
skrev for binære søk?
Ja, Annie?
>> STUDENT: Mens lengden på listen er større enn null.
>> JASON Hirschhorn: Mens lengde av listen er større enn null.
Og igjen ser vi noen C-jakt syntaktiske ting på her.
Men det meste av dette er på engelsk.
Hadde noen har noen linje de legger før dette i sin pseudo-kode?
>> STUDENT: Få en matrise av sortert tall.
>> JASON Hirschhorn: Du skrev "får en utvalg av sorterte tall. "Per
funksjon erklæringen, vil vi være bestått en rekke sortert tall.
>> STUDENT: [uhørbart].
>> JASON Hirschhorn: Så vi vil ha det.
Men ja, hvis vi ikke har det, vi ville trenge for å sortere vår rekke
tall, fordi binære søk fungerer bare på sortert arrays.
Så mens lengden på listen er lik null, er jeg kommer til å sette i noen klammeparentes
slik at den ser litt mer ut som C. Men samtidig, ser ut til å kartlegge på en
mens loop, så inne i denne stund løkke hva trenger vi å
gjøre for binære søk?
>> Noen andre som ikke har gitt meg en svar ennå, men som skrev dette?
>> STUDENT: Gå til midten av listen.
>> JASON Hirschhorn: Tom.
Gå til midten av listen.
Og oppfølgingsspørsmål, hva gjør vi når vi er på
midten av listen?
>> STUDENT: Gjør en sjekk om det er nummeret du leter etter.
>> JASON Hirschhorn: Excellent.
Gå midten av listen og sjekke hvis vår verdi er der -
fantastisk.
Har noen har noe annet som var annerledes enn dette?
Det er helt riktig.
>> Det første vi gjør i binært søk er å gå til midten av listen og
sjekk for å se om vår verdi er der.
Så jeg antar at hvis vår verdi er det, hva gjør vi?
>> STUDENT: Vi returnerer null [uhørbart].
>> JASON Hirschhorn: Ja, dersom vår Verdien er der, fant vi det.
Så vi kan fortelle noen måte, men dette funksjonen er definert, forteller vi brukeren
vi fant det.
Hvis den ikke er der, skjønt, er at der dette blir vanskelig.
Så hvis det ikke er det, noen andre som jobbet på binære søk eller
har en idé nå, hva gjør vi?
>> STUDENT: Spørsmål.
>> JASON Hirschhorn: Ja?
>> STUDENT: Er matrisen allerede sortert?
>> JASON Hirschhorn: Ja, vi antar rekken allerede er sortert.
>> STUDENT: Så da må du sjekke om verdien som du ser er større enn
verdien som du ønsker, kan du flytte til midten av den andre halvdelen.
>> JASON Hirschhorn: Så hvis midten av listen er større enn hva vi er
på jakt etter, så vi vet hva?
Vi flytter hvor?
>> STUDENT: Du ønsker å flytte til halvparten av listen med
tall lavere enn det.
>> JASON Hirschhorn: Så får vi kaller det venstre.
Så hvis midten er større, kan vi søke den venstre halvdelen av listen.
Og så etter søk, hva mener jeg med søk?
>> STUDENT: [uhørbart].
>> JASON Hirschhorn: Vi går til midten.
Vi har faktisk gjenta denne tingen.
Vi går tilbake gjennom vår mens loop.
Jeg skal gi deg det siste -
annet, hvis, i midten mindre enn hva vi, hva gjør vi her?
>> STUDENT: Gå til høyre.
>> JASON Hirschhorn: Søk i retten.
Dette ser bra ut, men er det noen som har noe som vi kan være mangler eller
noe annet som du putter i pseudo-kode?
Så dette er hva vi har så langt.
Mens lengden av listen er større enn null, skal vi gå
til midten av listen og sjekke om vår verdi er der.
>> Hvis midten er større, skal vi søke igjen, annet hvis midten er
mindre, skal vi søke den rette.
Så vi har alle hatt noen kjennskap til begrepene vi bruker i informatikk
og de verktøyene vi har.
Men vil du allerede merke vi var snakke på engelsk, men vi fant en
mange ting som syntes å kartlegge om å verktøyene vi har i vår koding verktøysett.
Så rett utenfor balltre, er vi ikke kommer til å faktisk kode ennå.
>> Hva ser vi her på engelsk at kart på til ting vi kan skrive i C?
>> STUDENT: Mens.
>> JASON Hirschhorn: Mens.
Så dette mens her kart på til hva?
>> STUDENT: En stund loop.
>> JASON Hirschhorn: En while-loop?
Eller kanskje, mer generelt, en sløyfe.
Vi ønsker å gjøre noe om og om igjen.
Så vi kommer til å kode en loop.
Og vi allerede vet, fordi vi har gjort dette et par ganger og vi
har nok av eksempler der ute, hvordan faktisk å skrive
denne indeksen for en loop.
Så det burde være ganske enkelt.
Vi bør være i stand til å få det startet ganske raskt.
>> Hva annet skal vi se på her?
Hvilke andre strukturer syntaxes, ting at vi er kjent med i C, gjør vi
allerede har en følelse av naturbasert ut av de ordene vi brukte?
Ja, Anna?
[Uhørbart]
bare tuller.
Anna, gå videre.
>> STUDENT: Hvis og annet.
>> JASON Hirschhorn: Hvis og annet - akkurat her.
Så hva gjør de ser ut?
>> STUDENT: An hvis annet utsagn.
>> JASON Hirschhorn: Yeah, forhold, ikke sant?
Så vi må sikkert skrive noen tilstander.
Og igjen, men kanskje forvirrende i første, vi har generelt en følelse nå
om hvordan å skrive forhold og syntaksen for forholdene.
Og hvis vi ikke gjør det, vi bare slå opp syntaks for forholdene, klipp og lim
det, fordi vi vet vi trenger en tilstand her.
Eventuelle andre ting vi ser at kartet på ting vi kanskje trenger å gjøre i C?
Ja, Aleha?
>> STUDENT: Dette kan være opplagt, ved å bare sjekke om en
Verdien er lik noe.
>> JASON Hirschhorn: Så hvordan skal vi sjekke og - for så å gå til midten av listen
og sjekk om vår verdi er det?
Hvordan skal vi gjøre det i C?
Hva er syntaksen for det?
>> STUDENT: lik, lik.
>> JASON Hirschhorn: lik, lik.
Så denne sjekken er trolig kommer å være et lik, lik.
Så vi vet vi trenger at et sted.
Og faktisk, bare i å skrive det, vi ser de andre tingene.
Vi er nødt til å gjøre noen sammenligningsoperatorer i det -
fantastisk.
Så det faktisk ser ut, ved og store, har vi ikke skrevet en
ord av C-kode ennå.
Men vi fikk den mentale modellen ned via forelesninger og disse shorts.
>> Vi skrev pseudo-kode som en gruppe.
Og allerede har vi 80% hvis ikke 90% av hva vi trenger å gjøre.
Nå trenger vi bare å kode den, som igjen, er en
ikke-triviell problem å løse.
Men minst er vi fast på logikk.
Minst nå når vi går til kontortiden, Jeg kan si, jeg vet hva jeg trenger
å gjøre, men kan du minne meg av syntaksen?
Eller selv om kontortiden er overfylt, du kan google for syntaksen, heller
enn å bli sittende fast på logikken.
>> Og igjen, heller enn å prøve å løse logikken og syntaks problemer alle
på en gang, er det ofte er bedre å bryte disse to vanskelige problemer ut i
to mer håndterbare seg og gjøre det pseudo-kode først og deretter koden i C.
Så la oss se hva jeg gjorde for pseudo-kode på forhånd.
>> Mens lengden av listen er større enn null, ser på midten
av listen.
Hvis nummeret funnet returnert sant, ellers hvis antallet høyere, søk venstre.
Else if nummer lavere, søk høyre, return false.
Så det ser nesten identisk hvis ikke nesten identisk med hva vi skrev.
Egentlig, Tom, hva du sa først, bryte midten av listen og hvis
nummeret funnet i to uttalelser er faktisk det jeg gjorde.
>> Jeg kombinerte dem der.
Jeg skulle ha lyttet til du første gang.
Så det er pseudo-kode har vi.
Hvis du ønsker å nå, beklager, går tilbake til vår opprinnelige problemet.
La oss kode binary.c.
Så gjennomføre en iterativ versjon av binære søk ved hjelp av følgende
funksjon erklæring.
>> Og du trenger ikke å kopiere det ned ennå.
Jeg er faktisk kommer til å åpne opp rett her binary.c.
Så det er funksjonen erklæringen i midten av skjermen.
Og du vil se jeg tok den pseudo-kode fra on mine sider, men nesten identiske
til det vi skrev, og sette det inn for deg.
Så nå, la oss ta fem minutter å kode denne funksjonen.
>> Og igjen, hvis du har noen spørsmål, rekk opp hånden, gi meg beskjed, vil jeg
komme rundt.
>> STUDENT: [uhørbart].
>> JASON Hirschhorn: Så jeg tok den binære søk definisjon på
toppen, på linje 12.
Det er hva jeg fikk for min lysbilde.
Og så all denne pseudo-kode jeg bare kopiere og limes fra raset,
pseudo-kode lysbilde.
Jeg er fortsatt ikke hørt [uhørbart].
>> Så hvis du er ferdig med din implementering, jeg ønsker å sjekke det.
Jeg mailet deg helpers.h fil tidligere i denne klassen.
Og det vil være tilgjengelig på nettet også for nedlasting for folk å se
denne delen tid forsinket.
Og jeg bare brukt den generiske distribusjon kode fra pset3.
Så jeg tok find.C, bruke min helpers.h fil snarere enn helpers.h fil
som er gitt i fordelingskode.
>> Og jeg måtte gjøre en annen endring i find.C snarere enn å ringe bare rett og slett
søk, ring binary_search.
Så hvis du ønsker å teste koden din, vet at det er hvordan du gjør det.
Faktisk, når vi skal kjøre denne koden akkurat nå, jeg bare laget en kopi av
min pset3 katalog, igjen, byttet ut hjelperne filer og deretter gjort at
endre seg i find.C å ringe binary_search snarere enn bare å søke.
>> JASON Hirschhorn: Ja.
Du har et spørsmål?
>> STUDENT: Nevermind.
>> JASON Hirschhorn: Ingen grunn til bekymring.
Vel, la oss komme i gang.
Vi vil kode dette som en gruppe.
En annen kommentar.
Igjen, dette er, kan lett byttes i for Problem Set Tre.
Jeg har min helpers.h fil som, snarere enn helpers.h vi er gitt,
erklærer binære søk, boble sortere og valg liksom.
Og i find.c vil du merke på linjen, hva er det, linje 68, kaller vi binær
søke snarere enn søk.
Så igjen, den koden som er tilgjengelig online eller koden som du er
skape akkurat nå enkelt kan byttes i for p satt tre for å sjekke det.
>> Men først, la oss kode binære søk.
Vår funksjon erklæring, vi tilbake en bool.
Vi tar et heltall kalles verdi.
Vi tar en matrise av heltall kalles verdier, og vi tar n være
størrelsen av matrisen.
På linje 10, akkurat her, har jeg skarp inkluderer stdbool.h.
Er det noen som vet hvorfor det er det?
Så hva betyr det kodelinje gjøre?
>> STUDENT: Den lar deg bruke en bool returtype.
>> JASON Hirschhorn: Nettopp.
>> STUDENT: Eller det er et bibliotek som lar å bruke en bool returtype.
>> JASON Hirschhorn: Så skarp inkluderer stdbool.h linjen gir meg noen
definisjoner og erklæringer for ting at jeg får lov til å bruke i
dette biblioteket.
Så blant dem er å si at det er denne type kalles bool, og det kan være
sant eller usant.
Så det er det den linjen gjør.
Og hvis jeg ikke har den linjen, ville jeg komme i trøbbel for å skrive dette
ord akkurat her, bool, rett der.
Helt riktig.
Så jeg trenger det i denne koden.
OK.
Så dette, igjen, er en iterativ utgave, ikke en rekursiv en.
Så la oss komme i gang.
>> La oss starte med dette første linje av pseudo-kode.
Og forhåpentligvis vil vi - eller ikke forhåpentligvis.
Vi kommer til å gå rundt i rommet.
Vi vil gå linje for linje, og jeg vil hjelpe du finne ut av linjen som vi trenger
å skrive først.
Så mens lengden på liste er større enn null.
La oss starte i front.
Hvilken linje skal jeg skrive her, i koden?
>> STUDENT: Mens parentes n er større enn 0.
>> JASON Hirschhorn: Mens n er stor enn 0.
Så n er på størrelse med en liste, og vi sjekker om -
>> [interposing VOICES]
>> JASON Hirschhorn: - beklager?
>> STUDENT: Hvordan vet vi at n er størrelsen av listen?
>> JASON Hirschhorn: Beklager.
Per PSett spesifikasjonen, søke og sortere funksjoner du trenger for å skrive,
n er størrelsen av listen.
Jeg glemte å forklare det her.
Men ja. n er størrelsen listen, i dette tilfellet.
Så mens n er større enn 0.
OK.
Det kan vise seg litt problematisk skjønt, hvis ting går på.
Fordi vi vil fortsette å vite Størrelsen på listen i denne
funksjon, men sier vi starter med et utvalg av fem heltall.
Og vi går gjennom, og vi har nå snevret det ned til
en rekke to heltall.
Hvilke to heltall er det?
Størrelsen er to nå som vi ønsker å se på, men som to er det?
Betyr det fornuftig, det spørsmålet?
>> OK.
Jeg spør det igjen.
Så vi starter med denne matrisen av 5 heltall, og n er lik 5, ikke sant?
Vi skal kjøre gjennom her.
vi vil sannsynligvis endre størrelse, høyre, så ting går videre.
Hvilket er hva vi sier vi ønsker å gjøre.
Vi ønsker ikke å søke hele greia igjen.
Så sier vi endrer det til to.
Vi tar halvparten av listen som er rart.
Så bare plukke to.
Så nå n er lik to.
Jeg beklager dårlig tørr slette markører.
Høyre?
Og vi søker gjennom listen igjen med en liste over størrelse to.
Vel, er vårt spekter fortsatt av størrelse 5.
Vi sier at vi bare ønsker å søke 2 flekker i det.
Så hvilke to stedene er de?
>> Betyr det fornuftig?
Er de de 2 venstre flekker?
Er de de rette to stedene?
Er de de midterste to stedene?
Vi har brutt ned problemet, men vi faktisk vet ikke hvilken del av
problemet vi fortsatt ser på, bare ved å ha disse to variablene.
Så vi trenger litt mer da, mens n er større enn 0.
Vi trenger å vite hvor det n er i vår faktiske array.
>> Så er det noen som har en bytte til denne linjen?
Det meste av denne linjen er helt riktig.
Er det en annen tillegg?
Kan vi bytte ut noe for n å gjøre denne linjen litt bedre?
Mm-hm?
>> STUDENT: Kan du initialisere en variabel som lengden til n som vil deretter bli brukt
senere i funksjon?
>> JASON Hirschhorn: Så initial en variabel lengde til n,
og vi bruker det senere?
Men da vi bare oppdatere lengde og vi fremdeles støte på dette problemet der vi
kutte ned lengden på vårt problem, men vi vet aldri hvor, faktisk,
at lengden kartene på.
>> STUDENT: Er ikke det kommer til å skje senere når du sier, søke igjen,
søke rett?
Du kommer til å gå til en annen område av din -
>> JASON Hirschhorn: Vi kommer til å gå til et område, men hvordan vet vi
som er å gå til?
Hvis vi bare har matrisen og dette n, hvordan vet vi hvor du skal
gå til i matrisen.
I ryggen, ja?
>> STUDENT: Har du, i likhet, lavere grense og en øvre grense eller variabel
noe sånt?
>> JASON Hirschhorn: OK.
Så dette er en annen idé.
Snarere enn bare å holde orden på størrelse, holder vi oversikt over den nedre og
øvre grense variabel.
Så hvordan skal vi beregne størrelsen fra en nedre grense og øvre grense?
>> [interposing VOICES]
>> JASON Hirschhorn: subtraksjon.
Og også å holde styr på den nedre bundet og øvre grense for å gi oss beskjed,
er vi søker disse to?
Er vi søker disse to over her?
Søker vi midt to?
Sannsynligvis ikke den midterste to, fordi dette, faktisk, er binært søk.
Men nå vil vi være i stand til å få den størrelsen, men også grensene i tabellen.
Kort sagt, hvis vi har vår giganten telefonboken, vi rive den i to.
Vi vet nå hvor det mindre telefonboken er.
Men vi er faktisk ikke ripping telefonboken i to.
Vi trenger fortsatt å vite hvor nye grensene for vårt problem er.
Er det noen som har noen spørsmål om det?
Ja?
>> STUDENT: Vil det fungere ved å skape en variabel, jeg, at du da bare skifte
stilling i forhold til dens nåværende posisjon, og lengden, n?
>> JASON Hirschhorn: Og hva er jeg?
>> STUDENT: Som jeg være som liksom -
Som du vil initial jeg å være den midtstilling av tabellen.
Og så, hvis verdien i posisjon jeg i midten av matrisen i funnet
være mindre enn verdien du trenger, jeg nå blir lengden av matrisen, samt
verdien av i dividert med to.
Som, se, du skiftet i -
>> JASON Hirschhorn: Høyre.
>> STUDENT: - opp til -
>> JASON Hirschhorn: Så jeg er nesten positivt at vil fungere.
Men poenget er, trenger du to biter av informasjon her.
Du kan gjøre det med begynnelse og slutt, eller du kan gjøre det med størrelsen, og deretter
noen markør.
Men du trenger to stykker av informasjon her.
Du kan ikke klare seg med bare én.
Betyr det fornuftig?
>> Så vi kommer til å gå gjennom, og vi kommer til å gjøre [uhørbart]
og skape noen markører.
Hva gjorde du skrive inn koden din?
>> STUDENT: Jeg bare sa int bundet en er lik 0..
>> JASON Hirschhorn: La oss kalle som int, begynner.
>> STUDENT: OK.
>> JASON Hirschhorn: Det gjør mer fornuftig for meg.
Og?
>> STUDENT: Jeg sa, jeg gjette, int slutt.
>> JASON Hirschhorn: int slutt.
>> STUDENT: Jeg antar, n minus 1, eller noe sånt.
Like, det siste elementet.
>> JASON Hirschhorn: Så du skrev, int begynner lik 0, semikolon, og int
ending lik n minus 1, semikolon.
Så egentlig, hva vi gjør her, 0 den første posisjon.
Og som vi vet i matriser, har de ikke gå opp til n, går de opp til n minus en.
Så vi har noen grenser i vårt utvalg.
Og disse innledende grenser skje for å være de første rammene av vårt problem.
OK.
Så det høres bra ut.
Så hvis vi går tilbake til denne linjen, mens lengden av listen er større enn 0,
det, i stedet for n, bør vi satt i her?
>> STUDENT: Skriv ending minus begynnelsen.
>> JASON Hirschhorn: Mens ending minus begynnelsen er større enn 0?
OK.
Og vi kunne, hvis vi ønsket å gjøre det litt hyggeligere, hva
annet kan vi gjøre?
Hvis vi ønsket å rengjøre denne koden opp litt?
Hvordan kan vi bli kvitt den 0?
Dette er bare en stil spørsmål.
Det er riktig akkurat nå.
>> STUDENT: Ending ikke lik begynnelsen?
>> JASON Hirschhorn: Vi kan gjøre hva?
>> [interposing VOICES]
>> STUDENT: Ending er større?
>> JASON Hirschhorn: Yeah.
Vi kan bare gjøre mens slutt er større enn begynnelsen.
Høyre.
Vi har lagt til begynnelsen til den andre siden av det, og vi ble kvitt 0.
Så dette ser bare en litt renere.
OK.
Så, mens lengden på listen er 0, vi skrev det, er større mens slutt
enn begynnelsen.
Vi kommer til å sette i vår nødvendig klammeparentes, og da det første
vi ønsker å gjøre er å se på dem i en liten liste.
Du?
Kan du gi meg den -
>> STUDENT: Hvis parentes verdi hakeparentes -
>> JASON Hirschhorn: Hvis parentes verdi hakeparentes.
>> STUDENT: ending delt på to.
>> JASON Hirschhorn: Ending?
>> STUDENT: Jeg ser et problem med -
>> JASON Hirschhorn: OK.
Vel, se på midten.
Hvordan vet vi hva midten er?
Yeah.
Så la meg slette den koden.
Hvordan vet vi hva midten er?
I alt, når du har begynnelsen og til slutt, hvordan finner du
midten?
>> STUDENT: Du gjennomsnittet.
>> STUDENT: Du legger dem sammen og deretter -
>> JASON Hirschhorn: Legg dem sammen og da?
>> STUDENT: Og du gjennomsnittlig.
Dele det med to.
>> JASON Hirschhorn: Legg dem sammen og dele på to.
Så int midten lik?
Tom, kan du gi den til meg?
>> STUDENT: Begynnelsen pluss ending -
>> JASON Hirschhorn: Begynnelsen pluss ending.
>> STUDENT: Alle, bracket, delt på to.
>> JASON Hirschhorn: Alle, i parentes, dividert med to.
Så det gir meg midten av noe, korrigere?
>> STUDENT: Du trenger også å runde det opp.
>> JASON Hirschhorn: Hva gjør du mener, trenger jeg å runde det opp?
>> [interposing VOICES]
>> STUDENT: Fordi hvis det er en merkelig tall, så det er som -
>> JASON Hirschhorn: Vel, OK.
Så jeg kunne runde det opp.
Men hvis det er et oddetall, en fem, kan jeg tar en bort fra midten.
Eller hvis det er et partall, heller, det er en bedre sak.
Hvis det er fire, vi har bare fire, kan jeg ta den første "midten", sitat, unquote eller
den andre "midt" en.
Enten ville arbeide for en binær søk, så jeg ikke egentlig trenger å runde det.
Men det er en annen ting jeg må se på denne linjen.
Vi kan ikke klar over det ennå, men vi vil komme tilbake til det.
Fordi denne linjen faktisk fortsatt trenger en annen ting.
>> Men så langt har vi skrevet fire linjer med kode.
Vi har fått vår begynnelsen og slutter markører.
Vi har vår mens loop, som kart på direkte til vår pseudo.
Vi ser på midten som kart direkte på vår pseudo.
Jeg vil si dette går til midten av listen, på linje med kode.
Og så, når vi går til midten av listen, neste ting vi må gjøre
er å sjekke om vår verdi er det for den pseudo vi skrev tidligere.
>> Så hvordan skal vi sjekke om vår verdi er på midten av listen?
Du.
Hvorfor ikke gjøre dette?
>> STUDENT: Hvis vår verdi er er på midten er lik
uansett hva vi setter -
Jeg mener lik lik -
>> JASON Hirschhorn: It -
OK.
>> STUDENT: Jeg er ikke sikker på hva den variabel vi leter
for selv, er fordi -
>> [interposing VOICES]
>> STUDENT: [uhørbart].
>> JASON Hirschhorn: Nettopp.
Per funksjonen erklæringen, vi leter etter en verdi.
Så vi søker etter en verdi i en matrise med verdier.
Så du er helt riktig.
Du vil gjøre, hvis åpen paren verdi brakett midten lukket vinkelen er
lik verdi, og inni der hva trenger vi å gjøre?
Hvis vår verdi er der, hva trenger vi å gjøre?
>> [interposing VOICES]
>> STUDENT: Return null.
>> JASON Hirschhorn: Return sant.
>> STUDENT: Return sant.
>> JASON Hirschhorn: Michael, hva betyr denne linjen gjøre?
>> STUDENT: [uhørbart] programmet har kjørt sin gang, og det er over, og
du har det du trenger å gjøre?
>> JASON Hirschhorn: Programmet eller hva?
I dette tilfellet?
>> STUDENT: Den funksjonen.
>> JASON Hirschhorn: Funksjonen.
Og så, for å gå tilbake til det som kalles den og gi den verdien, sant.
Helt riktig.
Main.
Hva er returtypen av hoved, Michael?
>> STUDENT: int, heltall?
>> JASON Hirschhorn: int, akkurat.
Et heltall.
Det var bare et spørsmål for å være sikker dere har vært på toppen av det.
Hva betyr det som regel tilbake, hvis alle ting fungerer bra?
>> STUDENT: Zero.
>> JASON Hirschhorn: Zero.
Helt riktig.
>> STUDENT: Hvis dette bare returnerer true, det er ingen informasjon som blir gitt
om hva -
Oh, er dette bare å si at det Verdien er inne i matrisen.
>> JASON Hirschhorn: Nettopp.
Dette programmet er ikke å gi informasjon av hvor verdien er.
Det er bare å si, ja, fant vi det, eller nei, det gjorde vi ikke det.
Så hvis nummeret funnet, returnere true.
Vel, faktisk vi bare gjorde det virkelig hurtig med at en kodelinje.
Så jeg skal flytte den linjen av pseudo.
>> STUDENT: Trenger vi ikke å forandre rekken?
Det bør være verdier, ikke verdi, ikke sant?
>> JASON Hirschhorn: Beklager.
Takk.
>> STUDENT: Ja.
>> JASON Hirschhorn: Denne linjen bør-verdier.
Helt riktig.
OK.
Så vi har sett på den midterste listen.
Hvis nummeret funnet avkastning sant.
Fortsetter videre med vår pseudo, hvis midten er større, søk igjen.
Så jeg hadde her, hvis antall høyere, søk igjen.
Constantine, kan du gi meg denne linjen med kode?
>> STUDENT: Hvis verdien av midten -
>> JASON Hirschhorn: Så hvis verdi -
hvis åpen paren verdier brakett midt tett brakett -
>> STUDENT: Er mindre enn verdien?
>> JASON Hirschhorn: Er mindre enn.
>> STUDENT: Mindre enn verdien.
>> JASON Hirschhorn: Verdi.
Vel, faktisk, vil du sjekk om nummeret -
Unnskyld.
Dette er litt forvirrende.
Men ellers hvis nummeret i midten av listen er større.
>> STUDENT: Oh, OK.
>> JASON Hirschhorn: Jeg kommer til å endre det.
Else hvis midten er høyere, vi vil søke venstre, OK?
Og hva gjør vi inne dette hvis tilstanden?
>> STUDENT: Kan jeg gjøre en liten endring til tilstanden, endre den til annet hvis?
>> JASON Hirschhorn: Else om?
OK.
Så denne koden vil kjøre omtrent det samme.
Men det fine med å bruke if, else hvis, annet hvis eller hvis, annet hvis, annet
betyr at bare en av dem skal skal kontrolleres, og ikke alle tre,
potensielt.
Og det gjør det litt finere på datamaskinen som er
kjøre programmet.
>> Så [? Constantine,?]
vi er inne i denne linjen, annet hvis verdier, brakett midt tett brakett
er større enn verdien.
Hva trenger vi å gjøre?
Vi trenger å søke venstre.
Hvordan gjør vi det?
Jeg kommer til å gi deg en start.
>> Vi har disse to tingene kalles begynner og slutter.
Så hva som må skje til begynnelsen?
Hvis du ønsker å søke venstre for liste, vi får vår nåværende begynnelsen.
Hva trenger vi å gjøre det?
>> STUDENT: Vi satt i begynnelsen til midten pluss en.
>> JASON Hirschhorn: Så hvis vi er søker venstre?
>> STUDENT: Beklager, midt minus -
så avslutningen ville være middel minus 1 og begynnelsen -
>> JASON Hirschhorn: Og hva skjer til begynnelsen?
>> STUDENT: Det forblir den samme.
>> JASON Hirschhorn: Så Betydningen forblir den samme.
Hvis vi søker venstre, er vi bruker samme begynnelsen -
helt riktig.
Og det slutter?
Sorry, hva gjør ending lik igjen?
>> STUDENT: Mellom minus en.
>> JASON Hirschhorn: Mellom minus en.
Nå, hvorfor minus en, ikke bare midten?
>> STUDENT: Den midterste er ute av bilde allerede, fordi vi hadde
sjekket at det er ute?
>> JASON Hirschhorn: Det er helt riktig.
Den midterste er ute av bildet.
Vi har allerede sjekket midten.
Så vi ikke ønsker "midten", sitat unquote, å fortsette å være i
array som vi ser.
Så dette er fantastisk.
>> Else hvis verdier brakett midten er større enn verdien slutter likhets
midten minus en.
Jeff, hva om denne siste linjen?
>> STUDENT: Else.
Verdier midten er mindre enn verdien?
>> JASON Hirschhorn: Vi vil du gir meg annet.
Så hvis du ikke gir meg -
>> STUDENT: Så da begynner ville være midt pluss en.
>> JASON Hirschhorn: Begynnelsen likemenn midtre pluss 1, igjen, for den samme
Grunnen til at Constantine ga oss tidligere.
Og på slutten, har som ikke gitt meg en linje med kode ennå?
Return false, Aleha, hva vi skriver her?
>> STUDENT: return false.
>> JASON Hirschhorn: return false.
Og vi må gjøre det, fordi hvis vi ikke synes det, trenger vi å si at vi
fant ikke det.
Og vi sa at vi kommer til å returnere en bool, så vi definitivt må tilbake
en bool sted.
>> Så la oss kjøre denne koden.
Jeg faktisk kommer til å -
så vi er i terminalen.
Vi vil fjerne vårt vindu.
La oss gjøre alt.
Vi fant det er en feil.
Det er en feil på linje 15, forventet semikolon ved enden av
erklæring.
Så hva gjorde jeg glemme?
>> STUDENT: Semicolon.
>> JASON Hirschhorn: Semicolon rett opp her.
Jeg tror det var Tom kode.
Så Tom, [uhørbart].
Bare tuller.
La oss ikke gjøre hele igjen.
>> STUDENT: Hva Dropbox katalog bør vi være i for dette?
>> JASON Hirschhorn: Så du kan bare se for denne biten.
Men igjen, hvis du ønsket å flytte denne koden på pset3 katalogen for å prøve
det ut, det var det jeg gjorde.
Hvis du vil legge merke til her - sorry, godt spørsmål.
>> [? LS,?]
Jeg har her på find.c koden fra denne ukens distro kode.
Jeg har helpers.h.
Jeg har en Make-fil som jeg faktisk redigert litt for å inkludere disse nye
filene vi skriver.
Alt dette kode vil være tilgjengelig, ikke fordelingskode, men den nye
Gjør fil, vil den nye helpers.h fil være tilgjengelig på nettet for nedlasting.
Igjen, så de som er ekstra koder har vi.
>> Så gjør alt, per denne linjen, gjør finne, binær, boble utvalg - merker
alle tre av dem og kompilerer inn denne kjørbar kode finne.
Så generelt, ønsker vi ikke til rett til check50.
Vi ønsker å kjøre noen tester på vår egen.
Men bare så vi kan fremskynde dette litt, check50 2013 pset3.find vil passere
i helpers.c-- my bad.
>> Jeg har ikke det akkurat nå.
Så vi faktisk kommer til å kjøre koden på ordentlig.
Usage.find /, vet du hva det betyr?
>> STUDENT: Du trenger en andre kommandolinje på den.
>> JASON Hirschhorn: Jeg trenger en andre kommandolinje.
Og per spesifikasjonen, jeg trenger å gå inn på hva vi leter etter.
Så la oss se for 42..
Vi vil holde det i sortert, fordi vi har ikke skrevet en slags funksjon ennå -
42, 43, 44.
>> Og Kontroll D ikke fant nålen i høystakken.
Det er ille.
Det er definitivt der.
La oss prøve noe annet.
Kanskje det er fordi jeg satt det i begynnelsen.
>> La oss gjøre 41, 42, 43.
Det vi går.
Den fant det.
La oss sette det på slutten nå, bare slik at vi kan være grundig -
40, 41, 42.
Fant du ikke nålen.
Så jeg nevnte dette tidligere.
Dessverre, jeg visste dette kom til å skje.
>> Men for pedagogiske formål, det er godt å utforske det.
Det fungerer ikke.
For noen grunn, kan det ikke finne det.
Vi vet hva som er der, men vi blir ikke å finne det.
Så en ting vi kan gjøre er å gå gjennom GDB å finne det, men gjør noen,
uten å gå gjennom GDB, har en følelse av hvor vi skrudd opp?
[? Madu? ?]
>> STUDENT: Jeg tror det kan bli når slutter er lik begynnelsen, og det er
bare ett element listen.
Da er det bare ignorerer det i stedet av faktisk sjekker det.
>> JASON Hirschhorn: Det er helt riktig.
Når ending tilsvarer begynnelsen, gjør vi fortsatt ha et element i vår liste?
>> STUDENT: Ja.
>> JASON Hirschhorn: Ja, faktisk, vi har ett og bare ett element.
Og det vil mest sannsynlig skje når, per koden vi testet, er vi på
forsiden av høystakken eller i slutten av høystakken.
Det er der begynnelse og ending kommer til å like
ett, med binære søk.
Så i disse to tilfellene det ikke fungerte, fordi slutter var lik begynnelsen.
>> Men hvis ender er lik begynnelsen betyr dette mens loop utføre?
Det gjør ikke det.
Og vi kunne ha sjekket som igjen gjennom GDB.
Så hvordan kan vi løse denne koden, fordi når mens slutt er lik
begynnelse, ønsker vi også dette mens sløyfen til å kjøre.
>> Så hva fikse kan vi gjøre til linje 18?
>> STUDENT: [uhørbart] er større enn eller lik.
>> JASON Hirschhorn: Helt riktig.
Mens ending er større enn eller lik begynnelsen.
Så nå, sørger vi for å få det hjørne tilfellet på slutten.
Og la oss se.
La oss kjøre dette en gang til.
>> La oss gjøre alt.
Igjen, må du bare følge med her.
Finn 41 denne gangen.
Bare holde det konsekvent.
>> Finn 42.
La oss sette det i begynnelsen -
42, 43, 44.
Vi fant det.
Så det var faktisk endring vi trengte å gjøre.
>> Det var en masse koding vi nettopp gjorde, binære søk.
Er det noen som har noen spørsmål før Jeg går videre inn i linjene vi skrev i
binære søk eller hvordan vi skjønte ut hva vi finne ut?
Før vi går videre, jeg ønsker også å påpeke ut at av og store, vi kartlagt
vår pseudo-kode ett til en på vår kode.
>> Vi har at vanskelige ting å regne ut med
begynner og slutter.
Men hadde du ikke funnet det ut, du ville ha skrevet ganske mye
identisk kode, lagre for de to øverste linjene.
Og så ville du ha realisert når du har gjort det i kontroller og saker som
du trenger noe annet.
Så selv om du hadde fulgt vår pseudo-kode linje til linje, ville du har
fått alle unntatt to linjer koden du trengte å skrive.
>> Og jeg ville være villig til å satse på at dere ville ha alt funnet ut
ganske raskt, at du trengte å sette en slags markør i det å regne
ut hvor du var.
Det igjen, er kraften til å gjøre pseudo-kode på forhånd.
Så vi kan gjøre logikken først, og deretter vi kan bekymre seg om syntaks.
>> Hadde vi vært forvirret om logikken mens du prøver å skrive denne koden i C,
vi ville ha fått all messed opp.
Og da ville vi stille spørsmål om logikk og syntaks og meshing
dem sammen.
Og vi ville ha fått tapt i det som raskt kan bli en
svært vanskelig problem.
Så la oss gå videre nå til valg liksom.
>> Vi har 20 minutter igjen.
Så jeg har en følelse vi vil ikke være i stand til å komme gjennom alle valg slags
og boble slag.
Men la oss i det minste forsøke å fullføre valget slag.
Så implementere utvalg slags bruker Følgende funksjon erklæring.
>> Igjen, dette er tatt fra oppgavesettet spesifikasjon.
Int verdier er parentes, er en rekke heltall.
Og int.n er størrelsen på denne matrisen.
Utvalg sorter kommer å sortere denne tabellen.
>> Så per vår mentale modell av utvalg sortere, trekker vi den -
første, vi går gjennom listen den første tid, finner det minste tallet,
sette den i begynnelsen, å finne den nest minste tallet, sette den i
andre posisjon hvis vi ønsker å sortere i stigende rekkefølge.
Jeg er ikke tvinge deg til å skrive pseudo-kode akkurat nå.
>> Men før vi gjør koden som en klasse i fem minutter, har vi tenkt å skrive
pseudo-kode, slik at vi har noen følelse av hvor vi skal.
Så prøv å skrive pseudo-kode på egen hånd.
Og deretter forsøke å snu det pseudo-koden inn kode.
Vi vil gjøre det som en gruppe i fem minutter.
>> Og selvfølgelig, la meg vite om du har noen spørsmål.
>> STUDENT: At det?
>> JASON Hirschhorn: Se hvor langt du kan komme i to minutter til.
Jeg forstår at du ikke vil være i stand til å fullføre.
Men vi vil gå over dette som en gruppe.
>> Du er all koding så [uhørbart], så jeg er beklager å stoppe hva du gjør.
Men la oss gå gjennom dette som en gruppe.
Og igjen, binære søk, du alle gi meg en hvis ikke flere linjer med kode.
Takk for det.
Vi kommer til å gjøre det samme Herfra koden sammen som en gruppe.
>> Så utvalg sort - la oss skrive noen raske pseudo-kode.
Per mental modell, kan noen gi meg den første linjen av pseudo-kode, er du snill?
Hva ønsker jeg å gjøre?
>> STUDENT: Mens listen er ute av drift.
>> JASON Hirschhorn: OK, mens listen er ute av drift.
Og hva mener du med "ute av drift?"
>> STUDENT: Mens [uhørbart]
har ikke blitt sortert.
>> JASON Hirschhorn: Mens listen er ute av drift, hva gjør vi?
Gi meg den andre linjen, vær så snill, Marcus.
>> STUDENT: Så finner den neste minste tallet.
Dette vil bli innrykket.
>> JASON Hirschhorn: Så finner den neste minste tallet.
Og så noen andre?
Når vi finner den nest minste nummer, hva gjør vi?
Jeg kommer til å si finne det minste tallet.
Det er det vi ønsker å gjøre.
>> Så finn det minste tallet.
Så hva gjør vi?
>> STUDENT: [uhørbart] til begynnelsen.
>> JASON Hirschhorn: Sorry?
>> STUDENT: Plasser den i begynnelsen av listen.
>> JASON Hirschhorn: Så legg den i begynnelsen av listen.
Og hva gjør vi for å tingen som var i begynnelsen
av listen, ikke sant?
Vi overskriver noe.
Så hvor skal vi sette det?
Ja, Anna?
>> STUDENT: Hvor den minste antallet var?
>> JASON Hirshhorn: Så legg begynnelsen av listen hvor
minste tallet var.
Så mens listen er ute av drift, finne det minste tallet, plasser den i
begynnelsen av listen, sett begynnelsen av listen der
minste tallet var.
Marcus, kan du omformulere denne linjen mens listen er ute av drift?
>> STUDENT: Mens tallene har ikke blitt sortert?
>> JASON Hirshhorn: OK, så for å at tallene ikke vært
sorteres, hva trenger vi å gjøre?
Hvor mye trenger vi å gå gjennom denne listen?
>> STUDENT: Så jeg antar en for loop, eller samtidig, er mindre, mens tallene kontrolleres
enn lengden av listen?
>> JASON Hirshhorn: OK, det er bra.
Jeg tror jeg misphrased spørsmålet mitt dårlig.
Jeg prøvde bare å få på vi er nødt til å gå
gjennom hele listen.
Så mens listen er ute av drift, for meg, er vanskelig å kartlegge på.
Men i utgangspunktet, det er hvordan Jeg tenker på dette.
Gå gjennom hele listen, finner minste tallet, plasser den i
begynner - faktisk, du har rett.
La oss sette dem begge.
>> Så mens listen er ute av drift, vi behov for å gå gjennom hele listen
gang, finne det minste tallet, sted det i begynnelsen av listen, sette
begynnelsen av listen hvor minste tallet var, og hvis det
listen er fortsatt ute av drift, vi har må gå gjennom dette
prosessen på nytt, ikke sant?
Det er derfor valg sortere, Big-O runtime av utvalget sortere, anyone?
>> STUDENT: n squared.
>> JASON Hirshhorn: n squared.
Fordi som Marcus og jeg innså her er vi nødt til å
går gjennom listen listen antall ganger.
Så går gjennom noe av lengde n n antall ganger
er faktisk n squared.
>> Så dette er vår pseudo.
Dette ser veldig bra ut.
Er det noen som har noen spørsmål om pseudo?
Fordi faktisk utvalg sorter bør trolig komme 1-1, kode fra
pseudo.
Så noen spørsmål om logikken i pseudo?
Spør den nå.
>> Utvalg sort - mens listen er ute av orden, kommer vi til å gå gjennom det
og finne den minste hver gang og legg den i fronten.
Så mens listen er ute av drift, kan noen gi meg at kodelinje som
har ikke gitt meg en linje av kode ennå, please?
Det høres ut som en hva?
>> STUDENT: Det er en for-løkke.
>> JASON Hirshhorn: Det høres liker en for-løkke.
OK, kan du gi meg for loop?
For -
>> STUDENT: i lik 0.
>> JASON Hirshhorn: i eller -
Hva er det vi mangler?
Hva går rett her?
>> STUDENT: Int.
>> JASON Hirshhorn: Nettopp.
(Int i = 0, -
>> STUDENT: i <n, i + +).
>> JASON Hirshhorn: Nailed det, Jeff.
Vi går gjennom listen, ikke sant?
Vi har sett at koden før.
Perfekt.
Så la oss sette våre klammeparentes her.
Jeg kommer til å sette noen klammeparentes her.
>> Så selv om det er 0, må vi gå gjennom hele listen.
Så hver gang vi går gjennom listen, hva gjør vi ønsker å holde styr på?
>> STUDENT: Hvis noen bytteavtaler er gjort.
>> JASON Hirshhorn: Finn det minste tallet.
Så vi bør nok holde styr på det minste tallet hver gang.
Så linjen kan jeg gjøre for å holde oversikt av det minste tallet?
Aleha, hvordan kan jeg holde sporet av noe?
>> STUDENT: Start en ny variabel.
>> JASON Hirshhorn: Start en ny variabel.
Så la oss lage en variabel.
Hvilken type?
>> STUDENT: Int.
>> JASON Hirshhorn: Int.
La oss kalle det den minste.
Og hva gjør det like når vi akkurat har startet opp?
Vi har ikke gått gjennom listen ennå.
Vi er på den første delen av listen vår første gang gjennom.
Hva gjør det likt, jo minste tallet?
>> STUDENT: verdiene jeg.
>> JASON Hirshhorn: verdiene jeg.
Det høres helt riktig, ikke sant?
Det minste tallet i begynnelsen er der vi er.
Så nå har vi vår minste, og vi trenger for å gå gjennom hele listen og
sammenligne dette minste til alt annet.
Så skal vi gå gjennom listen igjen?
Michael?
>> STUDENT: Du må gjøre en annen for loop.
>> JASON Hirshhorn: Another for loop.
La oss gjøre det.
Gi meg noen kode.
>> STUDENT: For sløyfe -
for de minste -
bare int j, kan du si?
= 0, er slik at -
>> JASON Hirshhorn: Vel, hvis vi ønsker å gå gjennom hele listen -
>> STUDENT: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
Vi kommer til å gå gjennom for loop igjen.
Og hvordan skal vi finne den minste tallet?
Tom?
Vi har den nåværende minste tallet, så hvordan finner vi den nye minste?
>> STUDENT: Vi kan sjekke om de minste nummer vi har er større enn
. verdier brakett j
>> JASON Hirshhorn: Så hvis minste er større enn verdiene brakett j.
Så hvis vår nåværende minste er større enn -
Jeg kommer til å flytte disse to linjene med kode der ute for et sekund.
Fordi før vi gjør noe bytte, vi behov for å gå gjennom hele listen.
Så dette pseudo burde faktisk være utenfor det indre for loop.
Så gå gjennom hele listen.
Hvis minste er større enn verdier j hva så?
>> STUDENT: Da minste tilsvarer verdier j.
>> JASON Hirshhorn: Fantastic.
En rask spørsmål -
første gang vi går gjennom denne sløyfen, Jeg kommer til å være lik 0, er j kommer
til lik 0 når vi får inn her.
Så vi kommer til å være å sammenligne et tall til seg selv.
Er det effektivt?
Nei, det er ikke veldig effektivt.
Så gjør vår j må gå fra 0 til n hver gang?
Trenger vi alltid å sjekke gjennom hele listen?
[Uhørbart]?
>> STUDENT: Start med i stedet.
>> JASON Hirshhorn: j kan begynne med hva?
>> STUDENT: jeg.
>> JASON Hirshhorn: j kan starte med jeg.
Så nå sammenligner vi starter med den vi er på.
Men selv da er at ettersom effektiv som mulig?
>> STUDENT: i + en.
>> JASON Hirshhorn: i + 1 synes å være den mest effektive, fordi vi
allerede har jeg.
Vi sier at etter hvert som minste på linje 15.
Vi kommer til å starte med neste automatisk.
Så vi går gjennom for loop.
Vi vil gå gjennom hver gang.
Vi vil gå gjennom en rekke ganger.
Nå har vi fått gjennom denne indre for loop.
Vi har den minste verdien redninger.
Vi trenger å plassere den på begynnelsen av listen.
Så hvordan legger jeg det på begynnelsen av listen?
Hva er den variabelen som refererer til begynnelsen av listen?
Vi er i dette utenfor for loop, så hva refererer til
begynnelsen av listen?
>> STUDENT: verdiene jeg.
>> JASON Hirshhorn: Helt riktig.
Verdier jeg er i begynnelsen av -
eller beklager, ikke i begynnelsen.
Det var forvirrende.
Det er der vi er i begynnelsen av usortert del av listen.
Så verdiene jeg.
Og hva gjør det lik?
>> STUDENT: Minst.
>> JASON Hirshhorn: Verdier jeg tilsvarer hva?
>> STUDENT: Minst.
>> JASON Hirshhorn: Minst.
Helt riktig.
Så vi plassere det i begynnelsen av listen, og nå trenger vi å sette
begynnelsen av listen der det minste tallet var.
Så hvordan kan jeg skrive hvor minste tallet var?
Verdier av hva?
>> STUDENT: 0.
>> JASON Hirshhorn: Den lille nummeret står på 0?
>> STUDENT: Ja.
>> JASON Hirshhorn: Hva om de minste antallet var ved slutten av
dette usortert liste?
>> STUDENT: Unnskyld, hva var spørsmålet?
>> JASON Hirshhorn: Hvor er det minste tallet?
Vi tok den minste og sette den på begynner med denne linjen her.
>> STUDENT: Den må ha blitt lagret i noen -
>> STUDENT: Verdier j.
>> JASON Hirshhorn: Vel, det er ikke nødvendigvis verdier j.
Det trenger ikke engang eksisterer på dette punktet.
>> STUDENT: Du må erklære en variabel tidligere og
deretter tildele det til -
når du finner det minste tallet, tildele indeks over det tallet til
noen variabel eller noe sånt.
>> JASON Hirshhorn: Så kan du si det igjen?
>> STUDENT: Så hvor du erklært int minste, bør du også erklære int
minste indeks = i, eller noe sånt.
>> JASON Hirshhorn: Så hvor jeg int minste, bør jeg ikke bare holde styr
av verdien, men plasseringen.
int smallest_location = i dette tilfelle, vil vi bare gjøre jeg.
Vi trenger å vite hvor det er.
Vi kom til slutten av koden, og vi skjønte vi hadde ingen anelse om hvor det var.
Og så igjen, er vi kartlegging denne på 1-1.
Dere koding dette på din egen vilje sannsynligvis komme til samme problem.
Hvordan i all verden finner jeg det?
Og så du skjønner, vent, jeg trenger å holde styr på det.
>> Så hvis minste er større enn verdiene j.
Vi satt minste tilsvarer verdier j.
Hva annet trenger vi å endre?
Constantin, hva annet gjøre vi trenger å forandre?
>> STUDENT: Plasseringen.
>> JASON Hirshhorn: Nettopp.
Så gi meg den linjen i koden.
>> STUDENT: smallest_location = j.
>> JASON Hirshhorn: Nettopp.
Og så ned på slutten, hvis vi ønsker å sette begynnelsen av listen, hvor
det minste tallet var, hvordan vi referere til hvor
minste tallet var?
Marcus?
>> STUDENT: Den minste tallet var ligger på minste sted.
>> JASON Hirshhorn: Så på verdier smallest_location.
Og hva gjør vi satt der?
Begynnelsen av liste, hva er det?
>> STUDENT: Vel, trenger vi egentlig ikke vet lenger fordi vi har overskrevet.
Så det er en byttet steder av disse to linjene?
Hvis du bytter de to linjene rundt.
>> JASON Hirshhorn: OK, så vi gjør ikke lenger, fordi vi har tilbake linjen
førverdier jeg til minste.
Så vi mistet den opprinnelige verdien.
Så du sa swap disse to linjene.
Så nå satt i begynnelsen av listen der det minste tallet var.
Så smallest_location tilsvarer verdier jeg.
Som beveger seg i begynnelsen av denne usortert del av listen til
minste sted.
Og deretter inn verdiene jeg vi flytter det minste tallet.
>> Betyr det fornuftig hvorfor vi måtte gjøre at swap?
Vi ville ha overskrevet denne verdien - en annen ting du sannsynligvis ville ha
funnet ut og funnet i BNP.
Så vi har tatt vare på all pseudo.
Er det noe annet vi trenger å skrive her?
Kan noen tenke på noe?
>> STUDENT: Hvordan vet du når du er ferdig?
>> JASON Hirshhorn: Hvordan kan vi vite når vi er ferdige?
Store spørsmål.
Så hvordan vet vi når vi er ferdige.
>> STUDENT: Lag en variabel for å holde tellingen av om det er en swap gjort eller ikke
og gå gjennom et pass.
>> JASON Hirshhorn: OK.
Det ville jobbe i boble slag.
Men for valg sorter, hvis vi ikke gjør det lage en swap, kan det bare være
fordi den minste verdien er i det sin rett sted.
Vi kan ha en liste 1, 2, 4, 3.
Den andre gangen gjennom vi vil ikke gjøre noen bytteavtaler.
Vi vil være på nummer to, men vi vil fortsatt trenger å holde det gående.
Så trenger vi å holde styr på når vi er ferdige, eller ønsker vi bare å gå
før dette er ferdig?
>> STUDENT: Vi kan bare gå før det er ferdig.
>> JASON Hirshhorn: Vi kan bare gå før dette er ferdig.
I boble sortere, er du helt riktig, Jeff og Aleha, med løsningen -
det er flott å holde oversikt over hvor mange swaps du har gjort, fordi i boble
sortere, hvis du faktisk gjør ingen bytteavtaler, du er ferdig, og du kan kanskje klippe
Problemet ned litt.
Men for valg liksom, har du virkelig må gå gjennom til slutten av
listen hver gang rundt.
>> Så dette er det.
Vi har to minutter igjen.
La oss gjøre alt.
La meg bare åpen Finn her og gjøre sikker på at jeg faktisk ringer opp -
Jeg kaller boble slag.
La oss endre dette til valget slag.
gjøre alt. / finne.
La oss finne 42.
Denne gangen vi kommer til å passere en usortert liste, fordi det skal sortere
første, per funnkode - burde sortere først bruker vår sorteringsfunksjonen og deretter
se etter noe.
Fingrene krysset alle.
>> Oh my goodness.
Whoa, hjertet mitt slo.
Så det er riktig.
Faktisk, hvis vi kjørte denne mer omfattende, koden, så vidt jeg kan
fortelle, er helt riktig.
Det er noen forslag Jeg ville ha for deg.
For eksempel 15 og 16 virke litt overflødig.
Det virker som du ikke nødvendigvis må spare både de.
Hvis du har den minste sted, du kan lett finne den minste verdien av
bare å skrive verdier av i.
>> Så hvis jeg skulle bli gradering koden din, som jeg faktisk vil være, ville jeg
sannsynligvis ta av et poeng hvis du inkludert begge disse, fordi du
trenger ikke begge disse.
Hvis du har plasseringen, kan du veldig lett få verdien.
Og det virker litt rart å oppbevare dem begge.
Kanskje ikke engang ta et poeng, men sikkert kommentere at det er kanskje
ikke et stilistisk valg du trenger å gjøre.
Selvfølgelig koden fortsatt går helt bra.
>> Så vi har dessverre ikke komme til boble slag.
Jeg er lei for det.
Vi gjorde ferdig utvalg slag.
Er det noen som har noen endelige spørsmål om valg liksom?
>> OK, før vi setter kursen ut, jeg vil ha deg å åpne opp din Chrome nettleser.
Sorry, det var bare en blatant plugg for en type nettleser.
Du kan åpne opp hvilken som helst type nettleser, men det vil trolig være Chrome.
Og gå til denne følgende nettsted -
sayat.me/cs50.
Hvis du ikke skriver på datamaskinen akkurat nå, er du helt klart
ikke gjør det, Tom.
>> Og kan du gjøre det enten rett nå eller i den neste timen -
gi meg noen tilbakemeldinger.
Dette er bare delen to.
Vi har mange flere sammen, så jeg har mye rom for å forbedre.
Jeg forhåpentligvis også gjorde noen ting godt.
Så du kan få meg til å føle så verst, men hvis du også ønsker å gi meg en smiley
ansikt, ville jeg sette pris på det også.
Fylle det i.
>> Og med en liten venstre, som var uke tre.
Jeg skal stå utenfor for litt hvis du har spørsmål.
Jeg vil se dere i forelese i morgen.