ROB Bowden: Hei, jeg er Rob Bowden, og la oss snakke om quiz0. Så, det første spørsmålet. Dette er spørsmålet hvor du trengte å kode tallet 127 i binær pærer. Hvis du ville, kunne du gjøre den vanlige konverteringen fra bi-- eller, fra desimal til binær. Men det er trolig kommer til å ta mye tid. Jeg mener, du kunne finne ut det, OK, en er der inne, er to der inne, 4 er der inne, 8 er der inne. Enklere måte, er 127 128 minus én. Det lengst til venstre lyspære er den 128-bit. Så 127 er egentlig bare alt av de andre lyspærer, siden det er lengst til venstre lyspære minus 1. Det er det for det spørsmålet. 

Spørsmål ett. Så med 3 biter du kan representerer 8 forskjellige verdier. Hvorfor da er 7 den største ikke-negative Desimalheltallet du kan representere? Vel, hvis vi kan bare representerer 8 forskjellige verdier, så hva vi kommer til å være representerer er 0 til 7. 0 opptar en av verdiene. 

Spørsmål to. Med n bits, hvor mange distinkte verdiene kan du representerer? Så, med n bits, har du to mulige verdier for hver bit. Så vi har to mulige verdier for den første biten, to mulige verdier for det andre, to mulig for den tredje. Og så det er 2 ganger 2 ganger 2, og til slutt svaret er 2 til n. 

Spørsmål tre. Hva er 0x50 i binært? Så husk at heksadesimale har en veldig grei konvertering til binære. Så her, vi trenger bare å se på 5 og 0 uavhengig. Så hva er fem i binært? 0101, det er en bit og 4 bit. Hva er 0 i binært? Ikke vanskelig. 0000. Så bare sette dem sammen, og det er hele tall i binær. 01010000. Og hvis du ønsket du kunne ta av det ytterste venstre null. Det er irrelevant. 

Så da alternativt hva er 0x50 i desimal? Hvis du ville, could-- deg hvis du er mer komfortabel med det binære, du kan ta det binære svar og konvertere til desimal. Eller vi kunne bare huske som heksadesimale. Slik at 0 i 0-th sted, og 5 er den i det 16 til det første sted. Så her har vi 5 ganger 16 til først, pluss 0 ganger 16 til null, er 80. Og hvis du har sett på tittelen på spørsmålet, det var CS 80, som var en type hint til svaret på dette problemet. 

Spørsmål fem. Vi har denne Scratch script, som er gjenta fire ganger peanøttsmør gelé. Så hvordan skal vi nå kode som i C? Vel, vi har her-- den delen i fet er den eneste delen man hadde å gjennomføre. Så vi har en 4 loop som er looping 4 ganger, printf-ing peanøttsmør gelé, med ny linje som problemet ber om. 

Spørsmål seks, et nytt skrape problem. Vi ser at vi er i en evig loop. Vi sier variabelen i og deretter økes i med 1. Nå ønsker vi å gjøre det i C. Det er flere måter vi kunne ha gjort dette. Her skjedde vi å kode evig løkke som en while (true). Så vi erklærer variabelen i, bare som om vi hadde variabel jeg i Scratch. Deklarere variabelen i, og for alltid while (true), sier vi variabelen i. Så printf% I-- eller du kan har brukt% d. Vi sier at variabel, og deretter øke den, i ++. 

Spørsmål sju. Nå ønsker vi å gjøre noe lignende Mario dot c fra oppgavesettet en. Vi ønsker å skrive ut disse hashtags, vi ønsker å skrive ut en fem med tre rektangel av disse hashes. Så hvordan skal vi gjøre det? Vel, gir vi deg en hel haug med kode, og du bare må fylle ut utskrifts grid funksjonen. 

