ROB BOWDEN: Hej, jeg hedder Rob Bowden, og lad os tale om quiz0. Så første spørgsmål. Det er spørgsmålet om, hvor du behov for at kode nummeret 127 i de binære pærer. Hvis du ville, kunne du gøre regelmæssig konvertering fra bi-- eller fra decimal til binær. Men det er sandsynligvis vil til at tage en masse tid. Jeg mener, du kunne regne ud, at, OK, 1 er i der, 2 er i der, 4 er der, 8 er derinde. Nemmere måde, 127 er 128 minus én. Det længst til venstre pære er 128-bit. Så 127 er virkelig bare alt af de andre pærer, da det er den længst til venstre pære minus 1. Det er det for det spørgsmål. 

Spørgsmål én. Så med 3 bit du kan repræsenterer 8 forskellige værdier. Hvorfor er 7 den største ikke-negative decimal heltal du kan repræsentere? Tja, hvis vi kun kan repræsenterer 8 forskellige værdier, så hvad vi kommer til at være repræsenterer er 0 til 7. 0 fylder en af ​​værdierne. 

Spørgsmål to. Med n bits, hvor mange særskilte Værdierne kan du repræsenterer? Så med n bits, har du 2 mulige værdier for hver bit. Så vi har 2 mulige værdier for den første bit, 2 mulige værdier for det andet, 2 muligt for den tredje. Og så er der 2 gange 2 gange 2, og sidste ende svaret er 2 til n. 

Spørgsmål tre. Hvad er 0x50 i binær? Så husk at hexadecimal har en meget ligetil omdannelse til binær. Så her er vi bare nødt til at se på 5 og 0 uafhængigt. Så hvad er 5 i binær? 0101, det er 1 bit og 4 bit. Hvad er 0 i binær? Ikke tricky. 0000. Så bare sætte dem sammen, og det er det fulde antal i binær. 01010000. Og hvis du ønskede du kunne tage det længst til venstre nul. Det er irrelevant. 

Så alternativt hvad er 0x50 i decimal? Hvis du ønskede, du could--, hvis du er mere komfortabel med den binære, du kunne tage det binære svar og konvertere det til decimal. Eller vi kunne bare huske at hexadecimal. Således at 0 er i 0-th sted, og 5 er i 16 til det første sted. Så her har vi 5 gange 16 til første plus 0 gange 16 til nul, er 80. Og hvis man så på titel til spørgsmålet, det var CS 80, som var lidt af en vink til svaret på dette problem. 

Spørgsmål fem. Vi har denne Scratch script, som er gentage 4 gange jordnøddesmør gelé. Så hvordan gør vi nu kode, der i C? Tja, vi har her-- den del med fed er den eneste del, du var nødt til at gennemføre. Så vi har en 4 løkke, der er looping 4 gange, printf-ing jordnøddesmør gelé, med ny linje som problemet beder om. 

Spørgsmål seks, en anden Scratch problem. Vi ser, at vi er i en evig løkke. Vi siger variablen i og derefter inkrementering jeg med 1. Nu ønsker vi at gøre det i C. Der er flere måder, vi kunne have gjort det. Her skete vi at kode evigt loop som en while (sand). Så vi erklærer variablen i, bare ligesom vi havde variabel jeg i Scratch. Erklære variablen i, og for evigt while (true), siger vi variablen i. Så printf% I-- eller du kunne have brugt% d. Vi siger, at variable, og så øg det, jeg ++. 

Spørgsmål syv. Nu ønsker vi at gøre noget meget lignende til Mario dot c fra problem angive én. Vi ønsker at udskrive disse hashtags, vi ønsker at udskrive et fem med tre rektangel af disse hashes. Så hvordan skal vi gøre det? Nå, vi giver dig en hel bundt af kode, og du bare skal udfylde print grid-funktionen. 

