[Powered by Google Translate] [§ 4] [mindre komfortable] [Nate Hardison] [Harvard University] [Dette er CS50.] [CS50.TV] 

Greit, velkommen tilbake til del. I denne ukens avsnitt skal vi gjøre et par ting. Vi skal først oppsummering Problem Set 2, som er Caesar og Vigenère oppgavesettet. Og så skal vi dykke inn Quiz 0 anmeldelse og tilbringe litt tid recapping hva vi har snakket om i hver av forelesningene så langt, og vi vil også gjøre noen problemer fra fjorårets spørrekonkurranser. På den måten dere har en god måte å forberede for det. 

Hvis du vil starte, har jeg startet opp et par gode løsninger for den forrige oppgavesettet, Set Oppgave 2, inn i dette rommet. Hvis dere alle treffer denne linken, og hvis du klikker mitt navn og klikk på min første revisjon vil du se caesar.c, som er akkurat det jeg ser på. La oss snakke om dette virkelig raskt. Dette er bare et eksempel løsning. Dette er ikke nødvendigvis den perfekte løsningen. Det er mange forskjellige måter å skrive dette, men det er et par ting som jeg ønsket å markere som jeg så da jeg var gradering, vanlige feil som jeg tror denne løsningen gjør en svært god jobb med håndtering. 

Den første er å ha en slags header kommentar på toppen. På linjene 1 til 7 ser du detaljene, hva dette programmet gjør. En god standard praksis når du skriver C-kode uansett om programmet er i en enkelt fil eller enten det er fordelt over flere filer er å ha noen form for orientere kommentar på toppen. Dette er også for folk som går ut og skrive kode i den virkelige verden. Det er der de vil sette informasjon om opphavsrett. Nedenfor er # omfatter. På linje 16 er det denne # define, som vi vil komme tilbake til i en smule. Og deretter en gang funksjonen starter, når viktigste starter, fordi dette programmet er alle inneholdt i en enkelt funksjon den aller første som skjer, og dette er veldig idiomatisk og typisk for et C-program som tar i kommandolinjeargumenter-er at det umiddelbart sjekker 

for argumentet teller, argc. Akkurat her ser vi at dette programmet er ventet to argumenter nøyaktig. Husk at det er det første argumentet som er spesiell en det er alltid navnet på programmet som blir kjørt, navnet på den kjørbare filen. Og så hva dette gjør er det hindrer brukeren i å kjøre programmet med flere eller færre argumenter. Grunnen til at vi ønsker å se etter denne gang er fordi Vi kan faktisk ikke tilgang til denne argv rekke her pålitelig før vi har sjekket for å se hvor stort det er. 

En av de vanligste feilene jeg så var folk ville umiddelbart gå i og grip argv [1]. De hadde ta nøkkelen argument ut av tabellen og gjøre en til jeg se på det, og deretter de ville gjøre testen for argc samt neste test, hvorvidt det første argumentet var faktisk et heltall på samme tid, og det ikke fungerer fordi i tilfelle at det ikke er noen argumenter som følger du skal flytte et argument som ikke er der eller forsøker å hente en som ikke er der. 

Den andre store ting som du bør legge merke til er at du alltid ønsker å skrive ut en slags nyttig feilmelding for brukeren å orientere dem. Jeg er sikker på at du har alle kjøre programmer der plutselig det krasjer, og du får dette latterlig lite dialog som dukker opp og sier noe forferdelig kryptisk og kanskje gir deg en feilkode eller noe sånt som gir ingen mening. Det er der du virkelig ønsker å gi noe nyttig og målrettet for brukeren, slik at når de kjører den de går "Å," ansikt håndflaten. "Jeg vet nøyaktig hva de skal gjøre. Jeg vet hvordan å fikse dette." 

Hvis du ikke skriver ut en melding, så du ender opp med faktisk la brukeren til å gå undersøke kildekoden å finne ut hva som gikk galt. Det er også noen ganger at du kommer til å bruke forskjellige feilkoder. Her har vi bare brukt en for å si det var en feil, Det oppstod en feil, det var en feil. Større programmer, ofte programmer som kalles av andre programmer, vil returnere en slags spesielle feilkoder i ulike scenarier programmatisk kommunisere hva du ellers ville bare bruke en fin engelsk melding for. Cool. Ettersom vi arbeider ned, kan du se at vi trekker nøkkelen ut. Vi tester for å se om nøkkelen passer. Vi får en melding fra brukeren. Grunnen til at vi gjør det i denne gjøre mens loop-og dette er noe som vi vil dekke i en liten bit-men det viser seg at hvis du skriver kontroll D når du får den GetString ledetekst på terminalen hva som faktisk gjør er det sender et spesialtegn til programmet. Det kalles ELF eller slutten av filen karakter. Og i så fall, vil vårt budskap streng være null, så dette var ikke noe vi sjekket for i problemet satt seg. 

Men som vi går på, nå som vi har begynt å snakke om pekere og dynamisk minne allokering på haugen, sjekker for null når du har en funksjon som kanskje returnere null som verdi er noe som du ønsker å komme i vane å gjøre. Dette er her først og fremst for illustrasjon. Men når du ser GetString i fremtiden, så fra oppgavesettet 4 på, vil du ønsker å holde dette i bakhodet. Igjen, dette er ikke et problem for Problem sett 3 enten siden vi ikke hadde dekket det ennå. Til slutt får vi til denne delen hvor vi kommer til det viktigste kryptering loop, og det er et par ting som skjer her. Først iterere vi over hele meldingen strengen selv. Her har vi holdt strlen samtale i tilstanden, der en rekke av dere har påpekt er ikke en fin måte å gå. Det viser seg i dette tilfellet er det heller ikke stor, delvis fordi vi endrer innholdet i selve meldingen inne for loop, slik at hvis vi har en melding som er 10 tegn lang, første gang vi starter som for loop strlen vil returnere hva? 10. 

Men hvis vi deretter endre meldingen, sier vi endre sin femte karakter, og vi kaster i en \ 0 karakter i femte posisjon, på en påfølgende iterasjon strlen (melding) vil ikke returnere hva den gjorde den aller første gangen vi iterated, men det vil i stedet gå tilbake 5 fordi vi kastet i at null terminator, og strengens lengde er definert av stillingen at \ 0. I dette tilfellet, er dette en fin måte å gå fordi vi endre det på plass. Men du merker at dette er faktisk overraskende enkelt å kryptere hvis du kan få regnestykket riktig. Alt som kreves er å sjekke hvorvidt brevet som du ser på er store eller små bokstaver. 

Grunnen til at vi bare nødt til å se etter det, og vi trenger ikke å se etter det er alfa saken er fordi Hvis et tegn er store eller om det er små så er det definitivt en bokstav, fordi vi ikke har store og små sifre. Den andre tingen vi gjør, og dette er litt kinkig- er vi har endret standard Caesar cipher formel at vi ga i oppgavesettet spesifikasjonen. Hva er annerledes her er at vi trekkes i store saken hovedstaden A, og så la vi til hovedstaden A tilbake på slutten. 