Så hvordan ser PrintGrid ut? Vel du er forbi Bredden og høyden. Så vi har en ytre 4 loop, som er looping i løpet av alle radene av denne grid som vi ønsker å skrive ut. Så har vi den inter-nestet 4 loop, det er å skrive over hver kolonne. Så for hver rad, vi skriver for hver kolonne, en enkelt hash. Så på slutten av raden vi skrive ut en enkelt ny linje for å gå til neste rad. Og det er det for hele rutenettet. 

Spørsmål åtte. En funksjon som PrintGrid sies å ha en bivirkning, men ikke en retur verdi. Forklar forskjellen. Så dette er avhengig av deg å huske hva en bivirkning er. Vel, en retur value-- vi vet PrintGrid ikke har returverdi, siden akkurat her det står ugyldig. Så noe som returnerer ugyldig gjør egentlig ikke tilbake noe. Så hva er bivirkning? Vel, er en bivirkning noe den slags vedvarer Etter at funksjonen endene det var ikke bare tilbake, og det var ikke bare fra inngangene. 

Så, for eksempel, kan vi endre en global variabel. Det ville være en bivirkning. I dette spesielle tilfelle, en svært viktig bivirkning skriver ut til skjermen. Så det er en bivirkning at PrintGrid har. Vi skriver ut disse tingene til skjermen. Og du kan tenke på at som en bivirkning, siden det er noe som vedvarer etter denne funksjonen slutter. Det er noe utenfor rammen av denne funksjon som til syvende og sist blir endret, innholdet på skjermen. 

Spørsmål ni. Tenk programmet nedenfor, hvilken linje tall har blitt lagt til skyld diskusjonen. Så i dette programmet er vi bare ringer GetString, lagre den i denne variable s, og deretter skriver den variabelen s. OK. Så forklare hvorfor linjen man er til stede. #include CS50 dot h. Hvorfor trenger vi å #include CS50 dot h? Vel vi ringer GetString funksjon, og GetString er definert i CS50 biblioteket. Så hvis vi ikke har #include CS50 dot h, vi ville få det implisitt erklæring av GetString funksjonsfeil fra kompilatoren. Så vi må ta med library-- Vi må ta med header-fil, ellers vil kompilatoren ikke erkjenner at GetString eksisterer. 

Forklar hvorfor linje to er til stede. Så standard io dot h. Det er akkurat det samme som forrige problem, bortsett fra i stedet for å håndtere GetString, vi snakker om printf. Så hvis vi ikke si at vi trenger til å omfatte standard io dot h, da vi ikke ville være i stand å bruke printf-funksjonen, fordi kompilatoren ville ikke vite om det. 

Why-- hvilken betydning av ugyldig på linje fire? Så her har vi int main (void). Det er bare å si at vi ikke får noen kommandolinje argumenter til main. Husk at vi kunne si int Hoved int argc streng argv parentes. Så her er vi bare si ugyldig å si at vi ignorerer kommandolinjeargumenter. 

Forklare, med hensyn til hukommelse, akkurat hva GetString i kø seks returer. GetString returnerer en blokk med minne, en rekke tegn. Det er virkelig å returnere en Peker til det første tegnet. Husk at en streng er en char stjerne. Så s er en peker til den første karakter i hvilken strengen er at brukeren tastes inn på tastaturet. Og det minnet skjer for å være malloced, slik at minnet er i haugen. 

Spørsmål 13. Tenk programmet nedenfor. Så alt dette programmet gjør er printf-ing 1 dividert med 10. Så når kompilert og henrettet, dette programmet utganger 0,0, selv om 1 dividert med 10 er 0,1. Så hvorfor er det 0.0? Vel, dette er fordi av heltallsdivisjon. So 1 er et helt tall, 10 er et helt tall. Så 1 dividert med 10, alt behandles som heltall, og i C, når vi gjør heltallsdivisjon, vi avkorte noen desimaltegn. Så 1 dividert med 10 0, og deretter vi prøver å skrive det som en dupp, så null skrives ut som en dupp er 0,0. Og det er derfor vi får 0,0. 