Så hvad betyder PrintGrid se ud? Nå du er forbi bredde og højde. Så vi har en ydre 4 loop, der er looping i alle rækkerne i denne grid, at vi ønsker at udskrive. Så har vi den inter-indlejrede 4 loop, det er udskrivning over hver kolonne. Så for hver række, vi udskriver for hver søjle en enkelt hash. Så i slutningen af ​​rækken, vi udskriver en enkelt ny linje til at gå til den næste række. Og det er det for hele nettet. 

Spørgsmål otte. En funktion som PrintGrid siges at har en bivirkning, men ikke en tilbagevenden værdi. Forklarer sondringen. Så dette er afhængig af dig at huske hvad en bivirkning er. Tja, en tilbagevenden value-- vi kender PrintGrid ikke har returværdi, eftersom lige her det siger ugyldig. Så noget, der returnerer void ikke rigtig returnere noget. Så hvad er den bivirkning? Tja, en bivirkning er noget den slags fortsætter efter at funktionen ender det var ikke lige vendt tilbage, og det var ikke bare fra indgangene. 

Så, for eksempel, kan vi ændre en global variabel. Det ville være en bivirkning. I dette særlige tilfælde, en meget vigtig bivirkning udskriver til skærmen. Så der er en bivirkning at PrintGrid har. Vi udskriver disse ting på skærmen. Og du kan tænke på at som en bivirkning, da det er noget, fortsætter efter denne funktion slutter. Det er noget, der ikke er omfattet af denne funktion, der i sidste ende bliver ændret, indholdet af skærmen. 

Spørgsmål ni. Overvej program nedenfor hvortil linjenumre er blevet tilføjet for skyld diskussion. Så i dette program, vi er lige ringer getString, oplagring Denne variabel s, og derefter udskriver variable s. OK. Så forklare, hvorfor line man er til stede. #include CS50 dot h. Hvorfor har vi brug for at # include CS50 dot h? Godt vi kalder den GetString funktion, og getString defineres i CS50 biblioteket. Så hvis vi ikke havde #include CS50 dot h, vi ville få det underforstået erklæring af getString funktion fejl fra compiler. Så vi er nødt til også at omfatte library-- vi er nødt til også at omfatte header fil, ellers compileren vil ikke erkende, at getString eksisterer. 

Forklar hvorfor linje to er til stede. Så standard io dot h. Det er præcis den samme som det tidligere problem, undtagen i stedet for at behandle GetString, vi taler om printf. Så hvis vi ikke sige, at vi har brug for omfatte standard io dot h, så ville vi ikke være i stand at bruge printf funktion, fordi oversætteren ville ikke vide det. 

Why-- hvad er betydningen af ugyldig linje fire? Så her har vi int main (void). Det er bare at sige, at vi ikke får nogen kommandolinie argumenter til main. Husk, at vi kunne sige int vigtigste int argc string argv parentes. Så her er vi bare sige tomrum at sige vi ignorerer kommandolinjeargumenter. 

Forklare med hensyn til hukommelse, præcis hvad getString på linje seks afkast. GetString returnerer en blok af hukommelse, en række tegn. Det er virkelig at vende tilbage en markøren til det første tegn. Husk, at en streng er en char stjerne. Så s er en pointer til den første karakter uanset strengen er at brugeren har indtastet på tastaturet. Og at hukommelsen sker for at være malloced, således at hukommelsen er i hoben. 

Spørgsmål 13. Overveje programmet nedenfor. Så alt dette program er at gøre er printf-ing 1 divideret med 10. Så når kompileret og henrettet, dette program udgange 0.0, selvom 1 divideret med 10 er 0,1. Så hvorfor er det 0,0? Nå, det er fordi af heltalsdivision. So 1 er et helt tal, 10 er et heltal. So 1 divideret med 10, alt behandles som heltal, og i C, når vi gør heltalsdivisioner, vi trunkere kommaet. Så 1 divideret med 10 0, og så vi prøver at printe som en svømmer, så nul udskrives som en float er 0,0. Og det er derfor, vi får 0,0. 