Jeg vet at noen av dere gjort dette i koden. Visste noen av dere gjør dette i innleveringer? Du gjorde dette. Kan du forklare hva dette betyr, Sahb? Ved å trekke den ut, fordi du gjorde en mod rett etter det, du må ta den ut, slik at måten du får [hoste] posisjon. Og så ved å legge det tilbake senere flyttet deg over den du ønsket. Ja, akkurat. Hva Sahb sa var at når vi ønsker å legge til vårt budskap og vår nøkkel sammen og deretter mod at mod at ved NUM_LETTERS, hvis vi ikke skalere vårt budskap i riktig 0-25 utvalg først, så vi kan ende opp med å få en veldig merkelig nummer fordi de verdier som vi ser på når vi ser på meldingen [i], når vi ser på den i. karakter av vår vanlig tekstmelding, er en verdi et sted i dette 65-122 rekkevidde basert på de verdier for ASCII store A gjennom små z. Og så når vi mod det med 26 eller NUM_LETTERS, siden det var vår # define øverst til høyre opp her, som kommer til å gi oss en verdi som er i 0-25 rekkevidde, og vi trenger en måte å deretter skalere det tilbake opp og få det inn i riktig ASCII-området. Den enkleste måten å gjøre det på er å bare skalere alt ned inn 0-25 rekkevidde til å begynne med, og deretter skifte alt tilbake opp på slutten. 

En annen vanlig feil som jeg så folk kjører inn er at hvis du ikke faktisk gjør dette skalering med en gang og du legger og tast sammen, og du legger dem, sier, inn i en char variabel, problemet med det er siden meldingen [i] er et relativt stort antall til å begynne med- husk det er minst 65 hvis det er en stor bokstav- hvis du har en stor nøkkel, si, noe som 100, og du legger dem to sammen til en signert røye du kommer til å få en overflow. Du kommer til å få en verdi som er større enn 127, som er den største verdien som en char variabel kan holde. Igjen, det er derfor du ønsker å gjøre den slags ting til å begynne med. Noen mennesker fikk rundt så fall ved å gjøre en if else og testing for å se om det ville overflyt før du gjør det, men på denne måten får rundt det. Og så i denne løsningen skrives vi ut hele strengen helt på slutten. Andra skrives ut et tegn om gangen. Begge er kjempebra. På dette punktet, gjør dere har noen spørsmål, noen kommentarer om dette? Ting du liker, ting du ikke liker? 

Jeg hadde et spørsmål. Kanskje jeg savnet det under din forklaring, men hvordan fungerer dette programmet hoppe mellomrommene for tilkobling nøkkelen til lengden av teksten? Dette er bare Caesar cipher. >> Å, unnskyld, ja. Ja, vi får se det. I Caesar cipher fikk vi rundt det fordi vi bare venda tegn. Vi bare rotert dem hvis de var store eller små bokstaver. Dere følelsen ganske godt om dette? Føl deg fri til å kopiere dette hjemme, ta den, sammenligne det med hva dere skrev. Definitivt gjerne sende spørsmål om det også. Og igjen, innser at målet her med problemet ditt setter er ikke å få dere til å skrive kode som er perfekt for dine oppgavesett. Det er en lærerik opplevelse. Ja. 

Tilbake til gjøre mens loop, hvis det tilsvarer null, så null betyr bare ingenting, de bare trykk enter? Null er en spesiell pekeren verdi, og vi bruker null når vi ønsker å si Vi har en peker variabel som peker til ingenting. Og så typisk det betyr at denne variabelen, denne meldingen variabel er tom, og her, fordi vi bruker CS50 spesiell streng type, hva er den CS50 streng type? Har du sett hva det er når David trukket tilbake hette i forelesningen? Det er en funky-det er en peker, ikke sant? Ok, ja. >> Det er en char *. Og så egentlig vi kunne erstatte dette her med char * melding, og så GetString funksjon, hvis det ikke får hell en streng fra brukeren, det kan ikke analysere en streng, og det ene tilfellet der det ikke kan analysere en streng er hvis brukeren skriver slutten av filen karakter, kontroll D, som ikke er noe du vanligvis gjør, men hvis det skjer deretter funksjonen vil returnere denne nullverdi som en måte å si "Hei, jeg fikk ikke en streng." Hva ville skje hvis vi ikke setter melding = null, som er noe som vi ikke har gjort ennå? Hvorfor skulle det være et problem her? Fordi jeg vet at vi snakket litt i foredrag om minnelekkasjer. Ja, la oss gjøre det, og la oss se hva som skjer. 

Basil spørsmålet var hva som skjer hvis vi ikke egentlig har denne meldingen = null test? La oss rulle opp til toppen. Dere kan kommentere dette. Egentlig vil jeg lagre den i en revisjon. Dette vil være Revisjon 3. Hva du må gjøre for å kjøre dette programmet er at du må trykke på denne tannhjulikonet her oppe, og du må legge til et argument til det. Du må gi den sentralt argument siden vi ønsker å passere i en kommandolinje argument. Her jeg kommer til å gi det nummer tre. Jeg liker 3. Nå zoome ut igjen, kjører programmet. Det kjører, kompilering, bygge. Here we go. Det venter på å bli spurt. Hvis jeg skriver inn noe sånt som hello-hvor ble det gå? Oh, tok mitt program for lang tid å kjøre. Jeg var jawing for lenge. Her går. Nå jeg skriver i hallo. Vi ser at det krypterer riktig. Nå hva skjer hvis vi gjør rask GetString å returnere null? Husk, jeg sa at vi gjorde det ved å trykke kontroll D samtidig. Jeg skal bla opp her. Vi vil kjøre den på nytt. Building. Der går. Nå når jeg treffer kontroll D Jeg fikk denne linjen som sier opt/sandbox50/bin/run.sh, Segmentation fault. Har dere sett det før? 

[Student] Hvorfor er det ingen >> Beklager? [Student] Hvorfor er det ingen kjerne dump i dette tilfellet? Kjernen dump er-spørsmålet er hvorfor er det ingen kjerne dump her? Spørsmålet er at det kan være, men kjernen dump er en fil som blir lagret på harddisken. I dette tilfellet har vi deaktivert kjerne dumper på flukt serveren slik at vi ikke har folk SEG forkastninger og bygge opp tonnevis av kjernen dumper. Men du kan få en. Kjerne dumper er den slags ting som du ofte kan deaktivere, og noen ganger du gjør. Segmentering skyld, for å svare på spørsmålet ditt, Basil, sier at vi prøvde å få tilgang til en peker som ikke ble satt til å peke på noe. Husk Binky i videoen når Binky forsøker å gå tilgang til en peker som ikke er peker til noe? I dette tilfellet antar jeg teknisk pekeren peker til noe. Den peker til null, som er teknisk 0, men som er definert til å være i et segment som ikke er tilgjengelig ved programmet, slik at du får en segmentering feil fordi du ikke tilgang minne som er i en gyldig segment som heap linjestykke eller stakksegmentet eller data segmentet. Cool. Eventuelle flere spørsmål om Caesar? 

La oss gå videre. La oss se på revisjon 2 veldig raskt. Det er Vigenère. Her i Vigenère vi vil gå gjennom dette ganske raskt fordi, igjen, Vigenère og Caesar er ganske lik. Header kommentar er før, # Define er før å unngå å bruke disse magiske tallene. Det fine er si at vi ønsket å flytte til et annet alfabet eller noe sånt. Snarere enn å måtte gå manuelt endre alle de 26-tallet i koden vi kan endre dette til 27 eller slippe den ned hvis vi bruker forskjellige alfabeter, ulike språk. Igjen har vi denne kontrollen av argumentet teller, og virkelig du kan nesten ta dette som en mal. Ganske mye hvert program du skriver bør ha- hvis det tar kommandolinjeargumenter-noen sekvens av linjer som lyder slik helt i begynnelsen. Det er en av de første mental helse testene du ønsker å gjøre. 

