>> JASON Hirschhorn: Välkommen till vecka tre, alla.
Vi har en hektisk men spännande avsnitt framför oss.
Så först, därför att vi har gjort vissa framsteg med kursen men vi fortfarande
har en hel del att lära kvar att göra, jag är ska visa er några resurser
som skulle visa sig vara oerhört hjälp eftersom du inte bara vända din
Problemet ställer, men också smälta alla det material vi ger er i
föreläsningar och kortfilmer och avsnitt.
>> Sen ska vi spendera de första 20 till 25 minuters avsnitt gå över
GDB, som du kan eller inte kan ha används vid denna punkt, men det är en
otroligt användbart verktyg som kommer att hjälpa dig att felsöka dina program.
Många av er kanske har använt printf i mitt i ditt program att räkna
vad en variabel uppgick.
GDB är ännu bättre än printf och inte skruva upp din kod eftersom du
köra det på en körbar fil.
Så går vi över 10 mest användbara kommandon du behöver för GDB, och vi är
kommer att gå på en övning tillsammans så i problem set tre och framåt, du
kan använda GDB för att felsöka dina program.
Och slutligen kommer vi att gå igenom några sortering och sökning algoritmer
som du såg på föreläsning, och vi är kommer att faktiskt kod, inte bara
pseudokod, men kod binär sökning, bubbla sortera och val av sort.
>> Så först, jag vill gå över resurserna.
Detta är en omfattande lista, och det är mindre typsnitt eftersom jag hade mycket att
passar på här.
Men dessa kommer inte bara hjälpa dig, igen, med problemsamlingar och
smälta information du lärt dig, men definitivt, kom frågesport tid, dessa kommer
vara otroligt hjälpsamma.
Så först, konstaterar föreläsningen.
Om du går till cs50.net/lectures och bläddra till vecka och dag,
ser du att det finns noteringar för varje lecture, vilket inte är helt enkelt en
transkript, men en redigerad version av vad som angavs i föreläsning med kod
strängar och andra hjälp tidbits.
Jag rekommenderar starkt att gå över dem.
Och sedan också, det finns källkod tillgängliga från varje föreläsning.
Och återigen, kommer dessa bilder också vara tillgängligt på cs50.net/sections
i kväll.
>> Så andra är shortsen varje vecka som täcker ämnen, vanligtvis 5 till 15
minuter i längd.
Och de som förhoppningsvis kommer att ge dig en bra primer på olika ämnen.
Tredje -
och detta är helt ny här år - är study.cs50.net.
Om du inte har kollat ​​upp det, jag rekommenderar starkt att du gör det.
Du får välja ett ämne.
Vi har massor av frågor om det.
Så till exempel, väljer du Funktioner.
Det ger dig några diabilder och noterar på funktioner.
De är faktiskt de bilder som TF uppmuntras att använda under vår
presentationer i avsnitt.
Det finns också tips och tricks för att hantera med funktioner, och det finns
övnings problem som hjälper du arbetar med funktioner.
Vi ger dig också länkar till korta på funktioner och de tider som fungerar
har kommit upp i föreläsningen.
Så study.cs50.net, helt ny här år, en fantastisk resurs.
>> Nästa, jag har människan, som är den manuella kommando som du kan köra på
kommandorad.
Så om du har några frågor om en kommando, till exempel, rand, som vi
mötte förra veckan under avsnitt och du har förmodligen stött på i
ditt problem inställd när man går igenom generera kod, men om du skriver man
rand, får du den sida som berättar allt om rand.
Det ger dig vad som krävs, det parametrar som krävs, samt avkastning
typ och en kort beskrivning av denna funktion.
>> Så kolla rand.
Det kan vara en liten ordrik och förvirrande, så ibland tycker jag att
helt enkelt googla det jag vill veta är det bästa sättet att hitta svaret.
Så öva med Google.
Få bra på Google.
Det kommer att bli din bästa vän.
>> Förutom Google, om du inte kan hitta det på Google, cs50.net/discuss, det är
diskussionsforumet.
Chanserna är om du har en fråga, en av dina 700 + kamrater också har att
fråga och kan ha bett det redan i diskutera
forum och få den besvarad.
Så om du har en vanlig fråga eller du har en fråga som du tror
kanske andra människor kanske har stött på, kolla cs50.net/discuss.
>> Slutligen, de två sista, om du vill prata med en riktig människa, kontor
timmar måndag till fredag.
Det finns även online-kontorstid för förlängnings studenter.
Och sist men absolut inte minst, mig, utropstecken.
Ni har alla mina kontaktuppgifter.
Om du behöver något, vänligen aldrig tveka inte att kontakta mig.
Du är alltid välkommen att göra det.
Mycket få av er har lagt till mig på Gchat, så det har varit en besvikelse,
men förhoppningsvis som kommer att förändras mellan detta och nästa avsnitt.
Har du frågor så långt på resurser?
Bra.
>> Slutligen, en annan kontakt för feedback, sayat.me/cs50.
Du kan ge mig anonym respons om hur jag gör.
Det var riktigt bra förra veckan.
Jag fick ett par kommentarer från er direkt efter avsnitt, plus från
andra elever som såg det under veckan, och det
var otroligt bra.
Jag kommer att försöka begränsa min användning av ordet "söt", men jag ska visa min
entusiasm och spänning på andra sätt.
Men det fanns andra tilläggs materiella återkopplingar,
både plus och delta.
Så snälla, jag ger er respons på dina problemsamlingar.
Känn dig fri att ge mig feedback på min undervisning.
Jag är här för er.
>> Bra.
Det är allt jag har för det första avsnittet.
Är det någon som har någon frågor hittills?
Och jag har en notering om kontrollcentralen.
Förlängnings studenter har messaged mig säger att de inte får något ljud,
men det är utanför min makt för att fixa.
Så förhoppningsvis blir det lösas inom kort.
Om du tittar på nätet, hej, men du kan inte höra mig.
>> Så först, ska vi att gå igenom GDB.
GDB, som jag antydde tidigare, är ett felsökningsverktyg
mycket bättre än printf.
Så för att komma igång med GDB, killar, om du vill öppna upp din apparat
och ta den fil som jag mailade till dig tidigare - den här filen kommer också att
tillgänglig online på lite -
och kör GDB. / namnet på filen.
Först, naturligtvis, måste du kompilera fil eftersom GDB fungerar bara på
körbara filer.
>> Men om du någonsin vill starta GDB, det första du gör,
du kör GDB. / Caesar.
Så det är namnet på det program som vi är kommer att gå med det just nu.
Så jag kommer att skriva att Caesar, som kommer att ge mig en körbar fil
här markeras med grönt.
Och sedan ska jag köra GDB. / Cesar.
>> Och där du går.
Du ser att vi har en text talar om för mig om den version av GDB, ger mig
viss garantiinformation, och då vi har BNP-prompten, som ser sorterar
av som vår kommandoraden, men du ser att det är öppet
Paren, GDB, nära Paren.
Innan vi fortsätter och felsöka den här filen som jag skickade till er alla, låt oss titta på
några användbara kommandon så vi har en känsla av vad vi kommer att täcka.
>> Dessa kommandon visas här i ordning som jag vanligtvis använder dem.
Så jag startar mitt program genom att köra GBD. / Namnet på programmet,
i det här fallet, Caesar.
Och sedan det första jag gör 99,9% av tiden är typ rast menar.
Det sätter en brytpunkt vid huvud.
I huvudsak, vad du gör det är programmet kommer att stanna vid
huvud så att du kan börja granska den linje för rad, snarare än att köra alla
vägen igenom.
Du kan bryta vid olika din kod, men viktigaste är i allmänhet en
bra ställe att börja.
>> Nästa kommando jag kör är körning.
Det startar programmet körs, och Om du måste ange kommandoraden
argument, kör du det kommandot.
Kör med argumenten.
Så eftersom vi går över en version av C, som är det program ni
skrev för pset två -
den här, naturligtvis, har en del buggar i det att vi förhoppningsvis hittar -
vi ska köra köra med några kommandot line argument eftersom Caesar,
som ni vet per problemet ställa spec, tar lite
kommandoradsargument.
>> Nästa par kommandon, nästa man faktiskt kallas nästa.
Att man tar dig rad för rad genom ditt program.
Så slår n sedan Enter tar dig till nästa rad, verkställande
föregående rad.
Steg inte bara tar dig till nästa rad, men det
tar dig inuti funktioner.
Så om du har skrivit en funktion i din kod, eller om du vill utforska en
att jag, till exempel, kan du träffa er, och snarare än att gå till nästa rad av
filen som du går igenom höger nu, kommer du faktiskt kliva in
denna funktion och se dess kod.
>> List visar, i mycket användarvänlig format, de 10-tal linjer runt
var du är i din kod så du kan faktiskt se filen
i stället för att byta tillbaka och tillbaka mellan olika vyer.
Print är som printf, som namnet antyder.
Det visar vad en variabel är lika.
>> Info lokalbefolkningen är riktigt bra.
Detta är en specialversion av tryck.
Info lokalbefolkningen visar dig alla de lokala variabler, skriver ut dem alla ut för dig
som finns tillgängliga.
Så jag i allmänhet, snarare än att behöva skriva ut de fyra variablerna som jag är
nyfiken på om jag är i en for-slinga för exempel, jag bara skriva info lokalbefolkningen,
och det kommer att visa mig vad min disk i är lika, samt den array som jag är
arbetar med jämlikar.
>> Slutligen, fortsätt.
Skriva paus stoppar dig vid brytpunkten.
Du kan gå igenom rad för linje med nästa och steg.
Fortsätt kör programmet till din nästa bryta punkt eller till det att hela om
det finns inga fler brytpunkter.
Inaktivera tar bort brytpunkter om du beslutade paus vid huvud var
olämpligt, du vill ställa in den någon annanstans.
Och slutligen q, sluta, spårar ur GDB.
>> Så detta program. / Caesar, vi kommer att titta igenom just nu och vi
ska använda GDB för att hitta buggar i det här programmet.
Jag körde det här programmet tidigare med Kontrollera 50, och jag fick en rynka pannan.
Allt det existerade, det sammanställas, det passerade en hel del av testerna, men för
någon anledning har den inte passera den femte testet, svarvning BARFOO, versaler, till
E-D-U-I-R-R, versaler, med användning av tre som en nyckel.
Jag kom ganska nära.
Jag fick med en bokstav.
Så det finns några små misstag i här.
Jag har tittat igenom min kod.
Jag kunde inte lista ut det.
Förhoppningsvis kan ni hjälpa mig lista ut vad felet är.
>> Så det är fel att vi är efter.
Låt oss gå in i GDB.
Återigen, jag kör GDB. / Caesar, så nu är vi i GDB.
Och vad är det första sak jag ska göra?
Jag har just gått in i GDB.
Någon ge mig en bra kommando för att komma in.
>> STUDENTEN break.
>> JASON Hirschhorn: break.
Fantastiskt.
Låt oss skriva det i.
Ni kan titta på upp här eller följ tillsammans på dina datorer.
Break, och du kommer att se en brytpunkt fastställdes till -
det ger mig några konstiga minnesadress, och det ger mig också radnumret.
Om jag skulle se tillbaka på den här filen, Jag skulle inse att huvud
hände på linje 21.
Vad ska jag köra nästa?
Är mitt program körs?
Nej.
Så vad ska jag köra nästa?
>> STUDENT: Kör.
>> JASON Hirschhorn: Kör.
Ska jag köra bara springa, eller bör Jag lägger en del andra saker i?
>> STUDENT: Kör med argumentet.
>> JASON Hirschhorn: Kör med kommandoargument.
Och eftersom jag felsökning av en mycket specifik fall, ska jag ange att
kommandoradsargumentet.
Så jag kör tre, som är, återigen, utmatningen jag fick från Check 50.
Starta programmet.
Vi går igenom ett par rader.
Du kommer nu se att vi är på rad 21.
Hur vet jag att vi är på rad 21?
Därför att om man tittar till vänster mitt terminalfönster, där
det står linje 21.
Och det ger mig, faktiskt, det kod som är vid linjen 21.
Så jag misspoke tidigare.
Huvud är faktiskt inte på linje 21.
Huvud är ett par rader över 21.
Men på rad 21, det är där vi bryter.
Denna kodrad har ännu inte verkställts.
Det är viktigt.
Linjen som du ser har inte utförts ännu.
Det är nästa kodrad du är på väg att köra.
>> Så nästa rad, eftersom ni är förmodligen bekant med, är detta
villkor kontroll för att se om jag har trädde en kommandorad argument.
Och en till i, vad är den andra en del av det som gör?
Vad är att jag?
>> STUDENT: Ändra det till ett heltal.
>> JASON Hirschhorn: Förlåt?
>> STUDENT: Det ändrar Argumentet till ett heltal.
>> JASON Hirschhorn: Så en till jag ändrar arg v1 från en sträng till ett heltal.
Och vad är det kontroll?
>> STUDENT: Om det finns en andra kommandorad argument åt sidan
från att köra programmet.
>> JASON Hirschhorn: Och vad är den andra halvan av det här
Booleskt uttryck kontroll?
Denna del hit, en till mig?
>> STUDENT: Om det är negativt.
>> JASON Hirschhorn: Att se till vad?
>> STUDENT: Att se till att det är i själva verket positivt.
>> JASON Hirschhorn: Exakt.
Detta är att kontrollera om det är negativ, och om det är negativt, jag
har en känsla av nästa rad kanske ska jag skrika åt användaren.
Så låt oss slå slut att genomföra denna linje.
Vi ser inte att linje som ni kanske förväntas se skrika på
användare och sedan återvänder, eftersom denna linje inte köra.
Jag angav 3.
Så jag gjorde faktiskt anger två kommando line argument, och 3 är
större än noll.
Så vi såg den linjen, avrättades vi, men vi ville inte gå
inne i om tillståndet.
>> Så nu, nästa, ser jag att jag ställer int nyckel är lika med en till jag arg v1.
Så det är jag skapa en variabel nyckel.
Så om jag skriver ut nyckeln just nu, eftersom som gör att du kan se
värde inuti variabel, nyckel är lika med 47.
Det är konstigt, men naturligtvis, det beror på att jag har inte
avrättades den linjen ännu.
Så nu om jag slog n, köra den linjen, och gör utskriftsknapp, kommer nyckeln lika 3,
vilket är vad vi förväntar oss att det till lika.
>> Så återigen, i GDB, den linje du ser du inte har verk ännu.
Du måste slå n eller s eller ett nummer av andra kommandon till faktiskt
exekvera den linjen.
Skriv ut nyckeln.
Nyckel s vid 3.
Så långt är allt bra.
String är vanlig text.
Låt oss köra den linjen.
Jag får en sträng från användaren.
>> Låt oss se i min Kontrollera 50, jag ange BARFOO versaler, så
det är vad jag ska skriva.
Om jag nu skriva ut vanlig text.
Du ser att det är lika med en sträng.
Det ger mig en annan konstig hexadecimal nummer, men det gör i
faktiskt säga att min sträng är BARFOO.
Om jag ville se vad nyckeln uppgick vid denna punkt, hur kunde jag kontrollera nyckeln?
>> STUDENTEN Print nyckel.
>> JASON Hirschhorn: Print nyckel, exakt.
Och faktiskt, det finns en genväg.
Om du tröttnar på att skriva ut, du kan bara skriva sid.
Så p knapp gör exakt samma sak.
Och igen, ser jag att det är lika med 3.
>> Om jag ville ta reda på vad både nyckel och BARFOO equaled samtidigt
men jag var trött på att skriva varje ett individuellt, jag
kan skriva info lokalbefolkningen.
Det ger mig viktiga jämlikar 3.
Enkel text motsvarar BARFOO.
Det ger mig också dessa två konstiga saker upptill, denna variabel i och
denna variabel n.
>> De som faktiskt existerande i mitt huvudprogram.
Vi har inte stött på dem ännu, men som en förhandsvisning, som
existerar i mitt för slinga.
Så just nu, de lika lite konstig siffror, eftersom de inte har
initierats ännu, men de finns kvar i minnet, så att de bara satt
till några sopor värde.
Men vi ser nyckeln i klartext text där.
>> Så jag kommer att köra den här linjen, linje 34, den för slingan.
Vi kommer att hoppa in i för slinga genom att träffa n..
Och vi är inne i för slingan.
Vi är på vår första kontroll.
Och återigen, bör dessa slags titta bekant för dig, eftersom det var en
Caesar program som skrevs, men igen, har något slags bugg.
>> Och nu om jag gör info lokalbefolkningen, eftersom jag är insidan som för slinga, ser du
att jag är lika med noll, eftersom vi förväntar oss.
Det är vad vi ställa in den till och initieras det i för slingan.
n är lika med 6.
Det är också rimligt att vi satt den till strlen av ren text.
Så jag gillar att göra info lokalbefolkningen eller skriv ut till variabel ofta att se till att
allt är alltid vad Jag förväntar mig att det lika.
I detta fall är allt vad jag förväntar mig det lika.
>> Så låt oss börja röra sig genom detta för slinga.
Linjen jag är på är linje 36, om vanligt text i är större än ett och vanlig
text i är mindre än eller lika med z.
Jag vet att mitt problem är inte med min första brev, är det med den andra bokstaven.
Om vi ​​ser tillbaka på Check 50, B går till E böter.
Jag tar det A och lämnar den som ett A, inte ändra det till D. So
något är fel med det andra brevet.
Så jag ska flytta det på en sekund.
>> Men om jag ville kolla vad vanligt text jag equaled i detta särskilda
fall, jag tycker att det borde vara vad?
Vad ska klartext jag lika i detta första omgången genom att loopen?
>> STUDENT: Zero?
>> JASON Hirschhorn: Enkel text av I?
Så det borde vara kapital B. Jag, naturligtvis, är lika med noll, men oformaterad text
bygel noll avslutad bygel motsvarar B eftersom strängar, som vi såg förra veckan,
är array, så vi får det första tecknet från det.
Så återigen, om jag skrivas ut vanlig text av Jag, jag tror faktiskt få karaktären
B. Och det är snyggt, eller hur?
Jag behöver faktiskt inte klartext I. Det är inte en av de variabler som jag som
eller initieras, men du kan skriva ut ut en mängd saker
om du skulle vilja.
>> Men låt oss gå igenom.
Om klartext jag är större än A och klartext I är mindre än eller lika med
Z, helt klart är det sant att vi har ett kapital B. Jag kommer att köra
lite kommando på det.
Vi såg att matte förra veckan, så vi ska tar det för givet att det fungerar
rätt enligt Check 50.
>> Dessa klamrar, den första visade att jag lämnar om
tillstånd, den andra visade att jag lämnar för loopen.
Och så nu när jag slog Nästa, vi får se Vi är tillbaka på för slingan igen.
Vi går igenom för slingan igen.
Låt oss verkligen kliva in i andra iteration av för slingan och typ
info lokalbefolkningen.
>> Så vi är i den andra iterationen vår för slinga.
Jag är lika med 1, som vi förväntar oss.
N är lika med 6, som vi förväntar oss.
Nyckel lika med 3, som vi förväntar oss.
Och ren text, ser du, är lika med EARFOO nu, inte BARFOO längre eftersom
i vårt tidigare iterationen, var B ändras till ett kapital E. Så vi är på väg
att stöta på problem, så detta är där vi ska
dyka i felsökning.
Men det någon som har några frågor om vad vi har gjort hittills?
Fantastiskt.
>> Så vi är på väg att genomföra detta om tillstånd, klartext fäste jag stängt
fäste större än A och vanlig text jag mindre än eller lika med Z. Men innan
Jag går in i det, eftersom det är här Jag vet att mitt misstag är, jag vill peka
ut vanlig text av I. So låt oss sätta utskrift.
Den gör motsvara tecknet A, så att verkar så långt är allt gott och väl.
>> Så jag räknar med denna linje per min logik, denna linje ska vara sant.
Det är en stor bokstav.
Men om jag slog n, vi inser att detta linje, i själva verket inte köras.
Jag hoppade ner till else if.
Varför hände det?
>> STUDENT: Eftersom du har ditt tillstånd av vanlig text är större
än A, inte är lika med eller större än.
>> JASON Hirschhorn: Så jag hade min oformaterad text I är större än A, som inte är större
än eller lika med.
Så klart, gjorde huvudstaden A inte utlösa detta om tillstånd, och vi gjorde
inte kliva in i det, och vi gjorde inte göra de nödvändiga ändringarna.
Så det är det, faktiskt.
Jag kom på min bugg.
Jag skulle kunna gå tillbaka i min källfilen, ändra det, och uppdatera den och
kör Check 50 igen.
>> Men vi får se, bara för pedagogik s skull, om jag fortsätter att gå.
Den annars om inte köra heller, men vad stället lika är kommandot
det ändras inte.
Så det har inte förändrats alls, och om jag skriva ut ren text här, vi får se att gå
genom att för slingan inte gjorde det, i själva verket, ändra på det andra tecknet alls.
Det är fortfarande en kapital A.
>> Så återigen, debuggade vi våra misstag.
Vi insåg att det inte fanns viss logik saknas.
Och vi debuggade det i förväg innan faktiskt köra den linjen,
men du skulle ha märkt hade vi bara slå på Nästa och hoppa till det annars om,
det innebär att att om villkoret var inte sant.
Vi har inte, i själva verket får resultatet förväntas vi.
Så då vi skulle ha genomfört, hade vi inte varit så klok, att titta på
att om tillstånd och kontrollera om, i själva verket, våra villkor bör utvärderas till
sant i det aktuella sammanhanget.
>> Det var allt för felsökning av det här programmet.
Är det någon som har några frågor?
Vilket kommando skulle jag slog till sluta GDB?
F: Och då jag blir ombedd, sluta hur som helst?
Ja eller nej.
Jag ska träffa ja, och jag har slutat GDB.
>> Så det var en snabb primer till GDB.
Faktiskt, i ett verkligt scenario Jag gjorde detta på kontorstid.
Jag GDBed detta exakt program på kontorstid med en elev.
Och om vi går tillbaka till de kommandon som vi såg tidigare, använde vi break, först
sak gjorde vi.
Vi använde springa med kommandoradsargument, andra saken gjorde vi.
Vi använde bredvid en hel del att flytta oss genom linjer.
Och återigen, den korta versionen nästa är n..
Det är inom parentes i grått på bilden.
>> Vi använde inte steget, men vi gjorde inte nödvändigtvis för detta fall.
Men vi skulle kunna använda den i lite senare på idag om vi felsökning, för
exempel binär sökning när binära Sök heter i ett separat
funktion, men det finns något fel med det.
Vi kommer att vilja kliva in samtalet till binär sökning och
faktiskt felsöka det.
Lista vi använde inte heller eftersom vi hade en bra känsla för vår kod, men om jag
ville få en känsla för vilken kod jag var runt, jag kunde bara använda listan.
>> Skriv att vi använt, info lokalbefolkningen som vi använt.
Fortsätt att vi inte behöver använda i detta fall, varken vi behöver använda
inaktivera, men vi gjorde användning sluta.
Återigen, dessa 10 kommandon, öva på dem.
Om du förstår dessa 10 kommandon, du bör fastställas för felsökning alla
utfärda med GDB.
>> Så vi är på väg att gå på, igen, till springande punkten i avsnitt idag, att gå över
dessa sortering och sökning algoritmer.
Innan vi gör det, återigen, några frågor, kommentarer, oro för GDB?
Så är alla kommer att använda GDB stället printf?
Så alla, för all framtid skull, alla nickar huvudet rätt
nu, så jag kommer att se dig på kontorstid och alla TF kommer att se dig och
de kommer att säga, visa mig hur man använder GDB, och du kommer att kunna
för att visa dem, eller hur?
Typ av?
Kanske förhoppningsvis.
Cool.
>> Så vi kommer att flytta in sortering och sökning.
Du ser jag har en lista som redan sorterade för oss, men det kommer inte
vara fallet alltid.
Så i den problembild specifikation för problem set tre, du har shorts
att du kan titta på, och det faktiskt ber dig att titta på dessa shorts.
Även i föreläsning i förra veckan, gick vi över en hel del av dessa algoritmer, så jag är
inte kommer att tillbringa tid i klassen går över dessa algoritmer igen eller ritning
bilder för hur dessa algoritmer fungerar.
Återigen, den informationen kan du re-watch föreläsning, eller att information
fångas utomordentligt på shortsen för dessa sökningar, alla
som finns på cs50.net.
>> Så istället, vad vi ska göra är att skriva dessa program.
Vi har en känsla, en mental modell, av hur de arbetar, och så vad vi ska
göra är att koda dem på riktigt.
Vi ska vända den mentala modell, den bilden, om man så vill, i
faktiska koden.
Och om du var lite förvirrad eller dimmig på den mentala modell, jag helt
förstå.
>> Vi ska inte faktiskt kommer att hoppa till kod direkt.
Så medan denna prompt i detta bildspel frågar du att koda binär sökning, och
faktiskt, en iterativ version av binär sökning, det första jag
verkligen vill att du ska göra är att skriva några pseudokod.
Så du har denna mentala modell om hur binär sökning fungerar.
Ta ut ett papper om du har en lätt tillgänglig, eller öppna upp en
textredigerare, och jag skulle vilja alla att skriva.
Ta fyra minuter att skriva pseudokod för binär sökning.
>> Återigen, tänk på det mentala modell.
Jag ska komma runt om du har frågor och vi kan dra bilden ut.
Men först, innan vi börjar programmera, Jag skulle vilja skriva
pseudokod för binär sökning så när vi dyka in, har vi några riktning som
där vi ska gå.
>> STUDENT: Kan vi anta den rad av värden som vi får är redan sorterade?
>> JASON Hirschhorn: Så för binär sökning till arbete - utmärkt fråga - du
måste ta i en sorterad matris med värden.
Så antar att det kommer att fungera.
Vi ska gå tillbaka till den här bilden.
Du ser i lila funktionen deklaration är bool binary_search int
värde, int-värden, int n.
Detta bör ser bekant om du har redan närmade sig eller fått din
händer smutsiga med problemet set.
>> Men det är funktionsdeklarationen.
Återigen, inte ska behöva oroa sig för så mycket just nu.
Vad jag verkligen vill att du ska göra är att ta fyra minuter till pseudo binär
söka, och sedan går vi över den som en grupp.
Och jag kommer att komma runt.
Om du har frågor är du välkommen fri att räcka upp handen.
>> Varför inte ta två minuter att avsluta den pseudo?
Jag vet att detta kan verka löjligt att Vi spenderar så mycket tid på
något som inte ens egentligen i C, men framför allt för dessa mer
utmanande algoritmer och problem uppsättningar som vi måste ta reda på,
med början i pseudokod inte oroa om syntaxen, bara behöva oroa
logiken, är otroligt bra.
Och på det sättet, du är inte lösa två otroligt svåra problem på en gång.
Du ska bara fokusera på logiken, och då du flyttar in i syntaxen.
>> OK.
Låt oss börja gå igenom pseudokoden.
Jag har skrivit upp här, binär sökning pseudokod.
Vi kommer att skriva detta på ombord tillsammans.
Eller ska jag skriva det och du kommer att ge mig uppmaning jag behöver.
Så kan någon ge mig den första raden i pseudokoden som du
skrev för binär sökning?
Ja, Annie?
>> STUDENT: Medan längden på listan är större än noll.
>> JASON Hirschhorn: Medan längd på listan är större än noll.
Och återigen ser vi några C-ser syntaktiska saker på här.
Men det mesta av detta är på engelska.
Var det någon som har någon linje de sätter innan detta i sin pseudo-kod?
>> STUDENT: Få en array av sorterade siffror.
>> JASON Hirschhorn: Du skrev "få en matris med sorterade siffror. "Per den
funktionsdeklarationen, kommer vi att passera en matris av sorterat antal.
>> STUDENTEN [OHÖRBAR].
>> JASON Hirschhorn: Så Vi kommer att ha det.
Men ja, om vi inte hade det, vi skulle behöva sortera vårt utbud av
siffror, eftersom binär sökning bara fungerar på sorterade arrayer.
Så medan längden på listan är lika med noll, jag är ska sätta i några klammerparenteser
så att det ser lite mer ut som C. Men samtidigt verkar för att kartlägga på en
while-slinga, så inne i denna stund loop vad behöver vi för att
göra för binär sökning?
>> Någon annan som inte har gett mig en svara på ännu men som skrev det här?
>> STUDENT: Gå till mitten av listan.
>> JASON Hirschhorn: Tom.
Gå till mitten av listan.
Och följdfrågan, vad gör vi när vi är på
mitten av listan?
>> STUDENT: Gör en kontroll om det är det nummer du letar efter.
>> JASON Hirschhorn: Excellent.
Gå i mitten av listan och kontrollera om vårt värde är där -
fantastiskt.
Var det någon som har något annat som var annorlunda än det här?
Det är precis rätt.
>> Det första vi gör i binär sökning är att gå till mitten av listan och
kontrollera om vårt värde är där.
Så jag antar att om vårt värde är där, vad gör vi?
>> STUDENT: Vi återvänder noll [OHÖRBAR].
>> JASON Hirschhorn: Ja, om vår värde är det, fann vi det.
Så vi kan säga något sätt, men detta Funktionen är definierad, vi talar om för användaren
vi fann det.
Om det inte finns där, men det är där det blir knepigt.
Så om det inte finns där, någon annan som arbetade med binär sökning eller
har en idé nu, vad gör vi?
>> STUDENT: Fråga.
>> JASON Hirschhorn: Ja?
>> STUDENT: Är arrayen redan sorterade?
>> JASON Hirschhorn: Ja, vi antar matrisen är redan sorterade.
>> STUDENT: Så då måste man kontrollera om det värde som du ser är större än
det värde som du vill, kan du flytta till mitten av den andra halvan.
>> JASON Hirschhorn: Så om mitten av listan är större än vad vi är
söker, då vet vi vad?
Vi rör oss där?
>> STUDENT: Du vill flytta till den halva av listan med
tal lägre än så.
>> JASON Hirschhorn: Så vi ska kalla det vänster.
Så om mitten är större, kan vi söka den vänstra halvan av listan.
Och sedan genom sökningen, vilken menar jag med sökandet?
>> STUDENTEN [OHÖRBAR].
>> JASON Hirschhorn: Vi går till mitten.
Vi upprepar faktiskt denna sak.
Vi går tillbaka genom vår while-slinga.
Jag ska ge er den sista -
annars, om det är mitt mindre än vad vi gör, vad gör vi här?
>> STUDENT: Gå till höger.
>> JASON Hirschhorn: Sök rätt.
Det ser bra ut, men det någon som har något som vi kanske saknas eller
något annat som du sätter i pseudo-kod?
Så det här är vad vi har hittills.
Även om längden av listan är större än noll, kommer vi att gå
till mitten av listan och kontrollera om vårt värde är där.
>> Om mitten är större, kommer vi att söka vänster, annars om mitten är
mindre, ska vi söka rätt.
Så vi har alla haft viss erfarenhet av ord vi använder i datavetenskap
och de verktyg vi har.
Men du kommer redan att märka att vi var tala engelska, men vi hittade en
massa saker som verkade för att kartlägga den till verktyg som vi har i vår kodning verktygslåda.
Så höger utanför bat, vi är inte kommer att faktiskt koda ännu.
>> Vad är det vi ser här på engelska som kartor på att saker och ting kan vi skriva i C?
>> STUDENT: Medan.
>> JASON Hirschhorn: Medan.
Så denna stund här kartor på vad?
>> STUDENT: En while-slinga.
>> JASON Hirschhorn: En while-slinga?
Eller förmodligen mer allmänt en slinga.
Vi vill göra något om och om igen.
Så vi kommer att koda en loop.
Och vi redan vet, för vi har gjort detta ett par gånger och vi
har gott om exempel där ute, hur man faktiskt skriver
detta index för en slinga.
Så det borde vara ganska lätt.
Vi borde kunna få det började ganska snabbt.
>> Vad ser vi här?
Vilka andra strukturer syntaxer, saker som vi känner till i C, gör vi
redan har en känsla utifrån bort av de ord vi använt?
Ja, Anna?
[OHÖRBAR]
bara skojar.
Anna, gå vidare.
>> STUDENT: Om och annat.
>> JASON Hirschhorn: Om och annat - här.
Så vad gör de se ut?
>> STUDENT: En om annat uttalande.
>> JASON Hirschhorn: Ja, förhållanden, eller hur?
Så vi måste antagligen skriva några villkor.
Och återigen, men kanske förvirrande i första, vi har i allmänhet en känsla nu
om hur man skriver villkor och syntaxen för villkor.
Och om vi inte gör det, vi ser bara upp syntax för förhållanden, klippa och klistra
att, eftersom vi vet att vi behöver en förutsättning för detta.
Alla andra saker som vi ser att kartan på saker vi kan behöva göra i C?
Ja, Aleha?
>> STUDENT: Det kan vara självklart, genom att bara kolla om en
värde är lika med något.
>> JASON Hirschhorn: Så hur ska vi kontrollera och - så gå till mitten av listan
och kolla om vårt värde är det?
Hur ska vi göra det i C?
Vad är syntaxen för det?
>> STUDENT: Lika, lika.
>> JASON Hirschhorn: Lika, lika.
Så denna kontroll är förmodligen kommer att vara ett likhets, lika.
Så vi vet att vi behöver att någonstans.
Och faktiskt, bara att skriva det, Vi ser dessa andra saker.
Vi kommer att behöva göra några jämförelseoperatorer in där -
fantastiskt.
Så det faktiskt ser ut, med och stora, har vi inte skrivit en
ord av C-kod än.
Men vi fick den mentala modellen ner via föreläsningar och dessa shorts.
>> Vi skrev pseudo-kod som en grupp.
Och redan har vi 80%, om inte 90% av vad vi behöver göra.
Nu behöver vi bara att koda den, vilket återigen är en
icke-trivialt problem att lösa.
Men åtminstone vi är fast på logiken.
Åtminstone nu när vi går till kontorstid, Jag kan säga att jag vet vad jag behöver
att göra, men kan du påminna mig om syntaxen?
Eller även om kontorstid är trångt, du kan Google för syntaxen, snarare
än att fastna på logiken.
>> Och återigen, snarare än att försöka lösa logiken och syntaxproblem alla
på en gång, är det ofta mycket bättre att bryta dessa två svåra problem ut i
två mer hanterbara och kära och göra det pseudokod först och sedan koden i C.
Så låt oss se vad jag gjorde för pseudo-kod i förväg.
>> Även om längden av listan är större än noll, titta på mitten
i listan.
Om antalet hittade tillbaka sant, annars om antalet högre, söka vänster.
Else om antalet är lägre, sök rätt, returnera false.
Så det ser nästan identiska om inte nästan identisk med vad vi skrivit.
Faktiskt, Tom, det du sa först, bryta mitt i listan och om
nummer hittas i två rapporter är faktiskt vad jag gjorde.
>> Jag kombinerade dem där.
Jag borde ha lyssnat på du första gången.
Så det är den pseudo-kod som vi har.
Om du vill nu, sorry, gå tillbaka till vårt ursprungliga problem.
Låt oss kod binary.c.
Så genomföra en iterativ version av binär sökning med hjälp av följande
funktionsdeklarationen.
>> Och du behöver inte kopiera ner riktigt än.
Jag faktiskt går att öppna upp just här binary.c.
Så det finns funktionsdeklarationen i mitten av skärmen.
Och så ser jag tog pseudo-kod från på mina sidor, men nästan identiska
vad vi skrev, och sätta det i för dig.
Så nu, låt oss ta fem minuter att koda denna funktion.
>> Och igen, om du har några frågor, upp handen, låt mig veta, jag ska
komma runt.
>> STUDENTEN [OHÖRBAR].
>> JASON Hirschhorn: Så jag tog det binära Sök definition på
överst, på linje 12.
Det är vad jag fått för mina slide.
Och sedan allt detta pseudo-kod jag bara kopiera och klistras från bilden,
pseudokod slide.
Jag är fortfarande inte höra [OHÖRBAR].
>> Så om du är klar med din genomförande, jag vill kolla upp det.
Jag mailade dig helpers.h filen tidigare i denna klass.
Och det kommer att finnas tillgängliga på nätet också för nedladdning för personer som tittar
detta avsnitt tiden fördröjs.
Och jag bara använt den generiska fördelningen kod från pset3.
Så jag tog find.C, använda min helpers.h fil snarare än den helpers.h fil
som har gett i distributionen kod.
>> Och jag var tvungen att göra en annan förändring i find.C snarare än att kräva bara helt enkelt
sök, ring binary_search.
Så om du vill testa din kod, vet att det är hur man gör det.
Faktum är att när vi ska köra den här koden just nu, jag gjorde bara en kopia av
min pset3 katalog, återigen, bytte ut hjälpare filer och sedan gjort att
förändras i find.C ringa binary_search snarare än att bara söka.
>> JASON Hirschhorn: Ja.
Har du frågor?
>> STUDENT: Nevermind.
>> JASON Hirschhorn: Inga bekymmer.
Nåväl, låt oss komma igång.
Vi kommer att koda detta som en grupp.
En andra anmärkning.
Återigen, detta är, kan enkelt bytas ut mot in för Problem Set Tre.
Jag har min helpers.h fil som, snarare än helpers.h vi gett,
förklarar binär sökning, bubbla sortera och val av sort.
Och i find.c märker du på linjen, vad är det, linje 68, kallar vi binär
sök snarare än sökning.
Så återigen, den kod som är tillgänglig nätet eller den kod som du är
skapar just nu lätt kan bytas i för p set 3 för att kontrollera det.
>> Men först, låt oss koda binär sökning.
Vår funktion deklaration, vi tillbaka en bool.
Vi tar ett heltal som kallas värde.
Vi tar en array av heltal kallas värderingar, och vi tar n vara
storleken på matrisen.
På rad 10, just här, har jag skarp inkluderar stdbool.h.
Är det någon som vet varför det finns där?
Så vad betyder det kodrad göra?
>> STUDENT: Det kan du använda en typ bool avkastning.
>> JASON Hirschhorn: Exakt.
>> STUDENT: Eller det är ett bibliotek som gör att att använda en typ bool avkastning.
>> JASON Hirschhorn: Så den kraftiga inkluderar stdbool.h linje ger mig några
definitioner och förklaringar för saker att jag får använda i
detta bibliotek.
Så bland de som säger att det finns denna typ kallas bool, och det kan vara
sant eller falskt.
Så det är vad den linjen gör.
Och om jag inte har den linjen, skulle jag få i trubbel för att skriva detta
ord här, bool, precis där.
Exakt rätt.
Så jag behöver det i denna kod.
OK.
Så denna, återigen, är en iterativ versionen, inte en rekursiv en.
Så låt oss komma igång.
>> Låt oss börja med det första linje av pseudokod.
Och förhoppningsvis kommer vi - eller inte förhoppningsvis.
Vi kommer att gå runt i rummet.
Vi går rad för rad, och jag kommer att hjälpa du räkna ut den linje som vi behöver
att skriva först.
Så medan längden på listan är större än noll.
Låt oss börja i fronten.
Vilken linje ska jag skriva Här, i kod?
>> STUDENT: Även parentes n är större än 0.
>> JASON Hirschhorn: Medan n är stor än 0.
Så n är storleken på en lista, och vi kollar om -
>> [inplacering UTTRYCKER]
>> JASON Hirschhorn: - sorry?
>> STUDENT: Hur vet vi att n är storleken på listan?
>> JASON Hirschhorn: Förlåt.
Per den pset specifikation, sökandet och fungerar sorterar du behöver för att skriva,
n är storleken på listan.
Jag glömde att förklara det här.
Men ja. n är storleken på listan, i det här fallet.
Så medan n är större än 0.
OK.
Det kan visa sig vara lite problematiskt Men om det går på.
Eftersom vi kommer att fortsätta att känna till storleken på listan under hela denna
funktion, men säger att vi börjar med en samling av fem heltal.
Och vi går igenom och vi har nu minskat ner det till
en uppsättning av två heltal.
Vilka två heltal är det?
Storleken är 2 nu när vi vill titta på, men som 2 är det?
Är det vettigt att fråga?
>> OK.
Jag frågar igen.
Så vi börjar med denna samling av 5 heltal, och n är lika med 5, eller hur?
Vi kommer att gå igenom här.
Vi ska nog ändra storlek, rätt, eftersom det går på.
Vilket är vad vi säger att vi vill göra.
Vi vill inte söka hela saken igen.
Så säger vi ändra det till 2.
Vi tar halva listan som är konstigt.
Så bara plocka 2.
Så nu n är lika med 2.
Jag ber om ursäkt för de fattiga torra radera markörer.
Rätt?
Och vi söker igenom listan igen med en lista med storlek 2.
Tja, är vår samling fortfarande av storlek 5.
Vi säger att vi bara vill Sök 2 fläckar i den.
Så som två fläckar är de?
>> Låter det vettigt?
Är de vänster 2 fläckar?
Är de rätt 2 ställen?
Är de de 2 mitt fläckar?
Vi har brutit problemet ner, men vi faktiskt inte vet vilken del av
problemet vi fortfarande tittar på, bara genom att ha dessa två variabler.
Så vi behöver lite mer då, medan n är större än 0.
Vi måste veta var det n är i våra faktiska array.
>> Så det någon som har en byta till denna linje?
Merparten av denna linje är helt rätt.
Finns det ett annat tillägg?
Kan vi byta ut något för n till gör denna linje lite bättre?
Mm-hm?
>> STUDENT: Kan du initierar en variabel såsom längd på n som sedan kommer att användas
senare i funktion?
>> JASON Hirschhorn: Så initiera en variabel längd med n,
och vi använder det senare?
Men då vi uppdaterar bara längd och vi fortfarande stöter på detta problem, där vi
skära ner längden på vårt problem, men vi vet aldrig var, faktiskt,
denna längd kartor på.
>> STUDENT: Är inte det kommer att hända senare när du säger, söka vänster,
Sök rätt?
Du kommer att gå till en annan område av ditt -
>> JASON Hirschhorn: Vi kommer att gå till ett område, men hur vet vi
vilket är att gå till?
Om vi ​​bara har matrisen och denna n, hur vet vi var de ska
gå till i arrayen.
I ryggen, ja?
>> STUDENT: Har du, liksom, en lägre gräns och en övre gräns variabel eller
något sådant?
>> JASON Hirschhorn: OK.
Så det här är en annan idé.
Snarare än att bara hålla reda på storlek, vi hålla reda på den nedre och
övre gräns variabel.
Så hur vi beräknar storleken från en undre gräns och övre gräns?
>> [inplacering UTTRYCKER]
>> JASON Hirschhorn: subtraktion.
Och även att hålla reda på den nedre bundna och övre gräns för att låta oss veta,
Vi söker dessa två?
Ska vi söka dessa två hit?
Ska vi söka på två mitten?
Förmodligen inte de två mellersta, eftersom detta i själva verket är binär sökning.
Men nu kommer vi att kunna få den storlek, utan också gränserna för arrayen.
I huvudsak, om vi har vår jätte telefonbok, vi slita den på mitten.
Vi vet nu var det mindre telefonbok är.
Men vi är faktiskt rippning telefonboken i halv.
Vi behöver fortfarande veta var nya gränserna för vårt problem är.
Är det någon som har några frågor om det?
Ja?
>> STUDENT: Skulle det fungera genom att skapa en variabel, jag, att du sedan bara flytta
position i förhållande till dess nuvarande position, och längden, n?
>> JASON Hirschhorn: Och vad är jag?
>> STUDENT: Som jag vara som sorts -
Som du vill initiera i för att vara den mellanposition av matrisen.
Och sedan, om värdet på position i i mitten av uppsättningen i befunnits
vara lägre än det värde som du behöver, jag nu blir längden av arrayen, plus
Värdet på I dividerat med två.
Liksom, se, flytta dig i -
>> JASON Hirschhorn: Höger.
>> STUDENT: - upp till -
>> JASON Hirschhorn: Så jag är nästan positiva som kommer att fungera.
Men poängen är, behöver du två bitar av information här.
Du kan göra det med början och slut, eller så kan du göra det med storlek, och sedan
någon markör.
Men du behöver två stycken av information här.
Du kan inte klara sig med bara en.
Låter det vettigt?
>> Så vi kommer att gå igenom, och vi kommer att göra [OHÖRBAR]
och skapa några markörer.
Vad gjorde du skriver in din kod?
>> STUDENT: Jag sa bara int bunden en är lika med 0.
>> JASON Hirschhorn: Låt oss kalla att int, början.
>> STUDENT: OK.
>> JASON Hirschhorn: Det gör mer meningsfullt för mig.
Och?
>> STUDENT: Jag sa, jag antar, int slutar.
>> JASON Hirschhorn: int slutar.
>> STUDENT: Jag antar, n minus 1, eller något liknande.
Liksom, det sista elementet.
>> JASON Hirschhorn: Så du skrev, int början är lika med 0, semikolon, och int
slut är lika med n minus 1, semikolon.
Så i huvudsak, vad vi gör Här, 0 den första positionen.
Och som vi vet i matriser, går de inte upp till n, går de upp till n minus 1.
Så vi har några gränser för vår samling.
Och dessa inledande gränser råkar vara de ursprungliga gränserna för vårt problem.
OK.
Så det låter bra.
Sen om vi går tillbaka till denna linje, medan längden av listan är större än 0,
vilken, i stället för N, bör vi sätter in här?
>> STUDENT: Skriv slutar minus början.
>> JASON Hirschhorn: När slutar minus början är större än 0?
OK.
Och vi kunde, om vi ville göra det lite trevligare, vad
annat kunde vi göra?
Om vi ​​ville rensa denna kod upp lite?
Hur kan vi bli av med 0?
Detta är bara en fråga stil.
Det är rätt just nu.
>> STUDENTEN Ending inte lika början?
>> JASON Hirschhorn: Vi kan göra vad?
>> [inplacering UTTRYCKER]
>> STUDENTEN Ending är större?
>> JASON Hirschhorn: Ja.
Vi kan bara göra när du slutar är större än början.
Rätt.
Vi lade början till andra sidan om det, och vi blev av med 0.
Så det här bara ser en lite renare.
OK.
Så, medan längden på listan är 0, skrev vi som är större samtidigt som slutar
än början.
Vi kommer att sätta in vårt behov klamrar, och sedan det första
vi vill göra är att titta på dem i en liten lista.
Du?
Kan du ge mig den -
>> STUDENT: Om parentes värde hakparentes -
>> JASON Hirschhorn: Om parenteser värde hakparentes.
>> STUDENT: slutar delat med 2.
>> JASON Hirschhorn: Ending?
>> STUDENT: Jag ser ett problem med ditt -
>> JASON Hirschhorn: OK.
Tja, titta på mitten.
Hur vet vi vad mitt är?
Yeah.
Så låt mig ta bort den koden.
Hur vet vi vad mitt är?
I vad som helst, när du har början och i slutet, hur tycker du att
mitten?
>> STUDENT: Du genomsnitt.
>> STUDENT: Du lägger dem tillsammans och sedan -
>> JASON Hirschhorn: Lägg dem tillsammans och sedan?
>> STUDENT: Och du genomsnitt.
Dela det med 2.
>> JASON Hirschhorn: Lägg dem samman och dividera med 2.
Så int mitten är lika?
Tom, kan du ge den till mig?
>> STUDENT: Början plus slutar -
>> JASON Hirschhorn: Början plus slutar.
>> STUDENT: Alla, hållare, delat med 2.
>> JASON Hirschhorn: Alla, inom parentes, dividerad med två.
Så det ger mig mitt av något, korrigera?
>> STUDENT: Du måste också att runda upp.
>> JASON Hirschhorn: Vad gör du menar, jag behöver för att runda upp det?
>> [inplacering UTTRYCKER]
>> STUDENT: För om det är en udda nummer, då är det som om -
>> JASON Hirschhorn: Tja, OK.
Så jag kunde runda upp.
Men om det är ett ojämnt antal, 5, kan jag tar en bort från mitten.
Eller om det är ett jämnt tal, snarare det är en bättre fråga.
Om det är 4, har vi bara 4, kan jag ta den första "mitten", citat, unquote eller
den andra "mitt" en.
Antingen skulle fungera för en binär sökning, så jag egentligen inte behöver för att runda det.
Men det finns en annan sak som jag måste titta på den här raden.
Vi kanske inte inser det än, men vi ska återkomma till det.
Eftersom denna linje faktiskt fortfarande behöver en annan sak.
>> Men än så länge har vi skrivit fyra rader kod.
Vi har fått vår början och slutar markörer.
Vi har vår while-slinga, som kartlägger den direkt till vår pseudokod.
Vi tittar på mitten som mappar direkt på vår pseudokod.
Jag skulle säga att detta går till mitten på listan, denna rad kod.
Och sedan, när vi går till mitten av listan, nästa sak vi måste göra
är kontrollera om vårt värde är där för den pseudokod som vi skrev tidigare.
>> Så hur ska vi kontrollera om vårt värde är vid mitten av listan?
Du.
Varför inte göra det här?
>> STUDENT: Om vårt värde är är vid mitten är lika med
vad vi än ställer in -
Jag menar lika lika med -
>> JASON Hirschhorn: Det -
OK.
>> STUDENT: Jag är inte säker på vad det variabel vi söker
för även om, är att -
>> [inplacering UTTRYCKER]
>> STUDENTEN [OHÖRBAR].
>> JASON Hirschhorn: Exakt.
Per funktionsdeklarationen, Vi letar efter ett värde.
Så vi söker efter ett värde i en matris med värden.
Så du är exakt rätt.
Du kommer att göra, om det öppna föräldra värde fäste mitten stängd Fästets jämlikar
lika värde, och inuti finns vad behöver vi göra?
Om vårt värde är där, vad behöver vi göra?
>> [inplacering UTTRYCKER]
>> STUDENT: Tillbaka noll.
>> JASON Hirschhorn: Returnera sant.
>> STUDENT: Returnera sant.
>> JASON Hirschhorn: Michael, vad gör denna linje göra?
>> STUDENTEN [OHÖRBAR] programmet har körts sin gång, och det är över, och
du har vad du behöver göra?
>> JASON Hirschhorn: Programmet eller vad?
I det här fallet?
>> STUDENT: Funktionen.
>> JASON Hirschhorn: Funktionen.
Och så, för att återgå till vad som kallas den och ge den värdet sant.
Exakt rätt.
Main.
Vad är det för typ retur av huvud, Michael?
>> STUDENT: int, heltal?
>> JASON Hirschhorn: int, exakt.
Ett heltal.
Det var bara en fråga för att se till ni har varit på toppen av det.
Vad innebär det oftast tillbaka, om allting fungerar bra?
>> STUDENT: Noll.
>> JASON Hirschhorn: Zero.
Exakt rätt.
>> STUDENT: Om detta återkommer bara sant, det finns ingen information som ges
om vad -
Åh, det är bara att säga att det värde är inuti matrisen.
>> JASON Hirschhorn: Exakt.
Detta program är inte att ge information om var exakt värde är.
Det är bara att säga, ja, vi hittade det, eller nej, det gjorde vi inte det.
Så om antalet hittas, return true.
Jo, faktiskt vi bara gjorde det riktigt snabbt med att en rad kod.
Så jag ska flytta den linjen av pseudokod.
>> STUDENT: Inte vi behöver att ändra arrayen?
Det bör vara värden, inte värde, eller hur?
>> JASON Hirschhorn: Förlåt.
Tack.
>> STUDENT: Ja.
>> JASON Hirschhorn: Denna rad bör vara värden.
Exakt rätt.
OK.
Så vi har tittat på mitt lista.
Om antalet hittade avkastning sant.
Fortsätter med vår pseudokod, om mitten är större, sök kvar.
Så jag hade i här, om antalet högre, sök kvar.
Konstantin, kan du ge mig denna kodrad?
>> STUDENT: Om värdet på mitten -
>> JASON Hirschhorn: Så om värde -
om öppen paren värderar fäste mitten nära fäste -
>> STUDENT: Är mindre än värdet?
>> JASON Hirschhorn: Är mindre än.
>> STUDENT: Mindre än värdet.
>> JASON Hirschhorn: Värde.
Jo, faktiskt, vill du kontrollera om numret -
Ursäkta.
Det är lite förvirrande.
Men annars om antalet i mitt i listan är större.
>> STUDENT: Åh, OK.
>> JASON Hirschhorn: Jag ska ändra på det.
Annars om mitten är högre, vi vill söka vänster, OK?
Och vad gör vi inne detta om tillstånd?
>> STUDENT: Kan jag göra en liten förändring till tillståndet, ändra det till annars om?
>> JASON Hirschhorn: Else om?
OK.
Så här koden kommer att utföra ungefär samma.
Men det fina med att använda om, annars om, annars om eller om det, annars om, annars
innebär att endast en av dem kommer att kontrolleras, inte alla tre av dem,
potentiellt.
Och det gör det lite trevligare på den dator som är
köra ditt program.
>> Så [? Konstantin,?]
Vi är inne i den här linjen, annars om värderingar, fäste mitten nära fästet
är större än värdet.
Vad behöver vi göra?
Vi måste söka vänster.
Hur gör vi det?
Jag ska ge dig en start.
>> Vi har dessa två saker som kallas börjar och slutar.
Så vad som behöver hända till början?
Om du vill söka till vänster om lista, får vi vår nuvarande början.
Vad behöver vi göra det?
>> STUDENT: Vi sätter början till mitten plus 1.
>> JASON Hirschhorn: Så om vi är söka på vänster?
>> STUDENT: Förlåt, mitt minus -
så ändelsen skulle vara mitt minus 1 och början -
>> JASON Hirschhorn: Och vad händer med början?
>> STUDENT: Det förblir densamma.
>> JASON Hirschhorn: Så börden förblir densamma.
Om vi ​​söker vänster, vi är använder samma början -
exakt rätt.
Och det slutar?
Tyvärr, vad betyder det slutar lika igen?
>> STUDENT: Middle minus 1.
>> JASON Hirschhorn: Middle minus 1.
Nu, varför minus 1, inte bara mitt?
>> STUDENTEN Den mellersta är ur bilden redan, eftersom vi hade
kontrollerat att den är ute?
>> JASON Hirschhorn: Det är exakt rätt.
Den mellersta är ute ur bilden.
Vi kontrollerade redan i mitten.
Så vi vill inte "mitt" citat unquote, att fortsätta att vara i
array som vi söker.
Så det här är fantastiskt.
>> Else om värden fäste mitten är större än värdet slutar jämlikar
mitt minus 1.
Jeff, hur är detta sista raden?
>> STUDENT: Else.
Värden mitten är mindre än värdet?
>> JASON Hirschhorn: Vi ska du ger mig annat.
Så om du inte ger mig -
>> STUDENT: Så då börjar skulle vara mitt plus 1.
>> JASON Hirschhorn: Början jämlikar mitten plus 1, återigen, för samma
Anledningen till att Constantine gav oss tidigare.
Och i slutet, har som inte gett mig en kodrad ännu?
Returnera false, Aleha, vad vi skriver här?
>> STUDENTEN returnera false.
>> JASON Hirschhorn: returnera false.
Och vi måste göra det, för om vi inte att den är, måste vi säga att vi
hittade inte det.
Och vi sa att vi ska gå tillbaka en bool, så vi har definitivt återvända
en bool någonstans.
>> Så låt oss köra den här koden.
Jag är faktiskt tänker -
så vi är i terminalen.
Vi ska klara vårt fönster.
Låt oss göra allt.
Vi fann att det finns ett fel.
Det finns ett fel på rad 15, förväntas semikolon i slutet av
deklaration.
Så vad har jag glömt?
>> STUDENT: Semikolon.
>> JASON Hirschhorn: Semikolon rätt upp här.
Jag tror att det var Toms kod.
Så Tom, [OHÖRBAR].
Skojar bara.
Låt oss inte göra hela igen.
>> STUDENTEN Vad Dropbox katalog bör vi vara på detta?
>> JASON Hirschhorn: Så du kan bara titta på detta lite.
Men återigen, om du ville flytta detta koda in din pset3 katalog för att försöka
ut, det är vad jag gjorde.
Om du kommer att märka här - ledsen, bra fråga.
>> [? LS,?]
Jag har här på find.c koden från denna veckas distro kod.
Jag har helpers.h.
Jag har en Make-fil som jag faktiskt redigerade lite för att inkludera dessa nya
filer vi skriver.
Allt i denna lag kommer att finnas tillgänglig, inte distributionskoden, men den nya
Gör filen, den nya helpers.h filen kommer finnas tillgängliga på nätet för nedladdning.
Återigen, så de är de extra koder vi har.
>> Så gör alla, per denna linje, gör hitta, binär, val bubbla - märken
alla tre av dem och sammanställer i denna körbar kod find.
Så generellt, vill vi inte att direkt till check50.
Vi vill köra några tester på egen hand.
Men bara så att vi kan påskynda lite, check50 2013 pset3.find kommer att passera
i helpers.c-- min dåliga.
>> Jag har inte det just nu.
Så vi faktiskt kommer att köra koden på riktigt.
Usage.find /, vet du vad det betyder?
>> STUDENT: Du behöver en andra kommandoraden på det.
>> JASON Hirschhorn: Jag behöver en andra kommandorad.
Och per specifikationen, jag behöver att ange vad vi letar efter.
Så låt oss titta efter 42.
Vi kommer att hålla den i sorterad, eftersom vi har inte skrivit ännu en sorteringsfunktion -
42, 43, 44.
>> Och Kontroll D inte hittar nålen i höstacken.
Det är illa.
Det är definitivt där.
Låt oss prova något annat.
Kanske är det för att jag satte det i början.
>> Låt oss göra 41, 42, 43.
Så där.
Man fann det.
Låt oss uttrycka det i slutet nu, bara så att vi kan vara noggrann -
40, 41, 42.
Hittade inte nålen.
Så jag nämnde detta tidigare.
Tyvärr visste jag detta skulle hända.
>> Men för pedagogiska ändamål, det är bra att utforska den.
Det fungerar inte.
Av någon anledning, kan inte hitta den.
Vi vet vad som finns där, men vi inte hitta den.
Så en sak vi kan göra är att gå igenom GDB för att hitta den, men inte vem som helst,
utan att gå igenom GDB, ha en känsla av var vi skruvas upp?
[? Madu? ?]
>> STUDENT: Jag tror att det kan bli när man slutar är lika med början, och det är
bara en en-inslag listan.
Då är det bara ignorerar det istället att faktiskt kontrollera det.
>> JASON Hirschhorn: Det är exakt rätt.
När avslutningen är lika med början, gör vi fortfarande har en del i vår lista?
>> STUDENT: Ja.
>> JASON Hirschhorn: Ja, i själva verket är vi har en och endast en del.
Och det kommer sannolikt att hända när, per koden som vi testade, vi är på
framför höstacken eller vid slutet av höstack.
Det är där början och slut kommer att lika
en, med binär sökning.
Så i dessa två fall är det inte fungerade, eftersom sinande var lika med början.
>> Men om sinande är lika med början, gör detta medan loop köra?
Det gör det inte.
Och vi kunde ha kontrollerat det igen genom GDB.
Så hur kan vi åtgärda det här koden, eftersom när medan slutar är lika med
början, vill vi också här while-slinga för att köra.
>> Så vad fix kan vi göra till linje 18?
>> STUDENTEN [OHÖRBAR] är större än eller lika med.
>> JASON Hirschhorn: Exakt rätt.
Medan sluttid är större än eller lika med början.
Så nu ser vi till att få det hörn fall i slutet.
Och låt oss se.
Låt oss köra det en gång till.
>> Låt oss göra allt.
Återigen måste du bara följa med här.
Hitta 41 denna gång.
Bara hålla det konsekvent.
>> Hitta 42.
Låt oss uttrycka det i början -
42, 43, 44.
Vi fann det.
Så det var verkligen förändringen vi behövde göra.
>> Det var en hel del kodning vi precis gjorde, binär sökning.
Är det någon som har några frågor innan Jag går vidare in i rader som vi skrev i
binär sökning, eller hur vi tänkte ut vad vi räkna ut?
Innan vi går vidare vill jag också peka att i stort, vi kartlagt
vår pseudo-kod en till en på vår kod.
>> Vi hade så knepig sak att räkna ut med
börjar och slutar.
Men hade ni inte listat ut det, du skulle ha skrivit ganska mycket
identisk kod, med undantag för de två översta raderna.
Och då skulle du ha insett när du gjorde det i kontroller och fall som
du behöver något annat.
Så även om du hade följt vår pseudo-kod rad för rad, skulle du har
fått alla utom två rader koda du behövs för att skriva.
>> Och jag skulle vara villig att satsa att ni skulle ha räknat ut det
ganska snabbt, att du behövs för att sätta någon form av markör i det att räkna
reda på var du var.
Det igen, är kraften i att göra pseudo-kod i förväg.
Så vi kan göra logiken först, och sedan Vi kan oroa syntaxen.
>> Hade vi varit förvirrad om logiken samtidigt som man försöker att skriva denna kod i C,
vi skulle ha fått alla trasslat till.
Och då vi skulle ställa frågor om logik och syntax och meshning
dem alla tillsammans.
Och vi skulle ha blivit förlorade i vad som kan snabbt bli en
mycket svårt problem.
Så låt oss gå vidare nu till val av sort.
>> Vi har 20 minuter kvar.
Så jag har en känsla av att vi inte kommer att kunna få igenom alla val slag
och bubbel sort.
Men låt oss åtminstone försöka för att avsluta val sortera.
Så genomföra val sortera använder Följande funktionsdeklarationen.
>> Återigen, detta tas från problem set specifikation.
Int värden är konsoler, är en array av heltal.
Och int.n är storleken på matrisen.
Urval sort går att sortera denna array.
>> Så enligt vår mentala modell av val sortera, vi drar -
Först går vi igenom listan den första tid, hitta det minsta antalet,
lägga den i början, hitta den andra minsta antal, lägga den i
andra plats om vi vill sortera i stigande ordning.
Jag tänker inte tvinga dig att skriva pseudo-kod just nu.
>> Men innan vi gör koden som en klass i fem minuter, kommer vi att skriva
pseudo-kod så att vi har någon mening om vart vi ska.
Så försök att skriva pseudokod på egen hand.
Och sedan försöka vända det pseudo-kod i kod.
Vi kommer att göra det som en grupp i fem minuter.
>> Och naturligtvis, låt mig veta om du har några frågor.
>> STUDENT: Att det?
>> JASON Hirschhorn: Se hur långt du kan komma i två minuter.
Jag förstår att du inte kommer att kunna avsluta.
Men vi kommer att gå över det här som en grupp.
>> Du är all kodning så [OHÖRBAR], så jag är ledsen att pausa det du gör.
Men låt oss gå igenom det här som en grupp.
Och återigen, binär sökning, ni alla ger mig en om inte flera rader kod.
Tack för det.
Vi kommer att göra samma sak här, kod tillsammans som en grupp.
>> Så val sort - låt oss skriva några snabba pseudo-kod.
Per mental modell, kan någon ge mig den första raden i pseudo-kod, tack?
Vad vill jag göra?
>> STUDENT: Även om listan är i ordning.
>> JASON Hirschhorn: OK, medan listan är i ordning.
Och vad menar du med "out of order?"
>> STUDENT: Även om [OHÖRBAR]
har inte sorterats.
>> JASON Hirschhorn: Medan listan är ur funktion, vad gör vi?
Ge mig den andra raden, snälla, Marcus.
>> STUDENT: Så hitta nästa minsta talet.
Detta kommer att vara indragna.
>> JASON Hirschhorn: Så hittar Nästa minsta talet.
Och sedan någon annan?
När vi hittar den näst minsta nummer, vad gör vi?
Jag kommer att säga hitta det minsta antalet.
Det är vad vi vill göra.
>> Så hitta det minsta antalet.
Men vad ska vi göra?
>> STUDENTEN [OHÖRBAR] till början.
>> JASON Hirschhorn: Förlåt?
>> STUDENT: Lägg den i början av listan.
>> JASON Hirschhorn: Så placera den i i början av listan.
Och vad gör vi med den saken det var i början
på listan, eller hur?
Vi ska skriva över något.
Så var ska vi sätta det?
Ja, Anna?
>> STUDENT: Var det minsta Antalet var?
>> JASON Hirshhorn: Så sätter början av listan där
minsta talet var.
Så när listan är i ordning, hitta det minsta antalet, placera den i
i början av listan, placera början av listan där
minsta talet var.
Marcus, kan du formulera om denna linje medan listan är ur funktion?
>> STUDENT: Även om siffrorna har inte sorterats?
>> JASON Hirshhorn: OK, så för att vet att siffrorna inte har varit
sorteras, vad behöver vi göra?
Hur mycket behöver vi gå igenom den här listan?
>> STUDENT: Så jag antar att en for-loop, eller samtidigt, medan siffrorna kontrolleras är mindre
än längden av listan?
>> JASON Hirshhorn: OK, det är bra.
Jag tror att jag misphrased min fråga dåligt.
Jag försökte bara komma på vi kommer att behöva gå
igenom hela listan.
Så medan listan är ur funktion, för mig är svårt att kartlägga den.
Men i grund och botten, det är hur Jag tycker om det här.
Gå igenom hela listan, hitta minsta antalet, placera den i
början - faktiskt, du har rätt.
Låt oss sätta dem båda.
>> Så när listan är i ordning, vi behöver gå igenom hela listan
gång, hitta det minsta antalet, plats den i början av listan, sätta
början av listan där minsta antal var, och sedan om den
Listan är fortfarande ur funktion, vi har fick gå igenom detta
processen igen, eller hur?
Det är därför val sortera, Big-O runtime av urvals sortera, någon?
>> STUDENT: n kvadrat.
>> JASON Hirshhorn: n i kvadrat.
Eftersom som Marcus och jag bara insåg Här kommer vi att behöva
gå igenom listan listan antal gånger.
Så gå igenom något av längden n n antal gånger
är faktiskt n kvadrat.
>> Så det här är vår pseudokod.
Det ser mycket bra ut.
Är det någon som har några frågor om pseudokoden?
Eftersom faktiskt urval sort bör förmodligen komma 1-1, kod från
pseudokod.
Så några frågor om logiken i pseudokoden?
Fråga nu.
>> Val av sort - medan listan är ute av ordning, vi kommer att gå igenom den
och hitta den minsta varje gång och lägga den i fronten.
Så medan listan är ur funktion, kan någon ge mig den kodrad som
har inte gett mig en linje av koden ännu, snälla?
Det låter som en vad?
>> STUDENT: Det är en for-loop.
>> JASON Hirshhorn: Det låter gillar en for-loop.
OK, kan du ge mig den för loop?
For -
>> Elev: Jag är lika med 0.
>> JASON Hirshhorn: i eller -
Vad är det vi saknar?
Vad går just här?
>> STUDENT: Int.
>> JASON Hirshhorn: Exakt.
(Int i = 0; -
>> STUDENT: i <n, i + +).
>> JASON Hirshhorn: Nailed det, Jeff.
Vi går igenom listan, eller hur?
Vi har sett att koden innan.
Perfect.
Så låt oss sätta våra klammerparenteserna här.
Jag kommer att lägga en del krullparenteser här.
>> Så även om det är 0, vi måste gå igenom hela listan.
Så varje gång vi går igenom listan, vad vill vi att hålla reda på?
>> STUDENT: Om några swappar görs.
>> JASON Hirshhorn: Hitta det minsta antalet.
Så vi bör nog hålla koll på det minsta antalet varje gång.
Så linje kan jag göra för att hålla koll av det minsta antalet?
Aleha, hur kan jag behålla koll på någonting?
>> STUDENT: Starta en ny variabel.
>> JASON Hirshhorn: Starta en ny variabel.
Så låt oss skapa en variabel.
Vilken typ?
>> STUDENT: Int.
>> JASON Hirshhorn: Int.
Låt oss kalla det det minsta.
Och vad gör det lika när vi just har börjat?
Vi har inte gått igenom listan ännu.
Vi är på den första delen av lista vår första gången igenom.
Vad gör det lika, minsta antal?
>> STUDENTEN värden som jag.
>> JASON Hirshhorn: värden som jag.
Det låter precis rätt, eller hur?
Det minsta antalet i början är där vi är.
Så nu har vi vår minsta, och vi behöver att gå igenom hela listan och
jämföra detta minsta till allt annat.
Så går vi igenom listan igen?
Michael?
>> STUDENT: Du måste göra annan för slinga.
>> JASON Hirshhorn: Another för slinga.
Låt oss göra det.
Ge mig lite kod.
>> STUDENT: För loop -
för de minsta -
bara int j, kan man säga?
= 0, så att -
>> JASON Hirshhorn: Tja, om vi vill att gå igenom hela listan -
>> STUDENT: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
Vi kommer att gå igenom den för slingan igen.
Och hur ska vi hitta minsta antal?
Tom?
Vi har den nuvarande minsta antalet, så hur ska vi hitta nya minsta?
>> STUDENT: Vi kan kontrollera om de minsta antal vi har är större än
värden bygel j.
>> JASON Hirshhorn: Så om minsta är högre än värden fäste j..
Så om vår nuvarande minsta är större än -
Jag kommer att flytta dessa två linjer av kod där ute för en sekund.
Eftersom innan vi gör något swapping, vi behöver gå igenom hela listan.
Så här pseudo bör faktiskt vara utanför den inre for-loop.
Så gå igenom hela listan.
Om minsta är större än värden j sen då?
>> STUDENTEN Sedan minsta är lika med värdena j.
>> JASON Hirshhorn: Fantastic.
En snabb fråga -
första gången vi går igenom denna slinga, Jag kommer att vara lika med 0, är ​​j går
ska ha värdet 0 när vi kommer in här.
Så vi kommer att jämföra ett antal till sig själv.
Är det effektivt?
Nej, det är inte riktigt effektivt.
Gör så vår j måste gå från 0 till n varje gång?
Behöver vi alltid för att kontrollera igenom hela listan?
[OHÖRBAR]?
>> STUDENT: Börja med i stället.
>> JASON Hirshhorn: j burk börja med vad?
>> Elev: Jag.
>> JASON Hirshhorn: j kan börja med jag.
Så nu vi jämför med början med den som vi är på.
Men även då, är det som effektiv som möjligt?
>> STUDENT: i + 1.
>> JASON Hirshhorn: i + 1 verkar vara den mest effektiva, eftersom vi
redan har jag.
Vi anger att eftersom minsta i linje 15.
Vi ska börja med nästa automatiskt.
Så vi går igenom för loopen.
Vi går igenom varje gång.
Vi kommer att gå igenom ett antal gånger.
Nu har vi fått genom denna inre för slinga.
Vi har det minsta värdet sparas.
Vi måste hålla den mot det början av listan.
Så hur gör jag det på början av listan?
Vad är den variabel som refererar till början av listan?
Vi är i den här utanför för slinga, så vad avser det
början av listan?
>> STUDENTEN värden som jag.
>> JASON Hirshhorn: Exakt rätt.
Värden i är början av den -
eller ledsen, inte i början.
Det var förvirrande.
Det är där vi är i början av den osorterade delen av listan.
Så värderar jag.
Och vad betyder det lika?
>> STUDENT: Minsta.
>> JASON Hirshhorn: Värden i lika vad?
>> STUDENT: Minsta.
>> JASON Hirshhorn: Minsta.
Exakt rätt.
Så vi placera den i början av listan, och nu måste vi sätta
början av listan där det minsta antalet var.
Så hur skriver jag där minsta talet var?
Värden på vad?
>> STUDENT: 0.
>> JASON Hirshhorn: Den lilla nummer är på 0?
>> STUDENT: Ja.
>> JASON Hirshhorn: Vad händer om de minsta Antalet var vid slutet av
detta osorterad lista?
>> STUDENT: Förlåt, vad var frågan?
>> JASON Hirshhorn: Var är det minsta antalet?
Vi tog den minsta och lägga den på början, med denna linje här.
>> STUDENT: Det borde ha lagrats i vissa -
>> STUDENT: Värden j.
>> JASON Hirshhorn: Tja, det är inte nödvändigtvis värden j..
Det behöver inte ens existerar på denna punkt.
>> STUDENT: Du måste deklarera en variabel tidigare och
tilldela den till -
när du hittar det minsta antalet, tilldela index för det numret till
viss variabel eller något liknande.
>> JASON Hirshhorn: Så kan du säga det igen?
>> STUDENT: Så var du deklarerat int minsta, bör du också deklarera int
minsta index = i, eller något liknande.
>> JASON Hirshhorn: Så där jag tror int minsta, ska jag inte bara hålla reda
av värdet men platsen.
int smallest_location = i detta fallet, vi bara gör jag.
Vi måste veta var det är.
Vi fick till slutet av koden, och vi insåg vi hade ingen aning om var det var.
Och så igen, vi är kartläggning detta på 00:59.
Ni som kodar detta på din egen vilja förmodligen få samma problem.
Hur sjutton hittar jag den?
Och då inser man, vänta, jag behöver för att hålla reda på det.
>> Så om minsta är större än värdena j.
Vi satt minsta lika med värden j..
Vad mer behöver vi förändra?
Constantin, vad annars göra Vi behöver ändra?
>> STUDENT: Läget.
>> JASON Hirshhorn: Exakt.
Så ge mig den linjen i kod.
>> STUDENTEN smallest_location = j.
>> JASON Hirshhorn: Exakt.
Och sedan ner i slutet, om vi vill satte i början av listan där
det minsta antalet var, hur vi hänvisar till var
minsta talet var?
Marcus?
>> STUDENT: Det minsta antalet var ligger på minsta plats.
>> JASON Hirshhorn: Så vid värden smallest_location.
Och vad har vi lagt där?
I början av listan, vad är det?
>> STUDENT: Tja, vet vi inte riktigt vet längre eftersom vi skrivit över.
Så det är ett bytte platser av dessa två rader?
Om du byter dessa två linjer runt.
>> JASON Hirshhorn: OK, så vi gör inte längre, eftersom vi återställa linjen
innan värden jag till minsta.
Så vi förlorade det ursprungliga värdet.
Så du sa att byta dessa två linjer.
Så nu satte i början av listan där det minsta antalet var.
Så smallest_location lika värden i..
Det rör sig i början av detta osorterade delen av listan till
minsta läge.
Och sedan in i värden jag vi flyttar det minsta talet.
>> Låter det vettigt att vi var tvungen att göra det swap?
Vi skulle ha skrivits över det värdet - en annan sak du förmodligen skulle ha
räknat ut och fann i BNP.
Så vi har tagit hand om all pseudokod.
Finns det något annat vi behöver skriva här?
Kan någon komma på något?
>> STUDENT: Hur vet du när du är klar?
>> JASON Hirshhorn: Hur gör vi vet när vi är klara?
Bra fråga.
Så hur vet vi när vi är klara.
>> STUDENT: Skapa en variabel för att hålla räkningen av om det finns en swap gjort eller inte
och går igenom ett pass.
>> JASON Hirshhorn: OK.
Det skulle fungera i bubbel sort.
Men för urvalet sortera, om vi inte göra en swap, kan det bara vara
eftersom det minsta värdet är i det dess rätt plats.
Vi kanske har en lista 1, 2, 4, 3.
Den andra gången vi kommer inte att göra några swappar.
Vi kommer att vara på nummer 2, men vi ska fortfarande behöver för att hålla igång.
Så behöver vi för att hålla reda på när vi är klara, eller vill vi bara att gå
tills det är klart?
>> STUDENT: Vi kan bara gå tills den är klar.
>> JASON Hirshhorn: Vi kan bara gå tills det är klart.
I bubbel sortera, du är precis rätt, Jeff och Aleha, med din lösning -
det är bra att hålla reda på hur många swappar du gjort, för i bubblan
sortera, om du gör det i själva verket gör inga swappar, du är klar och du kan kanske minska din
Problemet ner lite.
Men för urvalet sortera, har du verkligen fick gå fram till slutet av den
lista varje gång.
>> Så det här är det.
Vi har två minuter kvar.
Låt oss göra allt.
Låt mig bara öppet Hitta hit och göra säker på att jag faktiskt ringer upp -
Jag tänker inte kalla bubbla sortera.
Låt oss ändra detta till val slag.
göra allt. / hitta.
Låt oss hitta 42.
Den här gången ska vi passera en osorterad lista, eftersom det borde sortera
första, per fyndet kod - bör sortera först med hjälp av vår sorteringsfunktion och sedan
leta efter något.
Tummarna alla.
>> Åh herregud.
Whoa, fick mitt hjärta att slå.
Så det är korrekt.
Faktum är att om vi körde detta mer utsträckning, koden, så vitt jag kan
berätta, är helt rätt.
Det finns några förslag Jag vill ha dig.
Till exempel, 15 och 16 verkar lite överflödig.
Det verkar som att du inte nödvändigtvis måste spara både dem.
Om du har den minsta plats, du kan lätt hitta det minsta värdet av
bara skriva värden på i.
>> Så om jag skulle klassificera din kod, som jag faktiskt kommer att vara, skulle jag
förmodligen ta bort en punkt om du ingår båda dessa, eftersom du
behöver inte båda dessa.
Om du har plats kan du mycket lätt få värdet.
Och det verkar lite konstigt att lagra dem båda.
Kanske inte ens ta en punkt, men säkert kommentera att det är kanske
inte ett stilist val du måste göra.
Naturligtvis koden fortfarande går alldeles utmärkt.
>> Så tyvärr gjorde vi inte få att bubbla slag.
Jag är ledsen för det.
Vi gjorde slut val sort.
Är det någon som har några sista frågor om val av sort?
>> OK, innan vi beger oss ut, jag vill ha dig att öppna upp din Chrome webbläsare.
Tyvärr var det bara ett flagrant plugg för en typ av webbläsare.
Du kan öppna upp någon typ av webbläsare, men det kommer förmodligen att Chrome.
Och gå till följande webbplats -
sayat.me/cs50.
Om du inte skriver i din dator just nu, är du helt klart
inte gör det, Tom.
>> Och var snäll och gör det heller rätt nu eller i nästa timme -
ge mig lite feedback.
Det här är bara avsnitt två.
Vi har många fler tillsammans, så jag har ett stort utrymme för att förbättra.
Jag förhoppningsvis också gjorde vissa saker bra.
Så du kan få mig att må dåligt, men om du också vill ge mig en smiley
ansikte, skulle jag uppskatta det också.
Fylla den i.
>> Och med en minut kvar, det var vecka tre.
Jag ska stå utanför för lite Om du har några frågor.
Jag kommer att se er i föreläsning imorgon.