Overveje programmet nedenfor. Nu er vi udskriver 0.1. Så ingen heltalsdivisioner, vi bare udskriver 0,1, men vi udskriver det til 28 decimaler. Og vi får denne 0.1000, en hel flok af nuller, 5 5 5, bla bla bla. Så spørgsmålet her er, hvorfor gør det udskrive, at i stedet for nøjagtigt 0,1? 

Så grunden her er nu floating point unøjagtighed. Husk, at en float er kun 32 bits. Så vi kan kun repræsentere et endeligt antal af floating point-værdier med de 32 bit. Nå der er i sidste ende uendeligt mange kommeværdier, og der er uendeligt mange flydende pointværdier i mellem 0 og 1, og vi er naturligvis i stand til at repræsenterer endnu flere værdier end. Så vi er nødt til at ofre for at være i stand til at repræsentere de fleste værdier. 

Så en værdi som 0,1, tilsyneladende Vi kan ikke repræsentere det nøjagtigt. Så i stedet for at repræsentere 0,1 vi gør bedste vi kan repræsentere denne 0.100000 5 5 5. Og det er temmelig tæt, men for en masse ansøgninger du skal bekymre dig om floating point unøjagtighed, fordi vi kan bare ikke repræsentere alt flydende punkter nøjagtigt. 

Spørgsmål 15. Betragt koden nedenfor. Vi er lige udskrivning 1 plus 1. Så der er ingen trick her. 1 plus 1 evalueres til 2, og så vi udskriver det. Dette blot udskriver 2. 

Spørgsmål 16. Nu er vi udskriver karakter 1 plus tegnet 1. Så hvorfor gør dette ikke udskrive det samme ting? Godt tegn 1 plus tegnet 1, tegnet 1 har ASCII værdi 49. Så dette er virkelig siger 49 plus 49, og i sidste ende det kommer til at udskrive 98. Så det ikke udskrives 2. 

Spørgsmål 17. Afslutte gennemførelsen ulige nedenfor på en sådan måde at funktionen returnerer true hvis n er ulige og falsk, hvis n er lige. Dette er en stor formål til mod operatøren. Så vi tager vores argument n, hvis n mod 2 er lig med 1, og det betyder, at n delt med 2 havde en rest. Hvis n divideret med 2 havde en rest, der betyder, at n er ulige, så vi vender tilbage sandt. Else vi return false. Du kunne også have gjort n mod 2 ligemænd nul, return false, ellers returnere sandt. 

Overvej rekursiv funktion nedenfor. Så hvis n er mindre end eller lig med 1, afkast 1, ellers tilbagevenden n gange f n minus 1. Så hvad er denne funktion? Nå, det er bare den faktoriel funktion. Dette er pænt repræsenteret n faktoriel. 

Så Spørgsmål 19 nu, vi ønsker at tage denne rekursiv funktion. Vi ønsker at gøre det iterativ. Så hvordan gør vi det? Godt for de ansatte opløsning, og igen er der flere måder, du kunne have gjort at vi starter med dette int produkt er lig med 1. Og i hele for-løkke, vil vi at multiplicere produktet til sidst ender med fuld fakultetsværdien. Så for int jeg lig med 2, i er mindre end eller lig med n, i ++. 

Du kan være undrende, hvorfor jeg er lig med 2. Nå, så husk at her har vi at at sikre vores base case er korrekt. Så hvis n er mindre end eller lig til 1, vi bare returnere 1. Så her over, vi starter ved jeg lig med 2. Tja, hvis jeg var 1, så til-- eller hvis n var 1, så for-løkken ville ikke udføre overhovedet. Og så ville vi bare tilbagevenden produkt, som er 1. Tilsvarende, hvis n var noget mindre end 1-- hvis det var 0, negative 1, whatever-- vi ville stadig tilbage 1, som er det præcis rekursiv version gør. 