Her er hva vi gjorde var vi sørget for at søkeordet var gyldig, og det var den andre sjekken som vi gjorde. Legg merke igjen at vi skilte dette fra argc og 2. Vær oppmerksom på at i dette tilfellet en ting som vi måtte gjøre var stedet for å bruke en til I ønsket vi å validere hele strengen, og for å gjøre det du faktisk må gå tegn for tegn over strengen. Det er ingen god måte å kalle noe på det fordi selv, for eksempel, en til i. kommer tilbake 0 hvis det ikke kan analysere et heltall, slik at ikke engang fungerer. Igjen, hyggelig melding som forteller brukeren nøyaktig hva som skjedde. Så her igjen, vi også håndtere saken der brukeren skriver i en kontroll D tilfeldig karakter. 

Og så Charlotte hadde et spørsmål tidligere om hvordan vi klarer å hoppe over områder i vårt bånd her. Dette var slags ligner på hva vi gjorde med Myspace program som vi gjorde i avsnitt, og måten dette arbeidet er at vi spores antall bokstaver som vi hadde sett. Så vi gikk over meldingen streng, som vi gikk over tegn for tegn, vi spores indeksen som en del av vår for loop, og deretter vi også spores antall bokstaver, slik at ikke-spesialtegn, ikke-sifre, ikke-mellomrommet at vi hadde sett i egen variabel. Og så denne løsningen endrer nøkkelen å få en virkelig nøkkel heltall, og det gjør det på sparket, rett før det går så å kryptere selve meldingen karakter. Det er noen løsninger som var perfekt stor for som ville endre nøkkelen opp ved testing for nøkkelen gyldighet. I tillegg til å sørge for at karakter og søkeordet ble en bokstav det også viste at til et heltall i 0-25 rekkevidde for deretter hoppe å gjøre det senere i dette for loop. Igjen, ser du her dette er virkelig nøyaktig samme kode som vi brukte i Caesar på dette punktet. Du gjør akkurat det samme, slik at den virkelige kunsten er å finne ut hvordan du slår inn søkeordet i et heltall. 

En ting som vi gjorde her som er litt tett er vi gjentok denne setningen, jeg antar du kan kalle det, 3 separate ganger på 58 linjer, 59, og 61. Kan noen forklare hva denne setningen betyr? Det er tilgang til en karakter, som du sa. Ja, det er [uhørbart] et tegn i søkeordet, og så er det antall bokstaver sett fordi du bare beveger seg langs søkeordet når du har sett brevet, så det kommer til å effektivt hoppe mellomrom og sånt. Ja, akkurat. Og når du har sett søkeordet blank du bare mod så du flytter tilbake rundt. Akkurat. Det er en perfekt forklaring. Hva Kevin sa er at vi ønsker å indeksere inn søkeordet. Vi ønsker å få num_letters_seen karakter, om du vil, men hvis num_letters_seen overstiger lengden på søkeordet, måten vi kommer tilbake i riktig område er vi bruker mod operatør å effektivt vikle rundt. For eksempel, som i korte, er vår nøkkelord bacon, og det er 5 bokstaver. Men vi har sett 6 bokstaver i vår ren tekst på dette punktet og kryptert 6. Vi vil ende opp tilgang til num_letters_seen, som er 6, mod lengden søkeordet, 5, og så vi får en, og så hva vi vil gjøre er at vi vil tilgang til første tegnet på innsiden av søkeordet vår på det tidspunktet. 

Greit, noen spørsmål om Vigenère før vi går videre? Dere følelsen ganske godt om dette? Cool, flott. Jeg vil være sikker på at dere får sjansen til å se kode at vi synes ser bra ut og har sjansen til å lære av det. Dette kommer til å bli det siste vi skal bruke mellomrom for tiden, og vi kommer til å overgangen nå, og jeg kommer til å gå til cs50.net/lectures slik at vi kan gjøre en liten bit av quiz gjennomgang. Den beste måten jeg tror å begynne å gjøre quiz anmeldelsen er å komme til denne Forelesninger siden, cs50.net/lectures, og under hver av uken overskrifter, så hvis jeg ser her i uke 0, Jeg ser at vi har en liste over emner som vi dekket i uke 0. 

Hvis noen av disse emnene virke uvant for deg vil du definitivt ønsker å gå tilbake og skure forelesningsnotater og muligens selv skumme gjennom forelesninger, se dem igjen hvis du vil å få en følelse for hva som skjer med hvert av disse emnene. Jeg vil si i tillegg i år en av de kule ressursene vi har fått er disse shorts som vi har laget, og hvis du ser på uke 0, Vi har ikke alle av temaene, men vi har ganske mange av dem, noen av de vanskeligere seg, så ser disse shorts igjen er en god måte å få deg opp til hastighet. Spesielt, jeg kommer til å sette i en plugg for 3 på bunnen, siden jeg gjorde de. Men hvis du sliter med binære, biter, hex, den slags ting, binær er et flott sted å starte. ASCII er en annen som er godt å se også. Du kan selv se meg på 1,5 x hastighet hvis jeg går for tregt for deg. Siden det er gjennomgang, gjerne gjøre det. 

Bare for å starte veldig raskt, vi kommer til å gå gjennom et par av disse quiz problemer bare for å raskt churn gjennom disse. For eksempel, la oss se på problemet 16 som jeg har rett her oppe på brettet. Vi har fått denne følgende beregning i binær, og vi ønsker å vise noe arbeid. Ok, jeg kommer til å gi dette en sjanse. Dere bør følge med papir, og vi vil gjøre dette veldig raskt. Vi ønsker å utføre følgende beregning i binær. Jeg har 00110010. Og jeg kommer til å legge til det 00110010. For matematikk genier følgende sammen hjemme, Dette er effektivt multiplisere med 2. La oss starte. Vi kommer til å følge samme tillegg algoritme som vi gjør når vi legger desimaltall sammen. Egentlig den eneste forskjellen her er at vi sløyfe tilbake rundt når vi har 1 + 1 i stedet for når vi kommer til 10 år. 

Hvis vi starter fra høyre, veldig raskt, er det det første sifferet? [Student] 0. >> [Nate H.] 0. Stor, det andre sifferet? [Student] 1. [Nate H.] Er det en 1? 1 + 1 er? [Student] 10. [Nate H.] Akkurat, så hva er siffer som jeg skriver rett under 2 de legges sammen? [Student] 1, 0 eller 0 og deretter bære en. [Nate H.] 0 og bære en 1, akkurat. Neste opp, Basil, nå er du. Hva er den tredje? >> [Basil] 1. [Nate H.] 1, perfekt. Kevin? [Kevin] 0. >> [Nate H.] 0, Charlotte? [Charlotte] 0. >> [Nate H.] Ja, og hva gjør jeg? [Student] The 1. [Nate H.] Og hva gjør jeg? Og da jeg bære en. Perfekt, Sahb? >> [Sahb] Nå har du en. [Nate H.] Og gjør jeg noe her? [Sahb] Så for den neste du har en fordi du gjennomført over 1. [Nate H.] Flott, så her kan vi fullføre den. Cool. [Student] Har 0 + 0 = 0? 0 + 0 = 0. 1 + 1, som du sa, er 10, eller 1, 0, heller. 10 er en misvisende benevnelse fordi for meg 10 betyr tallet 10, og det er innfall av hvordan vi representerer det når vi skriver det. Vi representerer tallet 2 med 1, 0, og nummer 10 er noe forskjellig. 