Tenk programmet nedenfor. Nå er vi skriver 0,1. Så ingen heltallsdivisjon, vi bare skriver ut 0,1, men vi skriver ut det til 28 desimaler. Og vi får dette 0,1000, en hel haug nuller, 5 5 5, blah blah blah. Så spørsmålet her er hvorfor det skrive ut at i stedet for nøyaktig 0,1? 

Så grunnen her nå floating point unøyaktighet. Husk at en float er bare 32 bits. Så vi kan bare representere et endelig antall av flyttall verdier med de 32 bits. Vel det er i siste instans uendelig mange flytverdier, og det er uendelig mange flytende punktverdier i mellom 0 og 1, og vi er selvsagt i stand til å representerer enda flere verdier enn det. Så vi må gjøre ofrene til være i stand til å representere de fleste verdier. 

Så en verdi som 0,1, tilsynelatende Vi kan ikke representere det akkurat. Så i stedet for å representere 0.1 gjør vi det beste vi kan representere dette 0.100000 5 5 5. Og det er ganske nær, men for mange applikasjoner du trenger å bekymre deg floating point unøyaktighet, fordi vi ikke kan representere all flytende punkter nøyaktig. 

Spørsmål 15. Tenk koden under. Vi bare utskrift 1 pluss 1. Så det er ingen triks her. 1 pluss 1 evaluerer til 2, og så vi skriver det. Dette skriver bare to. 

Spørsmål 16. Nå er vi skriver tegnet 1 pluss tegnet en. Så hvorfor gjør ikke dette skrive ut det samme? Vel tegnet en pluss tegnet 1, har tegnet en ASCII-verdi 49. Så dette er egentlig sier 49 pluss 49, og til slutt dette kommer til å skrive ut 98. Slik at dette ikke skrives 2. 

Spørsmål 17. Fullfør gjennomføringen av odde nedenfor på en slik måte at funksjonen returnerer true hvis n er et oddetall og usann hvis n er jevn. Dette er et flott formål for mod operatør. Så vi tar vårt argument n, dersom n mod 2 er lik 1, vel det betyr at n delt etter 2 hadde en rest. Hvis n dividert med 2 hadde en rest, som betyr at n er et oddetall, så vi returnere true. Annet vi return false. Du kunne også ha gjort n mod to likemenn null, return false, ellers returnere true. 

Tenk den rekursive funksjonen nedenfor. Slik at hvis n er mindre enn eller lik 1, retur 1, else return n ganger f av n minus 1. Så hva er denne funksjonen? Vel, dette er bare faktoriell funksjon. Dette er pent representert som n faktorer. 

Så spørsmålet 19 nå, vi ønsker å ta denne rekursiv funksjon. Vi ønsker å gjøre det iterativ. Så hvordan gjør vi det? Vel for de ansatte -løsning, og igjen er det flere måter du kunne ha gjort som starter vi med dette int produktet er lik 1. Og i hele denne for loop, skal vi skal multiplisere produktet til slutt ende opp med den fullstendig faktoriell. Så for int i er lik 2, er jeg mindre enn eller lik n, i ++. 

Du lurer kanskje på hvorfor jeg er lik to. Vel, husk at her har vi å sørge for at vårt base case er riktig. Slik at hvis n er mindre enn eller lik til 1, vi bare tilbake en. Så over her, starter vi på i lik to. Vel, hvis jeg var en, deretter the-- eller hvis n var en, deretter for loop ville ikke utføre i det hele tatt. Og så ville vi bare retur produkt, som er en. Tilsvarende, dersom n var noe mindre enn 1-- om det var 0, negativ en, whatever-- vi vil fortsatt være tilbake 1, som er nøyaktig hva den rekursive versjonen gjør. 