Nu, hvis n er større end 1, så vi vil at gøre mindst én iteration af denne løkke. Så lad os sige n er 5, så er vi vil gøre produktets gange lig med 2. Så nu vare er 2. Nu skal vi til at gøre produkt- gange lig med 3. Nu er det 6. Produkt gange svarer til 4, nu er det 24. Produkt gange lig 5, nu er det 120. Så i sidste ende, vi vender tilbage 120, som er korrekt 5 factorial. 

Spørgsmål 20. Dette er den ene, hvor du nødt til at udfylde i denne tabel med en given algoritme, noget, som vi har set, at passer disse algoritmiske løb gange disse asymptotiske run Times. Så hvad er en algoritme, er omega på 1, men store O n? Så der kan være uendeligt mange svar her. Den ene, som vi har set nok mest ofte er bare lineær søgning. 

Så i bedste fald scenarie, elementet er vi efter på begyndelsen af ​​listen og så i omega på 1 trin den første ting, vi kontrollere, vi bare straks at vende tilbage at vi fandt varen. I det værst tænkelige scenarie, elementet er i slutningen, eller varen ikke er på listen overhovedet. Så vi nødt til at søge hele listen, alle n elementer, og det er derfor, det er o n. 

Så nu er det noget, der er både omega n log n, og store O n log n. Nå de mest relevante ting vi har set her er Mergesort. Så Mergesort husk, er i sidste ende theta n log n, hvor theta er defineret hvis begge omega og store O er de samme. Både n log n. 

Hvad er noget, der er omega n og O n kvadreret? Nå, igen er der flere mulige svar. Her sker vi sige boble slags. Indsættelsessortering vil også arbejde her. Husk, at Boblesortering har denne optimering, hvor hvis du er i stand til at få gennem hele listen uden at gøre eventuelle swaps, så godt, kan vi straks returnere det listen blev sorteret til at begynde med. Så i bedste fald, det er bare omega n. Hvis det er ikke bare et pænt sorteret liste til at begynde med, så har vi O n kvadreret swaps. Og endelig har vi valg Sorter for n kvadreret, både omega og store O. 

Spørgsmål 21. Hvad er heltalsoverløb? Godt igen svarende til tidligere, vi kun har endeligt mange bits at repræsentere et heltal, Så måske 32 bits. Lad os sige, at vi har en underskrevet heltal. Så i sidste ende den højeste positivt tal, vi kan repræsentere er 2 til 31 minus 1. Så hvad sker der, hvis vi forsøger at inkrementér derefter at heltal? Nå, vi kommer til at gå fra 2 til 31 minus 1, hele vejen ned til negativ 2 til 31. Så dette heltalsoverløb er når du holder forøgelse, og i sidste ende kan du ikke få nogen højere, og det bare wraps hele vejen tilbage rundt til en negativ værdi. 

Hvad med en buffer overflow? Så en buffer overflow-- huske, hvad en buffer er. Det er bare en luns af hukommelse. Noget som et array er en buffer. Så en buffer overflow er, når du forsøger at få adgang til hukommelse efter udgangen af ​​det array. Så hvis du har en vifte af størrelse 5 og du forsøger at få adgang vifte beslag 5 eller beslag 6 eller beslag 7 eller noget ud over det ende, eller endog noget below-- række beslag negativ 1-- alle af dem er bufferoverløb. Du rører hukommelse i dårlige måder. 

Spørgsmål 23. Så i denne ene, du har brug for at gennemføre strlen. Og vi fortælle dig, at du kan antage s vil ikke være null, så du ikke behøver at gøre enhver kontrol for null. Og der er flere måder du kunne have gjort dette. Her er vi bare tage det ligetil. Vi starter med en tæller, n. n er tælle hvor mange tegn der er. Så vi starter på 0, og så vi gentage hele listen. 

Er s beslag 0 svarer til den null terminator karakter? Husk, vi leder efter null terminator karakter at bestemme hvor længe vores streng. Der vil afslutte alle relevante streng. Så er s beslag 0 lig til null terminator? Hvis det ikke er, så vi kommer til at se på s beslag 1, s beslag 2. Vi holde gå, indtil vi finde den null terminator. Når vi har fundet det, så n indeholder den totale længde af strengen, og vi kan bare returnere det. 