Hva er slags fint om binære er at det egentlig ikke er så mange tilfeller du trenger å lære. Det finnes 0 + 0 = 0, 0 + 1 = 1, 1 + 1 er 0, og deretter bære en 1, og så kan du se her på den tredje kolonnen fra høyre Vi hadde denne 1, 1 og 1. Og 1 + 1 + 1 er en 1, og du bære en annen en. Når du gjør binære tillegg, ganske enkelt. Jeg vil gjøre et par mer av disse forstanden sjekk dere før du går i, fordi dette er sannsynligvis noe vi får se på quiz. Nå la oss gjøre dette neste også. La oss gjøre problem 17. Vi kommer til å konvertere følgende binære tall til desimal. Jeg har 10100111001. Husk i det binære video som jeg gjorde Jeg gikk gjennom et par eksempler, og jeg viste hvordan alt fungerer når du gjør det i desimal. Når du arbeider i desimalfremstilling Jeg tror vi på dette punktet i våre liv så flytende i det som det er ganske lett å glatte over mekanikken i hvordan det faktisk fungerer. 

Men for å gjøre en rask oppsummering, hvis jeg har nummer 137 Dette betyr-og virkelig igjen, dette er i desimalfremstilling- tallet 137 i desimal betyr at jeg har 1 x 100 + 3 x 10 + 7 x 1. Dette er alle bor på skjermen. Og så hvis du ser på disse tallene her, 100, 10 og 1, ser du at de er faktisk alle krefter 10. Jeg har 10 ², 10 ¹, og 10 til null. Vi har en lignende slags ting i binær, bortsett fra at vår base, som vi kaller det, er 2 i stedet for 10 år. Disse 10s som jeg skrev ned her nederst, denne 10 ², 10 ¹, 10 til null, 10 er vår base, og eksponent, 0 1,, eller 2, er underforstått av posisjonen sifferet i antall at vi skriver. 1, hvis vi ser på det, er dette en i andre posisjon. Den 3 er i første posisjon, og 7 er i den 0th stilling. Det er slik vi får de ulike eksponentene nedenfor for våre baser. 

Etter alt dette we'll-faktisk, vet du hva? Vi vil gjøre-der gjorde min angre knapp gå? Der går. Jeg elsker denne angre ting. Etter dette tror jeg for meg minst den enkleste måten å begynne å konvertere et binært tall eller et heksadesimalt tall der basen er 16 og ikke 10 eller 2 er å gå videre og skrive ut baser og eksponenter for alle tallene i mitt binært tall på toppen. Hvis vi begynner fra venstre til høyre igjen, som er slags counterintuitive, Jeg kommer til å endre tilbake til svart her, har vi to til 0. posisjon, og da har vi to ¹, 2 ², og deretter 2 til 3, 2 til 4, 2 til 5, 6, 7, 8, 9, og 10. Disse tallene jeg har skrevet ut er alle eksponenter. Jeg bare skrev baser her i de første 3 bare for plass. 

På dette punktet kommer jeg til å gå videre, og jeg faktisk kommer til å slette ting som vi gjorde i desimal, hvis det er greit. Dere har alle fått det. De av dere ser på nettet er jeg sikker på vil være i stand til å spole tilbake meg hvis du vil. Bytte tilbake til pennen. Nå, hva vi kan gjøre-hvis dere ikke er helt opp til hastigheten på kreftene dine på 2, det er helt kult. Det skjer. Jeg forstår. Jeg hadde en gang en jobb intervju der jeg ble fortalt jeg burde vite alle krefter 2 opp gjennom 2 til den 30.. Det var ikke en jobb jeg fikk. Uansett, kan dere gå videre og gjøre regnestykket her, men med binære ikke det gjør virkelig fornuftig, og heller ikke det fornuftig med desimal eller heksadesimal heller, å gjøre regnestykket ut hvor du har nuller. Du kan se jeg har 0 her, en 0 her, 0 her, 0 her, 0 her, 0 her. Hvorfor kan det ikke være fornuftig å gjøre selve regnestykket å beregne den aktuelle strøm av 2 for den posisjonen? Akkurat som Charlotte sa, vil det være 0. Kan like godt spare deg selv tid hvis beregning krefter 2 er ikke din sterke side. I dette tilfellet trenger vi bare å beregne det for 2 til 0 som er-? [Student] 1. [Nate H.] 1, 2 til 3, som er-? [Student] 8. >> [Nate H.] 8. 2 til 4? [Student] 2. Jeg beklager, 1. [Nate H.] 2 til 4 er 16, akkurat. 2 til 5, Kevin? >> 32. [Nate H.] 32, 2 til 8? [Student] 32 x 8, 256. [Nate H.] Perfect. Og 2 til 10? [Student] 1024. [Nate H.] Yeah, 1024. 

Når vi har fått disse tallene kan vi oppsummere dem alle opp. Og det er her det er veldig viktig å gjøre et par ting. En er å gå sakte og kontrollere arbeidet. Du kan fortelle at det er en 1 på slutten av dette antallet, så jeg skal definitivt få et oddetall som følge min, fordi alle de andre som kommer til å bli enda tall gitt at det er et binært tall. Den andre tingen å gjøre er hvis du kommer til dette punktet på testen og du har skrevet det ut så langt og du kjører ut av tiden se på antall poeng at dette problemet er verdt. Dette problemet, som du kan se-hvis jeg vende tilbake til min laptop veldig raskt- dette problemet er verdt 2 poeng, så dette er ikke den slags tillegg du bør gå gjennom hvis du virkelig presset for tiden. Men vi vil bytte tilbake til iPad, og vi vil gå gjennom det veldig raskt. 

Jeg liker å gjøre de små tallene første fordi jeg finner det lettere. Jeg liker 32 og 8 fordi de går sammen ganske lett, og får vi 50. 16 og en får 17. Det får vi 57, og da kan vi gjøre resten av denne, slik at vi kan gjøre 57, 156. Kom igjen. Mann, vel, la oss se. Vi hadde 57, 256, og 1024. På dette punktet, vil jeg heller bare gå gjennom. Jeg har ingen anelse. Jeg trenger helt klart å lese meg opp på dette. 7, 6 og 4, får du 17. 1, 5, 5, 2, 13. Så får vi 3, og så får vi en. 1337. Easter egg, noen? Noen kjenner dette nummeret? Chris gjenkjenner nummeret. Hva betyr det, Chris? [Chris] Leet. Leet, så hvis du ser på dette, ser det ut som leet. Hacker ting. Se opp for den slags ting på midterm eller quiz, heller. Hvis du ser den slags ting, og du lurer på "Huh," som kan faktisk bety noe. Jeg vet ikke. David liker å sette det i. Det er en god måte å forstanden sjekke det. Som greit, jeg kan se hva som skjer. 

Det er Week 0/uke en ting. Hvis vi går tilbake til våre bærbare nå, zoome ut, og et par andre ting. Det er ASCII, som vi har gjort mye med problemet sett. Denne oppfatningen av kapital A. Hva er det egentlig? Å vite det er Desimalheltallet. 65 er hva det er kartlagt til i ASCII-tabellen, og det er derfor hvordan datamaskinen skriver det, og det er hvordan vi har fått unna med faktisk skriver tegnet kapital A og tegnet små bokstaver a i noen av disse løsningene og øvingsoppgaver som du har gjort. Et par andre ting. Vi har uttalelser, boolske uttrykk, betingelser, løkker, variabler og tråder. 