Nå, dersom n er større enn 1, så vi kommer til å gjøre minst ett iterasjon av denne sløyfen. Så la oss si n er 5, så vi er kommer til å gjøre produkt ganger er lik to. Så nå produktet er 2. Nå skal vi gjøre produkt ganger er lik 3. Nå er det seks. Produkt ganger tilsvarer 4, nå er det 24. Produkt ganger tilsvarer fem, nå er det 120. Så til slutt returnerer vi 120, noe som er riktig 5 fakultetet. 

Spørsmål 20. Dette er en der du må fylle i denne tabell med hvilken som helst gitt algoritme, noe som vi har sett, at passer disse algoritmisk run ganger disse asymptotiske kjøretider. Så hva er en algoritme som er omega på 1, men big O av n? Så det kan være uendelig mange svar her. Den som vi har sett nok mest ofte er like lineær søk. 

Så i beste fall scenario, elementet vi er leter etter er på begynnelsen av listen og så på omega for en trinn, det første vi sjekker, vi bare umiddelbart returnere at vi fant elementet. I verste fall, elementet er ved slutten, eller varen ikke er på listen i det hele tatt. Så vi må søke hele listen, alle n elementer, og det er derfor det er o n. 

Så nå er det noe som er både omega n log n, og store O n log n. Vel den mest relevante ting vi har sett her er flette slag. Så flette sortere, husker, er i siste instans Theta av n log n, der theta er definert dersom både omega og stort O er de samme. Både n log n. 

Hva er noe som er omega av N, O og n kvadrerte? Vel, igjen er det flere mulige svar. Her vi tilfeldigvis si boble slag. Innsetting slags ville også fungere her. Husk at boble slags har som optimalisering der, hvis du er i stand til å få gjennom hele listen uten å behøve å gjøre eventuelle bytteavtaler, da, vel, Vi kan umiddelbart tilbake at listen ble sortert til å begynne med. Så i beste fall det er bare omega av n. Hvis det er ikke bare et pent sortert liste til å begynne med, så har vi O n squared bytteavtaler. Og til slutt, har vi valg liksom for n squared, både omega og stor O. 

Spørsmål 21. Hva er heltallsoverflyt? Vel igjen, i likhet med tidligere, vi bare har begrenset mange biter for å representere et helt tall, så kanskje 32 biter. La oss si at vi har en signert heltall. Så til slutt den høyeste positivt tall vi kan representere er 2 til 31 minus en. Så hva skjer hvis vi prøver å deretter øke som heltall? Vel, vi kommer til å gå fra 2 til 31 minus 1, hele veien ned til negative 2 til 31. Så dette heltallsoverflyt er når du holder økes, og til slutt kan du ikke få noe høyere, og det bare brytes hele veien tilbake rundt til en negativ verdi. 

Hva med en buffer overflow? Så en buffer overflow-- huske hva en buffer er. Det er bare en del av minnet. Noe sånt som en matrise er en buffer. Så en buffer overflow er når du prøver å få tilgang til minnet utover slutten av denne matrisen. Så hvis du har en matrise av størrelse 5 og du forsøke å få tilgang matrise brakett 5 eller brakett 6 eller brakett 7, eller noe utover ende, eller til og med noe below-- rekke brakett negative 1-- alle av dem er buffer overflow. Du berører minne i dårlige måter. 

Spørsmål 23. Så i denne du trenger å implementere strlen. Og vi forteller deg at du kan anta s vil ikke være null, slik at du ikke trenger å gjøre noe sjekk på null. Og det er flere måter du kunne ha gjort dette. Her bare tar vi grei. Vi starter med en teller, n. n er telle hvor mange tegn det er. Så vi starter på 0, og da er vi iterere over hele listen. 

S er 0 brakett lik null terminator karakter? Husk at vi leter etter den avsluttende nulltegn å bestemme hvor lenge strengen er. Det kommer til å si opp noen relevant streng. Så er s brakett 0 lik til null terminator? Hvis det er det, så vi kommer til å se på s brakett 1, s brakett 2. Vi holder det gående til vi finne den avsluttende null. Når vi har funnet den, så n inneholder den totale lengde av strengen, og vi kan bare returnere det. 