Spørgsmål 24. Så dette er den ene, hvor du nødt til at gøre afvejning. Så en ting er god i én måde, men på hvilken måde er det dårligt? Så her, Mergesort tendens til være hurtigere end boble slags. Når det er sagt at-- godt, der er flere svar her. Men det vigtigste er, at Boblesortering er omega n for en sorterede liste. 

Husk, at tabellen vi lige har set tidligere. Så boble sorterer omega n, i bedste fald er det i stand til bare at gå over listen gang, bestemme hey denne ting er allerede sorteret, og vende tilbage. Mergesort, uanset hvad du gør, er omega n log n. Så for sorterede liste, boble sortere kommer til at være hurtigere. 

Nu hvad hægtede lister? Så en sammenkædet liste kan vokse og krympe til at passe så mange elementer efter behov. Når det er sagt at-- så normalt direkte sammenligning vil være en sammenkædet liste med et array. Så selvom arrays kan let vokse og skrumpe til at passe så mange elementer efter behov, liste en sammenkædet sammenlignet med en array-- en matrix har random access. Vi kan indekset i enhver særlige element i arrayet. 

Så for en linket liste, kan vi ikke bare gå til det femte element, Vi er nødt til at krydse fra begyndelsen indtil vi kommer til det femte element. Og det kommer til at forhindre os gør noget lignende binær søgning. Apropos binær søgning, binær søgning tendens til at være hurtigere end lineær søgning. Sagt at-- så er en mulig ting er, at du ikke kan gøre binær søge på hægtede lister, du kan kun gøre det på arrays. Men sandsynligvis endnu vigtigere, du kan ikke gøre binær søgning på en matrix, der ikke er sorteret. Upfront du måske brug for at sortere array, og først derefter kan du gør binær søgning. Så hvis dine ting er ikke sorterede til at begynde med, så lineær søgning kunne være hurtigere. 

Spørgsmål 27. Så overveje programmet nedenfor, som vil være i det næste lysbillede. Og dette er den ene, hvor vi er lyst til at udtrykkeligt fremgår, værdierne for forskellige variable. Så lad os se på det. 

Så line den ene. Vi har int x er lig med 1. Det er den eneste ting, der er sket. Så på linje et, vi ser i vores tabel, at y, a, b, og tmp er alle mørklagt. Så hvad er x? Nå vi bare sætte det lig med 1. Og derefter linje to, ja, ser vi, at y er sat til 2, og tabellen er allerede udfyldes for os. Så x er 1 og y er 2. 

Nu linje tre, men vi er nu inde i swap-funktion. Hvad gjorde vi passerer at bytte? Vi passerede tegnet x for a, og tegnet y for f. Hvor problemet tidligere erklærede, at adressen på x er 0x10, og adressen på y er 0x14. Så a og b er lig med 0x10 og 0x14 hhv. 

Nu ved linie tre, hvad er x og y? Nå, har intet ændret sig om x og y på dette punkt. Selvom de er inde i en main stakramme, de stadig har samme værdier, som de gjorde før. Vi har ikke ændret noget hukommelse. Så x er 1, y er 2. Ok. Så nu vi sagde int tmp lig stjerne en. Så på linje fire, alt er den samme bortset tmp. Vi har ikke ændret nogle værdier af noget bortset fra tmp. Vi sætter tmp lig stjerne en. Hvad er stjernen? Tja, en punkter til x, så stjerne en vil lige x, som er 1. Så alt er kopieret ned og tmp er sat til 1. 