De alle synes å være fornuftig for det meste? Noe av dette terminologi er litt funky til tider. Jeg liker å tenke på en uttalelse som for det meste noe som ender med et semikolon. Utsagn som x = 7, som setter en variabel, antagelig kalt x = 7. Antagelig x er også en type som kan lagre nummeret 7, så det er en int eller muligens en flåte eller en kort eller en røye, noe sånt. En boolsk uttrykk bruker disse dobbeltsidige lik og bang lik eller ikke lik, mindre enn, større enn, mindre enn eller lik, alle den slags ting. Forholdene så er hvis annet uttalelser. Jeg ville huske at du ikke kan ha en annen uten en tilsvarende hvis. På samme måte kan du ikke ha en else if uten en tilsvarende hvis. Looper, husker de tre typer loops vi har hammering inn i deg for de siste par seksjoner og øvingsoppgaver. Bruke gjøre mens når du får brukerundersøkelser, bruke mens looper før en bestemt betingelse er sann, og deretter bruke dem for løkker hvis du trenger å vet hvilken iterasjon av loopen du befinner deg på er hvordan jeg tenker på det. Eller hvis du gjør en for hvert tegn i en streng jeg ønsker å gjøre noe, for hvert element i en matrise jeg ønsker å gjøre noe til dette elementet. 

Tråder og hendelser. Disse har vi ikke dekket så eksplisitt i C, men husk dette fra bunnen av. Dette er ideen om å ha forskjellige skript. Dette er også denne oppfatningen av kringkasting en hendelse. Noen mennesker ikke bruke kringkasting i sine prosjekter i utgangspunktet, som er helt kult, men disse er to forskjellige måter å håndtere dette større problem kalt samtidighet, som er hvordan får du programmer for å utføre eller tilsynelatende utføre samtidig? Forskjellige oppgaver som kjører mens andre oppgaver også kjører. Dette er hvordan operativsystemet ser ut til å fungere. Dette er grunnen til at selv om, for eksempel, Jeg har fått min nettleser som kjører, kan jeg også slå på Spotify og spiller en sang. Det er mer av en konseptuell ting å forstå. Jeg ville ta en titt på trådene korte Hvis du ønsker å lære mer om det. 

La oss se, tror jeg det kan ha vært et problem på dette i en av disse. Igjen, jeg tror tråder og hendelser ikke noe som vi vil dekke i C bare fordi det er betydelig vanskeligere enn i Scratch. Du bør ikke bekymre deg for det der, men definitivt forstå begrepene, forstå hva som skjer. Før vi går videre, noen spørsmål om Week 0 materiale? Alle følelsen ganske bra? Forstå variabler og hva en variabel er? 

Flytte på. Uke 1. Et par ting her som ikke var spesielt dekket i quiz gjennomgang nødvendigvis og også er mer konseptuelle ting å tenke på. Den første er dette oppfatningen av hva kildekode, kompilatorer og objekt kode er. Noen? Basilikum. Er objektkode-Jeg mener kildekoden er hva du putter i clang, og objektkode er hva clang legger ut slik at datamaskinen kan lese programmet. Akkurat. Kildekode er C-kode som du faktisk skriver opp. Objektkode er hva du får ut av klang. Det er 0'er og 1'ere i at binært format. Hva skjer da er når du har en haug med objekt-filer, si at du kompilere et prosjekt eller et program som bruker flere kildekodefiler, som etter konvensjonen får. c filtypen. Det er derfor vi har caesar.c, vigenère.c. Hvis du skriver Java-programmer du gir dem utvidelsen. Java. Python-programmer har filtypen. Py ofte. 

Når du har flere. C-filer, kompilere du dem. Clang spytter ut alt dette binære useriøs. Deretter fordi du bare vil ha 1 program du har linker lenken alle disse objekt filer sammen i en kjørbar fil. Dette er også hva som skjer når du bruker CS50 biblioteket, for eksempel. Den CS50 biblioteket er både det. H header-fil at du leser, at # includecs50.h. Og da er det også en spesiell binær bibliotekfil som er blitt utarbeidet som er 0'er og 1'ere, og at-l flagget, så hvis vi går tilbake til våre Spaces, og vi ser veldig raskt på hva som skjer her når vi ser på vår clang kommando, hva vi har fått er at dette er vår kildekoden filen her. Dette er en haug med kompilatoren flagg. Og så helt til slutt, disse-l flagg koblingen i de faktiske binære filer for disse to bibliotekene, CS50 bibliotek og deretter regnestykket bibliotek. 

Forstå hver type filer "Formålet i innsamlingsprosessen er noe du ønsker å være i stand til å gi minst et høyt nivå oversikt. Kildekode kommer inn Object koden kommer ut. Objekt kodefiler knytte sammen, og du får en vakker, kjørbar fil. Cool. Det er også her du kan få feil på flere punkter i innsamlingsprosessen. Det er der, for eksempel, hvis du tar ut denne tilknytningen flagg, den CS50 flagg, og du utelater det i Spaces, eller når du kjører koden, Dette er hvor du vil få en feilmelding i å knytte fase, og linker vil si: "Hei, kalte deg en funksjon GetString som er i CS50 bibliotek. " "Du fortalte meg at det var i CS50 biblioteket, og jeg kan ikke finne koden for det." Det er der du må koble den inn, og som er atskilt fra en kompilator feil fordi kompilatoren ser på syntaks og den slags ting. Det er godt å vite hva som skjer når. 

Andre ting å vite om. Jeg vil si at du definitivt ønsker å ta en titt på den korte på typecasting gjort av Jordan å forstå hva ints er under panseret, hva chars er under panseret. Når vi snakker om ASCII, og vi faktisk ser på ASCII-tabellen, hva som gjør er å gi oss en under panseret utseende på hvordan datamaskinen faktisk representerer kapital A og tallet 7 og et komma og et spørsmålstegn. Datamaskinen har også spesielle måter å representere tallet 7 som et heltall. Den har en spesiell måte å representere nummer 7 som et flyttall, og de er svært forskjellige. Typecasting er hvordan du fortelle datamaskinen "Hei, jeg vil at du skal konvertere fra en representasjon til en annen representasjon. " Hvorfor ikke vi ta en titt på det. 

Jeg vil også ta en titt på den korte på biblioteker og kort på kompilatorer. De snakker om prosessen med samling, hva et bibliotek er, og gå over noen av disse spørsmålene som du kan få spurt. Spørsmål om Week 1-materiale? Er det noen emner her inne som synes skremmende du ønsker å dekke? Jeg prøver å blåse gjennom det meste av disse tidligere emner, slik at vi kan få til pekere og gjøre en liten bit av rekursjon. Tanker? Noe å dekke? Tid for litt sjokolade kanskje? Dere jobber gjennom den. Jeg kommer til å holde sipping på min kaffe. Uke 2. God samtale, god samtale. I uke 2 snakket vi litt mer om funksjoner. 

I de første oppgavesett vi ikke egentlig skrive noen funksjoner i det hele tatt annet enn hvilken funksjon? [Student] Main. >> Main, akkurat. Og så har vi sett de forskjellige kostymer som viktigste slites. Det er en der det tar ingen argumenter, og vi bare si tomrom i mellom parentesene, og så er det den andre der vi ønsker å ta kommandolinjeargumenter, og som vi så, det er der du har int argc og streng argv rekke eller nå som vi faktisk har utsatt streng til å være den char * at det er vi kommer til å begynne å skrive det som char * argv og deretter parentes. I Problem Set 3, så dere en haug av funksjoner, og du implementert en haug av funksjoner, tegne, se opp, krafse. Prototypene ble alle skrevet der for deg. 