Spørsmål 24. Så dette er en hvor du har å gjøre trade off. Så en ting er bra i ett måte, men på hvilken måte er det dårlig? Så her, slå sammen liksom en tendens til å være raskere enn boble slag. Når det er sagt at-- vel, det er flere svar her. Men det viktigste er at boble slags er omega for n for en sortert liste. 

Husk at bordet vi så tidligere. Så boble sorterer omega for n, den best case scenario er det er i stand til å bare gå over listen, når, bestemme hei denne saken er allerede sorteres, og retur. Flettesortering, uansett hva du gjør det, er omega n log n. Så for sortert liste, boble sorter kommer til å bli raskere. 

Hva nå om knyttet lister? Så en lenket liste kan vokse og krympe til å passe så mange elementer som det er nødvendig. Etter å ha sagt at-- så vanligvis den direkte sammenligning kommer til å være en koblet liste med en matrise. Så selv om arrays kan lett vokse og krympe å passe så mange elementer etter behov, en lenket liste sammenlignet med en array-- en matrise har random access. Vi kan indeksere inn i ethvert Spesielt element i matrisen. 

Så for en lenket liste, kan vi ikke bare gå til det femte elementet, vi har å traversere fra begynnelsen før vi kommer til det femte element. Og det kommer til å hindre oss i å gjør noe sånt binære søk. Snakker av binære søk, binære søk en tendens til å være raskere enn lineær søk. Etter å ha sagt at-- så, en mulig ting er at du ikke kan gjøre binær søke på lenkede lister, du kan bare gjøre det på arrays. Men sannsynligvis enda viktigere, du kan ikke gjøre binære søk på en matrise som ikke er sortert. Upfront du kanskje trenger å sortere rekken, og bare da kan du gjør binære søk. Så hvis noe ikke er sorterte til å begynne med, så lineær søk kan være raskere. 

Spørsmål 27. Så vurdere programmet nedenfor, som vil være i neste lysbilde. Og dette er en der vi er kommer til å ønske å eksplisitt verdiene for de forskjellige variabler. Så la oss se på det. 

Så linje en. Vi har int x er lik 1. Det er det eneste som har skjedd. Så på linje én, ser vi i vår bord, som y, a, b, og tmp er alle mørklagt. Så hva er x? Vel vi bare sette den lik 1. Og deretter linje to, vel, Vi ser at y er satt til 2, og bordet er allerede fylt ut for oss. Slik at x er 1 og y er 2. 

Nå, linje tre, er vi nå inne i swap-funksjonen. Hva gjorde vi passerer å bytte? Vi passerte ampersand x for en, og tegnet y for b. Hvor problemet tidligere uttalt at adressen av x er 0x10, og adressen y er 0x14. Så a og b er lik 0x10 og 0x14, henholdsvis. 

Nå på linje tre, hva er x og y? Vel, ingenting har endret seg ca x og y på dette punktet. Selv om de er inne i en hoved stack ramme, de har fortsatt den samme verdier de gjorde før. Vi har ikke endret noe minne. Så x er 1, y er 2. OK. Så nå sier vi int tmp lik stjerne en. Så på linje fire, alt er den samme bortsett tmp. Vi har ikke endret noen verdier på noe bortsett tmp. Vi setter tmp lik stjerne en. Hva er stjerne en? Vel, noen punkter til x, så stjerne en kommer til lik x, som er en. Så alt er kopiert ned, og tmp er satt til 1. 

Nå er den neste linje. Stjerne en lik stjerners b. Så for linje five-- godt igjen, alt er den samme, bortsett fra hva stjerne en er. Hva er stjerne en? Vel, vi sa bare stjerne a er x. Så vi endrer x til lik stjerne b. Hva er stjerne b? y. b peker på y. Så stjerners b er y. Så vi setter x lik y, og alt annet er den samme. Så vi ser i neste rad at x er nå 2, og resten er bare kopiert ned. 