Nu den næste linje. Stjerne a er lig stjernede b. Så ved linje five-- godt igen, alt er den samme, bortset fra hvad stjernen er. Hvad er stjernen? Godt, vi lige sagt stjerne a er x. Så vi er ved at ændre x til lige stjernede b. Hvad er stjernede b? y. B peger på y. Så stjerne b er y. Så vi indstillingen x er lig med y, og alt andet er det samme. Så vi ser i den næste række, at x er nu 2, og resten er bare kopieret ned. 

Nu i den næste linje, stjernede b lig tmp. Godt, vi lige sagt stjerne b er y, så vi indstille y lig med tmp. Alt andet er det samme, så alt bliver kopieret ned. Vi indstilling y lig med TMP, hvilket er en, og alt andet er det samme. 

Nu endelig linje syv. Vi er tilbage i den vigtigste funktion. Vi er ude efter swap er færdig. Vi har mistet a, b, og tmp, men i sidste ende vi ikke ændre nogen værdier noget på dette punkt, vi bare kopiere x og y ned. Og vi ser, at x og y er nu 2 og 1 i stedet for 1 og 2. Swappen har med succes udført. 

Spørgsmål 28. Antag, at du støder på fejlmeddelelser nedenfor i kontortiden næste år som en CA eller TF. Rådgive, hvordan du løser hver af disse fejl. Så udefineret reference til getString. Hvorfor kunne du se det? Tja, hvis en elev bruger GetString i deres kode, de har ordentligt hash inkluderet CS50 dot h at omfatte CS50 biblioteket. 

Nå, hvad gør de nødt til at rette fejlen? De har brug for at gøre en bindestreg lcs50 på kommandolinjen når de kompilering. Så hvis de ikke kan passere klang dash lcs50, de er ikke kommer til at have den faktiske kode, der implementerer getString. 

Spørgsmål 29. Implicit erklære bibliotek funktion strlen. Nå det nu, har de ikke gjort korrekt hash omfatter. I dette særlige tilfælde, headerfilen de skal omfatte, er streng dot h og med streng dot h, nu den student-- nu compiler har adgang til erklæringer om strlen, og det ved, at din kode bruger StrLen korrekt. 

Spørgsmål 30. Flere procent konverteringer end data argumenter. Så hvad er det? Nå huske, at disse procent signs-- hvordan de er relevante for printf. Så i printf vi måske percent-- vi måske udskrive noget ligesom procent i backslash n. Eller vi kan printe ligesom procent i, rum, procent i, plads, procent i. Så for hver af dem, procenttegn, vi har brug for at passere en variabel i slutningen af ​​printf. 

Så hvis vi siger printf paren procent Jeg backslash n nære paren, godt, siger vi, at vi er vil udskrive et heltal, men så har vi ikke passere printf et heltal til rent faktisk at udskrive. Så her mere procent konverteringer end data argumenter? Det er at sige, at vi har en hel bunke af procenter, og vi har ikke nok variabler til faktisk at udfylde disse procenter. 

Og så absolut, for spørgsmål 31, helt tabt 40 bytes i en blokke. Så dette er en Valgrind fejl. Det siger, at et eller andet sted i din kode, du har en fordeling, der er 40 bytes store, så du malloced 40 bytes, og du aldrig befriet det. Mest sandsynligt, du bare har brug for at finde nogle hukommelsesfejl, og finde, hvor du har brug for frigøre denne blok af hukommelse. 

Og spørgsmål 32, ugyldig write af størrelse 4. Igen dette er en Valgrind fejl. Dette behøver ikke at gøre med memory leaks nu. Dette er mest likely-- Jeg mener, det er en slags ugyldige hukommelse rettigheder. Og sandsynligvis dette er nogle slags buffer overflow. Hvor du har en array, måske et heltal array, og lad os sige, det er af størrelse 5, og du prøve at røre række beslag 5. Så hvis du prøver at skrive til denne værdi, det er ikke et stykke af hukommelse at du rent faktisk har adgang til, og så du kommer til at få denne fejl, siger ugyldig write størrelse 4. Valgrind kommer til at genkende dig er forsøger at røre hukommelse uhensigtsmæssigt. 

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