Det jeg ønsket å snakke om her med funksjoner veldig raskt er at det er 3 deler til dem når du skriver en funksjon. Du må angi avkastning type funksjonen. Du må angi et navn for funksjonen, og deretter må du angi argumentlisten eller parameterlisten. For eksempel, hvis jeg skulle skrive en funksjon for å oppsummere en haug av heltall og deretter gå tilbake til meg summen hva som ville være min retur-type hvis jeg ønsket å summere heltall og deretter returnere summen? Deretter navnet på funksjonen. Hvis jeg går videre og skrive i grønt, er denne delen returtypen. Denne delen er navnet. Og deretter i parentes er der jeg gi argumenter, ofte forkortet til args, noen ganger kalt params for parametere. Og hvis du har en, du bare angi ett. Hvis du har flere du skille hver enkelt med komma. Og for hvert argument gi deg det 2 ting som er-Kevin? [Kevin] Du må gi typen og så navnet. Og så navnet, og navnet er navnet som du kommer til å bruke å henvise til at argumentet innenfor summen funksjonen, i funksjonen som du nå skriver. 

Du trenger ikke å, for eksempel, hvis jeg kommer til å oppsummere, si, en rekke heltall-vi gjør int array, og jeg skal gi meg selv noen klammeparentes der- så når jeg passerer en matrise til summen funksjon Jeg passerer det i første posisjon av argumentet listen. Men tabellen som jeg passerer i ikke å ha navnet arr. Arr kommer til å være hvordan jeg refererer til som argument i kroppen av funksjonen. Den andre tingen som vi må ta hensyn til, og dette er litt forskjellig fra funksjoner, men jeg tror det er et viktig poeng, er at i C når jeg skriver en funksjon som dette hvordan vet jeg hvor mange elementer er i denne tabellen? Dette er noe av et lurespørsmål. Vi snakket om dette litt i forrige ukes delen. Hvordan vet jeg hvor mange elementer inne en rekke i C? Er det en måte? 

Det viser seg at det er ingen måte å vite. Du må passere det separat. Det er et triks som du kan gjøre hvis du er i samme funksjon som matrisen har blitt erklært, og du arbeider med en stabel array. Men det fungerer bare hvis du er i samme funksjon. Når du passerer en matrise til en annen funksjon, eller hvis du har erklært en rekke og du setter denne matrisen på haugen, har du brukt malloc  og den slags ting, er alle spill av. Da har du faktisk nødt til å passere rundt en spesiell argument eller en annen parameter forteller deg hvor stor matrise er. I dette tilfellet ønsker jeg å bruke komma-Jeg beklager, det kommer ut av skjermen her- og jeg vil passere i et annet argument  og kaller det int len ​​for lengden. 

En ting som kan komme opp på quiz ber deg om å skrive eller gjennomføre en bestemt funksjon som heter noe. Hvis vi ikke gi deg prototypen, så dette hele greia her, hele denne rotet kalles funksjonen erklæringen eller funksjonen prototype, dette er en av de første tingene som du ønsker å spikre ned hvis det ikke er gitt til deg med en gang på quiz. Den andre triks jeg har lært er at sier vi gjør gir deg en prototype for en funksjon, og vi sier: "Hei, har du til å skrive det." Inne i klammeparentes som du har på quiz Hvis du oppdager at det er en avkastning type og merke deg at avkastningen typen er noe annet enn tomrom, noe som betyr at funksjonen ikke returnerer noe, så en ting du definitivt ønsker å gjøre er å skrive en slags retur uttalelse på slutten av funksjonen. Retur, og i dette tilfellet, vil vi sette inn en tom fordi vi ønsker å fylle inn de tomme. Men dette får du tenke på riktig måte om hvordan jeg kommer til å nærme seg dette problemet? Og det minner deg om du er nødt til å returnere en verdi til den som ringer til funksjonen. 

Ja. >> [Student] Gjelder stil når vi skriver kode på quiz? Som innrykk og den slags ting? >> [Student] Yeah. Nei, ikke så mye. Jeg tror mye av-dette er noe vi vil avklare på quiz på dagen av, men typisk bekymre omfatter # og den slags ting, er det slags utenfor. [Student] Trenger du å kommentere en håndskrevet koden? Trenger du å kommentere en håndskrevet koden? Kommenterer alltid bra hvis du er bekymret for delvis kreditt eller du ønsker å kommunisere din hensikt til grader. Men jeg, igjen, vil avklare om quiz seg selv og på quiz dagen, men jeg tror ikke at du vil bli bedt om å skrive kommentarer, nei. Vanligvis ikke, men det er definitivt den slags ting der du kan kommunisere din intensjon, som "Hei, dette er hvor jeg skal med det." Og noen ganger som kan hjelpe med delvis kreditt. Cool. 

Basilikum. [Basil] Hva er forskjellen mellom å erklære, sier int lang i argumentene eller parametere versus erklære en variabel i funksjonen? Wow, gikk kaffe ned i luftrøret. [Basil] Like hvilke ting vi ønsker å sette i argumenter. Ja, det er et stort spørsmål. Hvordan velger du hvilke ting du ønsker å sette i argumentene i motsetning til hva du bør gjøre innsiden av funksjon? I dette tilfellet har vi inkludert begge disse som argumenter fordi de er noe som den som kommer til å bruke summen funksjonen må spesifisere disse tingene. 

Summen funksjonen, som vi snakket om, har ingen måte å vite hvor stor matrise er det blir fra sin ringer eller den som bruker summen funksjonen. Det har ingen måte å vite hvor stor denne matrisen er. Grunnen til at vi passerer i denne lengden her som et argument er fordi det er noe som vi i utgangspunktet forteller innringeren av funksjonen, den som kommer til å bruke summen funksjon "Hei, ikke bare du må gi oss en rekke av ints, du må også fortelle oss hvor stor tabellen som du har gitt oss er. " [Basil] De vil begge være kommandolinjeargumenter? Nei, dette er faktisk argumenter som du ville passere til funksjonen. 

La meg gjøre en ny side her. [Basil] Som navnet skulle passere- [Nate H.] Hvis jeg har int main (void), og jeg kommer til å sette i min return 0 her nede på bunnen, og si jeg vil kalle summen funksjonen. Jeg ønsker å si int x = sum (); Å bruke summen funksjon jeg har til å passere både i matrisen som jeg ønsker å oppsummere og lengden av tabellen, så dette er hvor antar jeg hadde en rekke ints, si at jeg hadde int numbaz [] = 1, 2, 3, type bruk som hacket seg syntaks akkurat der, så hva jeg ville gjøre er i sum jeg ønsker å passere i både numbaz og 3 å fortelle summen funksjonen "Ok, her er tabellen jeg vil at du skal summere." "Her er størrelsen." Gjør det fornuftig? Svarer at spørsmålet ditt? 