Nå i neste linje, lik stjerne b tmp. Vel, vi sa bare stjerne b er y, så vi setter y lik tmp. Alt annet er det samme, så alt blir kopiert ned. Vi setter y lik TMP, som er en, og alt annet er det samme. 

Nå endelig, linje sju. Vi er tilbake i den viktigste funksjonen. Vi er ute etter swap er ferdig. Vi har mistet en, b, og tmp, men til syvende og sist vi ikke endre noen verdier på noe punkt på dette, vi bare kopiere x og y ned. Og vi ser at x og y er Nå 2 og 1 stedet for 1 og 2. Rentebytteavtalen har lykkes henrettet. 

Spørsmål 28. Anta at du støter feilmeldingene nedenfor i kontortiden neste år som en CA eller TF. Advise hvordan du løser hver av disse feilene. Så udefinerte referanse til GetString. Hvorfor kan du se dette? Vel, hvis en student bruker GetString i koden sin, de gikk riktig hash inkludert CS50 dot h å inkludere CS50 biblioteket. 

Vel, hva gjør de trenger å fikse denne feilen? De trenger å gjøre en dash lcs50 på kommandolinje når de er kompilering. Så hvis de ikke passerer klang dash lcs50, de er ikke kommer til å ha den faktiske kode som implementerer GetString. 

Spørsmål 29. Implisitt erklære bibliotek funksjon strlen. Vel dette nå, de har ikke gjort riktig hash inkludere. I dette spesielle tilfellet, header-fil de trenger for å inkludere er streng dot h, og med streng dot h, nå den student-- nå kompilatoren har tilgang til erklæringer strlen, og den vet at koden bruker StrLen riktig. 

Spørsmål 30. Flere prosent konverter enn data argumenter. Så hva er dette? Husker godt at disse prosent signs-- hvordan de er relevante for printf. Så i printf kan vi percent-- vi kan skrive ut noe som prosent i backslash n. Eller vi kan skrive ut som prosent i, plass, prosent i, plass, prosent i. Så for hver av dem prosenttegn, trenger vi å passere en variabel ved slutten av printf. 

Så hvis vi sier printf paren prosent jeg backslash n nære paren, vel, sier vi at vi er kommer til å skrive ut et heltall, men da vi ikke passerer printf et heltall å faktisk skrive ut. Så her flere prosent konverteringer enn data argumenter? Det er å si at vi har en hel haug med prosenter, og vi ikke har nok variabler å faktisk fylle ut disse prosentene. 

Og så definitivt, for spørsmål 31, definitivt mistet 40 bytes i en blokker. Så dette er en Valgrind feil. Dette er å si at et sted i koden din, du har en fordeling som er 40 bytes stor, så du malloced 40 bytes, og du aldri frigjort den. Mest sannsynlig at du bare trenger å finne noen minnelekkasje, og finne ut hvor du må frigjøre denne minneblokk. 

Og spørsmålet 32, ugyldig skrive av størrelse 4. Dette er igjen en Valgrind feil. Dette trenger ikke å gjøre med minnelekkasjer nå. Dette er, de fleste likely-- jeg mener, det er noen slags ugyldig minne rettigheter. Og mest sannsynlig er dette noen slags buffer overflow. Der du har en matrise, kanskje et heltall array, og la oss si det er av størrelse 5, og du prøve å ta matrise brakett 5. Så hvis du prøver å skrive til verdi, det er ikke en del av minnet at du faktisk har tilgang til, og så du kommer til å få denne feilen, sier ugyldig skrive av størrelse 4. Valgrind kommer til å kjenne deg er prøver å røre minne upassende. 

Og det er det for quiz0. Jeg er Rob Bowden, og dette er CS50.