På mange måter gjør det parallelt hva vi gjør med hoved når vi har kommandolinjeargumentene. Et program som Caesar cipher, for eksempel, trengte det kommandolinjeargumenter ikke ville være i stand til å gjøre noe. Det ville ikke vet hvordan å kryptere hvis du ikke fortelle den hva nøkkel for å bruke eller hvis du ikke fortelle den hva strengen du ønsket å kryptere. Ber om innspill, dette er hvor vi har to ulike mekanismer for å ta innspill fra brukeren, for å ta informasjon i fra brukeren. For Problem Set 1 vi så dette GetInt, GetString, GetFloat måte for å be om innspill, og det kalles å bruke standard input stream. Det er litt annerledes. Det er noe som du kan gjøre på en gang, i motsetning til når du åpner programmet, når du starter programmet kjører. Kommandolinjeargumentene alle spesifiseres når du starter programmet kjører. Vi har vært å blande to av dem. Når vi bruker argumenter til en funksjon, er det mye som kommandolinjeargumenter til hovedsiden. Det er når du starter funksjonen må du fortelle det hva den trenger for å kunne utføre sine oppgaver. En annen god ting å se på, og jeg skal fortelle deg se på det i fritiden, og det ble dekket i quiz-var denne oppfatningen av omfanget og lokale variabler versus globale variabler. Gjør oppmerksom på det. 

Nå som vi får på denne andre ting, i uke 3 begynte vi å snakke om søking og sortering. Søking og sortering, i hvert fall i CS50, er veldig mye en introduksjon til noen av de mer teoretiske delene av informatikk. Problemet med søking, problemet med sortering er store, kanoniske problemer. Hvordan finner du et bestemt nummer i en rekke av milliarder av heltall? Hvordan finner du et bestemt navn i en telefonkatalog som er lagret på den bærbare datamaskinen? Og så vi introdusere denne oppfatningen av asymptotiske kjøre ganger å virkelig tallfeste hvor lenge, hvor hardt disse problem er, hvor lenge de tar for å løse. I, tror jeg, 2011s quiz det er et problem som jeg tror meritter dekker svært raskt, som er denne, problemet 12. O nei, det er Omega. 

Her snakker vi om raskest mulig kjøretid for en bestemt algoritme og deretter den tregeste mulig kjøretid. Dette Omega og O er egentlig bare snarveier. De er notasjonskonvensjonene snarveier for å si hvor fort på best mulig tilfelle vil vår algoritme kjøre, og hvor treg i verst tenkelige tilfelle vil vår algoritme kjøre? La oss gjøre et par av disse, og disse ble også dekket på kort på asymptotisk notasjon, som jeg anbefaler. Jackson gjorde en veldig god jobb. Med binær søk, snakker vi om binære søk som en algoritme, og vi vanligvis snakker om det i form av sin store O. Hva er den store O? Hva er den tregeste mulig kjøretid av binære søk? [Student] N ²? Close, antar jeg ligner på det. Det er mye raskere enn det. [Student] Binary? >> Ja, binær søk. [Student] Det er log n. Logg n, så hva gjør logge n mener? Det halverer det hver iterasjon. Nøyaktig, så i den tregeste mulig tilfelle, si hvis du har en sortert rekke av en million heltall og antall du leter etter er enten den aller første element i matrisen eller den aller siste element i matrisen. Husk fungerer det binære søk algoritme ved å se på midten element, se om det er kampen som du leter etter. Hvis det er, så flott, du fant den. 

På best mulig tilfelle, hvor fort gjør binære søk kjøre? [Studenter] 1. 1, er det konstant tid, stor O av en. Ja. [Student] Jeg har et spørsmål. Når du sier logge av n, mener du med hensyn til base 2, ikke sant? Ja, slik at den andre tingen. Vi sier log n, og jeg antar da jeg var på high school Jeg har alltid antatt at loggen var base 10. Ja, så ja, kan du logge base 2 typisk er det vi bruker. Igjen, gå tilbake til binære søk, hvis du søker for enten elementet på slutten eller elementet helt i begynnelsen, fordi du starter i midten og deretter kaste hvilken en halv oppfyller ikke kriteriene du leter etter, og du går videre til neste halvår og neste halvår og neste halve. Hvis jeg søker etter den største element i millioner heltall matrise Jeg kommer til å halvere det på de fleste log på 1 million ganger før jeg endelig teste og se at elementet jeg leter etter er i den største eller i den høyeste indeks av tabellen, og som vil ta logg av n, logg av 1 million ganger. 

Bubble slag. Husker dere gjøre boblen slags algoritme? Kevin, kan du gi meg en rask oppsummering av hva som skjedde i boblen slags algoritme? [Kevin] I utgangspunktet går gjennom alt på listen. Det ser på de to første. Hvis den første er større enn den andre en Den bytter dem. Deretter sammenlignes andre og tredje, samme, bytteavtaler, tredje og fjerde, hele veien ned. Større tall vil følge opp til slutt. Og etter imidlertid mange looper du er ferdig. Nøyaktig, så hva Kevin sa at vi vil se større tall boble opp til slutten av tabellen. For eksempel, gjør du noe imot vandre oss gjennom dette eksemplet hvis dette er vår array? [Kevin] Du tar 2 og 3. 3 er større enn 2, slik at du bytte dem. [Nate H.] Høyre, så vi bytte disse, og så får vi 2, 3, 6, 4 og 9. [Kevin] Så du sammenligne 3 og 6. 3 er mindre enn 6, så du lar dem, og 6 og 4, vil du bytte dem fordi 4 er mindre enn seks. [Nate H.] Høyre, så jeg får 2, 3, 4, 6, 9. [Kevin] og 9 er større enn 6, så du forlater den. Og du vil gå tilbake gjennom det igjen. 

[Nate H.] Er jeg ferdig på dette punktet? >> [Kevin] Nei Og hvorfor er jeg ikke ferdig på dette punktet? Fordi det ser ut som min tabellen er sortert. Jeg ser på det. [Kevin] Gå gjennom det igjen og sørge for at det ikke er flere bytteavtaler før du kan fullt ut slutte. Nøyaktig, så du må holde det gående gjennom og sørge for at det ikke er noen swapper at du kan gjøre på dette punktet. Det var egentlig bare flaks, som du sa, at vi endte opp med bare måtte gjøre en går gjennom og vi er sortert. Men for å gjøre dette i det generelle tilfellet vil vi faktisk nødt til å gjøre dette om og om igjen. Og faktisk, dette var et eksempel på en best mulig tilfelle, som vi så i problemet. Vi så at best mulig saken ble n.. Vi gikk gjennom matrisen en gang. Hva er det verste mulig tilfelle for denne algoritmen? [Kevin] N ². Og hva sånn ut? Hva ville en rekke ser sånn ville ta n ² tid? [Kevin] [hørbar] sortert. Akkurat, så hvis jeg hadde matrisen 9, 7, 6, 5, 2, først ni ville boble hele veien opp. Etter en iterasjon ville vi ha 7, 6, 5, 2, 9. Deretter 7 ville boble opp, 6, 5, 2, 7, 9, og så videre og så videre. 

Vi måtte gå gjennom hele matrisen n ganger, og du kan faktisk få litt mer presis enn dette fordi når vi har flyttet 9 hele veien opp til sin siste mulige posisjon Vi vet at vi aldri trenger å sammenligne mot dette elementet på nytt. Når vi begynner å boblende de 7 opp Vi vet at vi kan stoppe når 7 er rett før 9 siden vi allerede har sammenlignet 9 til det. Hvis du gjør dette på en smart måte er det ikke virkelig, jeg antar at mye tid. Du kommer ikke til å sammenligne alle mulige [hørbar] kombinasjoner hver eneste gang du går gjennom hver iterasjon. Men likevel, når vi snakker om dette øvre grense vi si at du ser på n ² sammenligninger hele veien gjennom. 

La oss gå tilbake, og siden vi begynner å bli litt kort på tid Jeg vil si at du bør definitivt gå gjennom resten av denne tabellen, fylle det ut. Tenk på eksempler. Tenk på konkrete eksempler. Det er veldig praktisk og nyttig å gjøre. Trekke den ut. Dette er den type tabell som når du går gjennom i informatikk du burde virkelig begynne å kjenne disse utenat. Dette er den typen spørsmål du får i intervjuer. Dette er slags ting som er bra å vite, og tenke på de edge tilfeller virkelig finne ut hvordan å tenke vel vitende om at for boble sortere verst tenkelige utvalg å sortere med det er en som er i motsatt rekkefølge. 

Pekere. La oss snakke litt om pekere. I de siste minuttene har vi her Jeg vet dette er noe sammen med fil I / O som er ganske ny. Når vi snakker om pekere grunnen til at vi ønsker å snakke om pekere er fordi, en, når vi jobber i C Vi er virkelig på et relativt lavt nivå sammenlignet med de fleste moderne programmeringsspråk. Vi er faktisk i stand til å manipulere variabler i minnet, finne ut hvor de er faktisk ligger innenfor RAM vår. Når du har gått på å ta operativsystem klasser du vil se at det er, igjen, slag av en abstraksjon. Det er faktisk ikke tilfelle. Vi har virtuelt minne som gjemmer disse detaljene fra oss. 

Men for nå kan du anta at når du har et program, for eksempel når du begynner å kjøre din Caesar cipher program- Jeg vil bytte tilbake til min iPad virkelig raskt- at helt i begynnelsen programmet ditt, hvis du har, sier 4 gigabyte RAM på din bærbare PC, du får sette denne blings, og vi kaller dette RAM. Og den starter på et sted vi kommer til å ringe 0, og det ender på et sted som vi kaller 4 gigabyte. Jeg kan virkelig ikke skrive. Man, er at hacket. Når programmet utfører operativsystemet rister opp RAM, og det angir ulike segmenter for ulike deler av programmet til å leve i. Her nede dette området er slag av en ingenmannsland. Når du går opp litt lenger her du har faktisk det stedet hvor koden for programmet liv. At faktisk binær kode, som kjørbar fil faktisk blir lastet inn i minnet når du kjører et program, og den lever i kodesegmentet. Og som programmet utfører prosessoren ser på dette kodesegmentet å finne ut hva som er den neste instruksjonen? Hva er neste kodelinje jeg trenger å kjøre? 

Det er også en data-segmentet, og det er her de streng konstanter bli lagret som du har brukt. Og så lenger opp er det dette stedet kalt haugen. Vi har tilgang til minnet i det ved hjelp av malloc, og deretter mot toppen av programmet det er stabelen, og det er der vi har spilt for det meste av begynnelsen. Dette er ikke i målestokk eller noe. Mye av dette er svært maskinen avhengig, operativsystemet avhengige, men dette er relativt hvordan ting blir chunked opp. Når du kjører et program og erklærer deg en variabel kalt x- Jeg kommer til å trekke en annen boks der nede, og dette kommer til å bli RAM også. Og jeg kommer til å se. Vi vil trekke takkete linjer for å indikere dette er bare en liten del av RAM og ikke alle av det som vi trekke øverst. 

Hvis jeg erklærer en heltallsvariabel kalt x, så hva jeg egentlig får er en kartlegging som er lagret i symboltabellen av mitt program som forbinder navnet x til denne regionen av minnet som jeg har trukket her mellom de vertikale stolpene. Hvis jeg har en linje med kode i mitt program som sier x = 7 prosessoren vet "Oh, ok, jeg vet at x bor på dette stedet i minnet." "Jeg kommer til å gå videre og skrive en 7 der." Hvordan føles det vet hvilken plassering dette er i minnet? Vel, det er alt gjort på kompilering. Kompilatoren tar seg av tildeling hvor hver av variablene kommer til å gå og å opprette en spesiell kartlegging eller snarere koble prikkene mellom et symbol og hvor det kommer, en variabel navn og hvor det kommer til å leve i minnet. Men det viser seg at vi faktisk kan få tilgang til den i våre programmer også. Dette blir viktig når vi begynner å snakke om noen av datastrukturer, som er et konsept som vi kommer til å innføre senere. 

Men for nå, hva du kan vite er at jeg kan lage en peker til denne plasseringen, x. For eksempel kan jeg lage en peker variabel. Når vi lage en peker variabel vi bruke stjernen notasjon. I dette tilfellet, sier dette jeg kommer til å lage en peker til en int. Det er en type akkurat som alle andre. Vi gir den en variabel som y, og da vi satt den lik adressen, til en adresse. I dette tilfellet, kan vi sette y for å peke til x ved å ta inn adressen x, som vi gjør med denne ampersand, og da vi satt y å peke på den. Hva dette egentlig betyr er hvis vi ser på RAM vår Dette skaper en egen variabel. Det kommer til å kalle det y, og når denne linjen med kode utfører det er faktisk kommer til å lage en liten peker som vi vanligvis trekker som en pil, og det setter y å peke på x. Ja. [Student] Hvis x er allerede en peker, ville du bare gjøre int * y = x stedet for å ha tegnet? Ja. Hvis x er allerede en peker, så kan du sette to pekere lik hverandre, i så fall ikke y vil peke på x, men det ville peke på hva x peker til. Dessverre, vi er ute av tiden. 

Hva jeg kan si på dette punktet, kan vi snakke om dette offline, men jeg vil si begynne å jobbe gjennom dette problemet, # 14. Du kan se det allerede litt fylt ut for deg her. Du kan se at når vi erklærer 2 pekere, int * x og * y, og merk at peker * ved siden av variabelen var noe som ble gjort i fjor. Det viser seg at dette er likt det vi gjør i år. Det spiller ingen rolle hvor du skriver * når du erklære pekeren. Men vi har skrevet * ved siden av typen fordi det gjør det veldig klart at du erklære en peker variabel. Du kan se at erklære 2 pekere gir oss to esker. Her når vi setter x lik malloc hva dette sier er å sette minne i haugen. Denne lille boksen her, denne sirkelen, ligger på haugen. X er koblet til den. Legg merke til at y er fortsatt ikke peker til noe. For å få minne-for å lagre nummeret 42 i x vi ville bruke det notasjon? [Student] * x = 42. Akkurat, * x = 42. Det betyr følge pilen og kaste 42 i det. Her hvor vi setter y og x har vi y peker til x. Igjen, dette er akkurat som det Kevin sa hvor vi setter y lik x. Y er ikke peker til x. Snarere er det å peke på hva x peker til også. 

Og så til slutt i denne siste boksen er det to mulige ting som vi kunne gjøre. Det ene er at vi kunne si * x = 13. Den andre tingen er at vi kunne si-Alex, vet du hva vi kunne gjøre her? Du kan si * x = 13 eller- [Student] Du kan si int uansett. [Nate H.] Hvis dette ble referert til som en int variabel vi kunne gjøre det. Vi kan også si * y = 13 fordi de er begge peker til samme sted, slik at vi kunne bruke enten variabel for å komme dit. Ja. >> [Student] Hvordan ville det se ut som om vi bare si int x er 13? Det ville være å erklære en ny variabel kalt x, som ikke ville fungere. Vi ville ha en kollisjon fordi vi erklært x å være en peker opp her. [Student] Hvis vi bare hadde den uttalelsen i seg selv hva ville det se ut i form av sirkelen? Hvis vi hadde x = 13 da ville vi ha en boks, og heller enn å ha en pil kommer ut av boksen vi ville tegne det som bare en 13. [Student] I boksen. Okay. 

Takk for at du ser på, og lykke til på Quiz 0. [CS50.TV]