ROB BOWDEN: Hoi, ik ben Rob Bowden, en laten we praten over quiz0. Dus, de eerste vraag. Dat is de vraag waar u nodig om het aantal te coderen 127 in de binaire bollen. Als je wilde, kon je doen de reguliere conversie uit bi-- of, van decimaal naar binair. Maar dat gaat waarschijnlijk om veel tijd in beslag nemen. Ik bedoel, je zou erachter te komen dat, OK, 1 is daar, 2 is daar, 4 is daar, 8 is daar. Gemakkelijkere manier, 127 is 128 minus één. Dat meest linkse lamp is de 128-bit. Dus 127 is eigenlijk gewoon alles van de andere gloeilampen, want dat is de meest linkse gloeilamp minus 1. Dat is het voor die vraag. 

Vraag één. Dus met 3 bits kunt u vertegenwoordigen 8 verschillende waarden. Waarom dan 7 de grootste niet-negatief decimale integer je kan vertegenwoordigen? Nou, als we kunnen alleen vertegenwoordigen 8 verschillende waarden, dan wat we gaan te zijn die is 0 tot 7. 0 neemt een van de waarden. 

Vraag twee. Met n bits, hoeveel verschillende waarden kunt u vertegenwoordigt? Dus, met n bits, je hebt 2 mogelijke waarden voor elke bit. Dus hebben we 2 mogelijke waarden voor de eerste bit, 2 mogelijke waarden voor de tweede, 2 mogelijk het derde. En dat is dus 2 maal 2 maal 2, en uiteindelijk is het antwoord op de 2 n. 

Vraag drie. Wat is 0x50 in binaire? Dus vergeet niet dat hexadecimale heeft een zeer eenvoudige conversie naar binair. Dus hier, we hoeven alleen maar te kijken naar de 5 en 0 onafhankelijk. Dus wat is 5 in binaire? 0101, dat is de 1 bit en 4 bit. Wat is 0 in binaire? Niet lastig. 0000. Dus gewoon zet ze samen, en dat is het volledige nummer in binaire. 01010000. En als je wilde kon je de start die meest linkse nul. Het is irrelevant. 

Dus dan als alternatief, wat is 0x50 in decimale? Als je wilde, je could-- als je meer comfortabel met het binaire, kon je dat binaire antwoord nemen en zetten die naar decimalen. Of we kunnen alleen niet vergeten dat hexadecimaal. Dus dat 0 is in de 0-e plaats, en de 5 in de 16 eerste plaats. Dus hier, hebben we 5 maal 16 tot de eerste, plus 0 maal 16 tot de nul, is 80. En als je keek naar de titel op de vraag, het was CS 80, wat voor soort was van een hint naar het antwoord op dit probleem. 

Vraag vijf. Wij hebben dit Scratch script, dat is herhalen 4 keer pindakaas gelei. Dus hoe kunnen we nu code die in C? Nou, we hebben hier-- het deel in het vet is het enige deel dat u moest implementeren. Dus we hebben een 4 lus die is looping 4 tijden, printf ing pindakaas gelei, met nieuwe lijn als het probleem vraagt. 

Vraag zes, een ander Scratch probleem. We zien dat we in een eeuwig lus. We zijn de variabele i zeggen en dan het verhogen i door 1. Nu willen we dat doen in C. Er zijn meerdere manieren kunnen we dit gedaan hebben. Hier gebeurde we om de code forever loop als een while (true). Dus we verklaren de variabele i, net alsof we variabele i in Scratch. Verklaar de variabele i, en voor altijd while (true), zeggen dat we de variabele i. Dus printf% I-- of je zou kunnen hebben gebruikt% d. We zeggen dat de variabele, en verhoog het dan, i ++. 

Vraag zeven. Nu willen we iets vergelijkbaars doen Mario dot c van probleem set één. We willen deze hashtags af te drukken, we willen afdrukken van een vijf door drie rechthoek deze hashes. Dus hoe gaan we dat doen? Nou, geven wij u een hele bos van code, en je gewoon hebben in de functie afdruk rooster in te vullen. 

Dus wat doet PrintGrid eruit? Nou, je bent voorbij de breedte en hoogte. Dus we hebben een buitenste 4 lus, dat is looping in alle rijen van deze raster dat we willen om uit te printen. Dan hebben we de inter-geneste 4 lus, dat is afgedrukt op een elke kolom. Dus voor elke rij is een afdruk voor elke kolom, een enkele hash. Dan aan het einde van de rij drukken wij een enkele nieuwe regel te gaan naar de volgende rij. En dat is het voor het hele net. 

Vraag acht. Een functie als PrintGrid schijt een neveneffect, maar geen terugkeer waarde. Verklaar het onderscheid. Dus dit op u vertrouwt het herinneren wat een bijwerking is. Nou ja, een terugkeer value-- we weten PrintGrid niet hebben return waarde, omdat hier het zegt leegte. Dus alles wat die leegte terugkeert niet echt iets terug. Dus wat is de bijwerking? Nou, een neveneffect is iets dat soort blijft bestaan nadat de functie eindigt dat was niet net terug, en het was niet alleen van de ingangen. 

Dus, bijvoorbeeld, kunnen we wijzigen van een globale variabele. Dat zou een neveneffect. In dit geval een zeer belangrijk neveneffect is het afdrukken op het scherm. Zodat een neveneffect dat PrintGrid heeft. Wij drukken deze dingen naar het scherm. En je kunt bedenken die als bijwerking, want dat is iets dat aanhoudt nadat deze functie beëindigt. Dat is iets wat buiten het toepassingsgebied van deze functie die uiteindelijk wordt gewijzigd, de inhoud van het scherm. 

Vraag negen. Beschouw onder het programma, waaraan regelnummers zijn toegevoegd Ter wille van de discussie. Dus in dit programma zijn we gewoon roepen GetString, slaan in deze variabele s, en vervolgens het afdrukken van die variabele s. OK. Dus waarom lijn niemand aanwezig is. #include CS50 dot h. Waarom moeten we #include CS50 dot h? Nou we het aanroepen van de GetString functie, en GetString wordt gedefinieerd in de CS50 bibliotheek. Dus als we niet hoefden #include CS50 dot h, we zouden dat impliciete verklaring krijgen van de GetString functie fout van de compiler. Dus moeten we de library-- bevatten we nodig hebben om de header-bestand bevatten, of anders de compiler zal niet erkennen dat GetString bestaat. 

Leg uit waarom lijn twee aanwezig is. Dus standaard io dot h. Het is precies hetzelfde de vorige oplossing, behalve in plaats van omgaan met GetString, we hebben het over printf. Dus als we niet zeggen dat we nodig hebben standaard io dot h omvatten, dan zouden we niet in staat zijn naar de printf functie te gebruiken, omdat de compiler zou het niet weten. 

Why-- wat is de betekenis van vervallen in lijn vier? Dus hier hebben we int main (void). Dat is gewoon te zeggen dat we krijgen geen command line argumenten naar main. Vergeet niet dat we int kon zeggen belangrijkste int argc touwtje argv beugels. Dus hier zijn we gewoon zeggen leegte te zeggen dat we negeren commandoregel argumenten. 

Leggen met betrekking tot geheugen, precies wat GetString in lijn zes rendementen. GetString is het terugsturen van een blok van geheugen, een reeks tekens. Het is echt het terugsturen van een pointer naar het eerste teken. Vergeet niet dat een string is een char ster. Dus s is een pointer naar de eerste karakter in welke de string dat de gebruiker op het toetsenbord ingevoerd. En dat geheugen toevallig malloced, dus dat het geheugen in de heap. 

Vraag 13. Beschouw het programma hieronder. Dus alles wat dit programma doet wordt printf-ing 1 gedeeld door 10. Zo worden opgesteld en uitgevoerde programma, uitgangen 0.0, hoewel 1 gedeeld door 10 is 0,1. Dus waarom is het 0.0? Nou, dit is omdat van integer divisie. Dus 1 een geheel getal, 10 een geheel getal is. So 1 gedeeld door 10, alles wordt beschouwd als gehele getallen, en in C, als we dat doen integer divisie, we afkappen elke komma. So 1 gedeeld door 10 0, en dan proberen we afdrukken die als float, zodat nul afgedrukt als een float is 0.0. En daarom krijgen we 0.0. 

Beschouw het programma hieronder. Nu zijn we het afdrukken van 0,1. Dus geen integer divisie, we zijn gewoon afdrukken 0.1, maar we zijn het af te drukken tot 28 cijfers achter de komma. En we krijgen dit 0,1000, een hele hoop nullen, 5 5 5, blah blah blah. Dus de vraag is hier waarom doet het afdrukken die plaats precies 0.1? 

Dus de reden is hier nu floating point onnauwkeurigheid. Vergeet niet dat een float is slechts 32 bits. Dus kunnen we alleen maar een eindig aantal vertegenwoordigen van floating point waarden met die 32 bits. Nou er is uiteindelijk oneindig veel floating point waarden, en er is oneindig veel zwevende punt waarden tussen 0 en 1, en we zijn uiteraard in staat om vertegenwoordigen nog meer waarden dan. Dus we moeten offers brengen om kunnen de meeste waarden vertegenwoordigen. 

Dus een waarde zoals 0.1, blijkbaar kunnen we niet garanderen dat precies. Dus in plaats van die 0.1 doen we het beste kunnen we dit 0.100000 5 5 vertegenwoordigen 5. En dat is aardig in de buurt, maar voor veel toepassingen je zorgen te maken over floating point onnauwkeurigheid, want we kunnen gewoon niet vertegenwoordigen alle zwevende punten precies. 

Vraag 15. Beschouw de onderstaande code. We zijn net het afdrukken van 1 plus 1. Dus er is geen truc. 1 plus 1 evalueert tot 2, en dan zijn we het afdrukken van dat. Hiermee wordt slechts 2. 

Vraag 16. Nu zijn we het afdrukken van het karakter 1 plus het karakter 1. Dus waarom is dit niet print het zelfde ding? Nou het karakter 1 plus het karakter 1, het karakter 1 heeft ASCII-waarde 49. Dus dit zegt echt 49 plus 49, en uiteindelijk dit gaat om af te drukken 98. Dus dit wordt niet afgedrukt 2. 

Vraag 17. Voltooiing van de uitvoering oneven hieronder zodanig dat de functie geeft true als n oneven en onwaar als n even is. Dit is een groot doel voor de mod operator. Dus nemen we ons argument n, als n mod 2 gelijk is aan 1, goed Dat betekent dat n verdeeld door 2 had een restant. Als n gedeeld door 2 had een restant, dat betekent dat n oneven is, dus we return true. Anders keren we vals. Je zou ook kunnen n hebben gedaan mod 2 gelijken nul, return false, anders return true. 

Beschouw het recursieve functie hieronder. Als n kleiner is dan of gelijk aan 1, return 1, anders return n keer f van n minus 1. Dus wat is de functie? Nou, dit is slechts het faculteit-functie. Dit is mooi vertegenwoordigd als n faculteit. 

Dus vraag 19 nu, we willen neem deze recursieve functie. We willen het iteratieve maken. Dus hoe kunnen we dat doen? Goed voor het personeel oplossing, en weer is er meerdere manieren je had kunnen doen dat, beginnen we met dit int product gelijk aan 1. En in dit hele lus, we gaan te product uiteindelijk vermenigvuldigen eindigen met de volledige faculteit. Dus voor int i is gelijk aan 2, i minder dan of gelijk aan n, i ++. 

U vraagt ​​zich misschien af ​​waarom ik gelijk aan 2. Nou, vergeet niet dat hier hebben we te zorg ervoor dat ons basisscenario correct is. Als n kleiner is dan of gelijk 1, we zijn net terug 1. Dus hier, we beginnen bij i is gelijk aan 2. Nou als ik waren 1, dan the-- of als n waren 1, dan is het voor de lus helemaal niet zou uitvoeren. En dus zouden we gewoon terugkeer product, dat is 1. Evenzo, als n zijn iets minder dan 1-- als het 0, 1 negatief, whatever-- we zouden nog steeds terugkeren 1, dat is precies wat de recursieve versie doet. 

Nu, als n groter dan 1, dan gaan we ten minste één do iteratie van deze lus. Dus laten we zeggen n 5 is, dan zijn we ga naar het product keer doen gelijk 2. Dus nu product is 2. Nu gaan we doen product keer is gelijk aan 3. Nu is 6. Product keer gelijk 4, nu is het 24. Product keer gelijk 5, nu is het 120. Dus dan uiteindelijk zijn we terug 120, die juist 5 faculteit is. 

Vraag 20. Dit is degene waar je moet invullen in de tabel met een bepaalde algoritme, alles wat we hebben gezien, dat past deze algoritmische run malen deze asymptotische doorlooptijden. Wat is een algoritme dat is omega van 1, maar big O van n? Dus oneindig kan veel antwoorden hier. Degene die we waarschijnlijk het meest heb gezien vaak is gewoon lineair zoeken. 

Dus in het beste geval scenario, het item dat we naar de begin van de lijst en zo in omega van 1 stappen, het eerste wat we checken, we gewoon onmiddellijk terug dat vonden we het item. In het worst case scenario, de functie bij het einde, of het item niet in de lijst op alle. Dus we moeten zoeken de hele lijst, alle n elementen, en dat is waarom het is o n. 

Dus nu is het iets dat zowel omega van n log n, en de grote O van n log n. Nou de meest relevante ding we hebben hier te zien is fuseren soort. Dus samenvoegen sorteren, onthouden, is uiteindelijk Theta n log n, waarbij theta gedefinieerd als zowel omega en grote O hetzelfde. Beide n log n. 

Wat is iets dat omega van n en o, van n kwadraat? Nou, nogmaals er is meerdere antwoorden mogelijk. Hier gebeuren we bubble sort zeggen. Insertion sort zou hier ook werken. Vergeet niet dat bubble sort heeft dat optimalisatie waar, als je in staat om te krijgen zijn de hele lijst zonder te doen elke swaps, dan, nou ja, we kunnen onmiddellijk terug te keren dat de lijst gesorteerd was om mee te beginnen. Dus in het beste geval, het is gewoon omega van n. Als het is niet alleen een mooi gesorteerde lijst om mee te beginnen, dan hebben we O van n kwadraat swaps. En tot slot hebben we selectie sorteren voor n kwadraat, zowel omega en grote O. 

Vraag 21. Wat is integer overflow? Weer goed, vergelijkbaar met eerdere, we hebben maar een eindig aantal stukjes een integer vertegenwoordigen dus misschien 32 bits. Laten we zeggen dat we een signed integer. Dan uiteindelijk de hoogste positief getal we kunnen vertegenwoordigen 2 tot 31 min 1. Dus wat gebeurt er als we proberen te vervolgens increment dat integer? Nou, we gaan om te gaan van 2 tot en met de 31 minus 1, helemaal naar beneden om negatieve 2 tot 31. Dus dit integer overflow is wanneer je blijft ophogen, en uiteindelijk kun je niet get any hoger en het gewoon wraps helemaal terug rond een negatieve waarde. 

Hoe zit het met een buffer overflow? Dus een buffer overflow-- herinneren wat een buffer is. Het is gewoon een stuk van het geheugen. Iets als een array is een buffer. Dus een buffer overflow is wanneer u probeert om toegang te krijgen tot het geheugen na het einde van die array. Dus als je een waaier van grootte 5 en je proberen om toegang te krijgen scala beugel 5 of beugel 6 of beugel 7, of iets verder dan de einde, of zelfs iets below-- scala beugel negatieve 1-- al die zijn buffer overflows. Je raakt het geheugen in slechte manieren. 

Vraag 23. Dus in dit degene die je nodig hebt te implementeren strlen. En wij zeggen jullie dat je kan veronderstellen s zal niet leeg zijn, zodat je niet hoeft te Voer een check voor null. Er zijn meerdere manieren kon je dit hebt gedaan. Hier nemen we gewoon het eenvoudig. We beginnen met een teller, n. n tellen hoeveel tekens er zijn. Dus beginnen we op 0, en dan hebben we itereren over de hele lijst. 

Is s 0 beugel gelijk aan de null terminator karakter? Vergeet niet dat we op zoek naar de null terminator karakter te bepalen hoe lang onze string. Dat gaat te beëindigen alle relevante string. Dus is s beugel 0 gelijk om de null terminator? Als het niet, dan gaan we naar kijken naar s beugel 1, s beugel 2. We blijven gaan tot we vind het null terminator. Zodra we het gevonden hebt, dan n bevat de totale lengte van de tekenreeks, en we kunnen gewoon terug dat. 

Vraag 24. Dus dit is het een waar je moeten de afweging maken. Dus een ding is goed in één manier, maar op welke manier is het slecht? Dus hier, samenvoegen soort heeft de neiging om zijn sneller dan bubble sort. Dat gezegd dat-- goed, er zijn hier meerdere antwoorden. Maar het belangrijkste is dat de bubble sort is omega van n voor een gesorteerde lijst. 

Vergeet niet dat de tafel we gewoon eerder zagen. Dus bel sorteert omega van n, het best case scenario is het is om iets meer te kunnen gaan de lijst een keer, bepalen hey dit ding is nu al gesorteerd en rendement. Samenvoegen sorteren, wat er ook gebeurt je doet, is het omega van n log n. Dus voor gesorteerde lijst, bel soort gaat sneller. 

Nu wat over gelinkte lijsten? Dus een gelinkte lijst kan groeien en krimpen zoveel elementen passen als nodig. Dat gezegd dat-- zo meestal directe vergelijking gaat worden een gekoppelde een lijst met een array. Dus hoewel arrays kunnen gemakkelijk groeien en krimpen om zoveel mogelijk elementen passen indien nodig, een gekoppelde lijst vergeleken met een array-- een array heeft random access. We kunnen indexeren in elke bepaald element van de array. 

Dus voor een gelinkte lijst, kunnen we niet ga je gewoon naar het vijfde element, We moeten doorkruisen van het begin tot we bij het vijfde element. En dat gaat ons te verhinderen iets als binary search doen. Spreken van binary search, binary search meestal sneller dan lineair zoekactie. Dat gezegd dat-- ja, één ding mogelijk is dat je niet binair kunnen doen zoeken op gelinkte lijsten, kunt u alleen doen op arrays. Maar wellicht nog belangrijker, kun je binary search niet doen op een array niet gesorteerd. Upfront moet u mogelijk om te sorteren de array, en alleen dan kan je doet binary search. Dus als je ding is niet gesorteerde om te beginnen, dan lineair zoeken zou sneller zijn. 

Vraag 27. Dus overweeg hieronder het programma, die in de volgende dia. En dit is de ene waar we zijn gaat willen expliciet te vermelden de waarden van verschillende variabelen. Dus laten we eens kijken naar dat. 

Dus regel één. We hebben int x gelijk aan 1. Dat is het enige wat er is gebeurd. Dus op lijn één, zien we in onze tafel, dat y, a, b en TMP zijn verduisterd. Dus wat is x? Nou we zojuist het gelijk is aan 1. En dan lijn twee, goed, we zien dat y is ingesteld op 2, en de tafel is al ingevuld voor ons. Dus x 1 is en y 2 is. 

Nu, lijn drie, we zijn nu binnen in de swap-functie. Wat deden we langs om te ruilen? We passeerden ampersand x voor een, en ampersand y voor b. Wanneer het probleem eerder verklaarde dat het adres van x is 0x10, en het adres van y is 0x14. Dus a en b gelijk zijn aan 0x10 en 0x14, respectievelijk. 

Nu op lijn drie, wat zijn x en y? Nou is er niets veranderd over x en y op dit punt. Ook al zijn ze in een grote stack frame, ze nog steeds dezelfde waarden voorheen. We hebben niet gewijzigd enkele herinnering. Dus x is 1, y is 2. Prima. Dus nu hebben we gezegd int tmp gelijk aan een ster. Dus op lijn vier, alles is hetzelfde, behalve voor tmp. We hebben geen waarden veranderd van om het even wat, behalve voor tmp. We zijn het instellen tmp gelijk aan een ster. Wat is een ster? Nou, een puntensysteem om x, So ster een gaat gelijk x, die 1. Dus alles wordt gekopieerd beneden en TMP ingesteld op 1. 

Nu is de volgende regel. Star een gelijk ster b. Dus door lijn five-- weer goed, alles is hetzelfde, behalve wat ster een is. Wat is een ster? Nou, we hebben net gezegd ster a x. Dus we veranderen x gelijke ster b. Wat is ster b? y. b punten op y. Dus ster b y. Dus we zijn het instellen van x gelijk is aan y, en al het andere is hetzelfde. Zo zien we in de volgende rij dat x is nu 2, en de rest zijn gewoon naar beneden gekopieerd. 

Nu in de volgende regel, ster b gelijk tmp. Nou, we hebben net gezegd ster b is y, dus we zijn het instellen van y gelijk aan tmp. Alles is hetzelfde, dus alles wordt gekopieerd naar beneden. We zijn het instellen van y gelijk aan tmp, dat is één, en al het andere is hetzelfde. 

Nu eindelijk, lijn zeven. We zijn terug in de belangrijkste functie. We zijn na swap is voltooid. We hebben a, b verloren, en tmp, maar uiteindelijk hebben we zijn geen waarden veranderen iets op dit punt, we gewoon kopiëren x en y naar beneden. En we zien dat x en y Nu 2 en 1 in plaats van 1 en 2. De swap heeft met succes uitgevoerd. 

Vraag 28. Stel dat je tegenkomt de foutmeldingen hieronder tijdens kantooruren volgend jaar als een CA of TF. Adviseren hoe elk van deze fouten te herstellen. Dus undefined verwijzing naar GetString. Waarom zou je dit zien? Nou, als een student wordt met behulp van GetString in hun code, ze hebben de juiste hash opgenomen CS50 dot h om de CS50 bibliotheek op te nemen. 

Nou, wat doen ze nodig hebt om deze fout te verhelpen? Ze moeten een dash lcs50 bij het doen command line als ze samenstellen. Dus als ze niet voorbij clang dash lcs50, ze zijn niet van plan om de werkelijke hebben code die GetString implementeert. 

Vraag 29. Impliciet verklaren bibliotheekfunctie strlen. Nou dit nu, ze hebben niet gedaan de juiste hash omvatten. In dit specifieke geval, de header file ze nodig hebben om onder meer is touwtje dot h, en met touwtje dot h, nu de student-- nu de compiler toegang tot de verklaringen van strlen, en hij weet dat je code correct gebruik van strlen. 

Vraag 30. Meer procent conversies dan gegevens argumenten. Dus wat is dit? Goed herinneren dat deze procent signs-- hoe ze relevant zijn voor printf bent. Dus in printf zouden we percent-- we misschien wel iets af te drukken zoals procent i Backslash n. Of we kunnen printen, zoals procent i, ruimte, procent i, ruimte, procent i. Dus voor elk van deze procenttekens moeten we om een ​​variabele gaat over op het einde van printf. 

Dus als we zeggen printf paren procent i backslash n dicht paren, goed, zeggen we dat we naar een integer drukken, maar dan doen we niet printf passeren een integer daadwerkelijk drukken. Dus hier meer procent omzettingen dan data argumenten? Dat zegt dat we een hele hoop van procenten, en we hebben niet genoeg variabelen om daadwerkelijk in die procenten invullen. 

En dan zeker, voor vraag 31, zeker verloren 40 bytes in één blokken. Dus dit is een Valgrind fout. Deze zegt dat ergens in je code, heb je een toewijzing die is 40 bytes groot dus je malloced 40 bytes, en je nooit bevrijd is. Waarschijnlijk heb je gewoon nodig hebt om wat geheugenlek vinden, en vinden waar je moet bevrijden dit blok van het geheugen. 

En vraag 32, ongeldige schrijfsnelheid van maat 4. Ook dit is een Valgrind fout. Dit hoeft niet te doen met memory leaks nu. Dit is de meeste likely-- Ik bedoel, het is een soort van ongeldige geheugen rechten. En het meest waarschijnlijk is dit aantal soort van buffer overflow. Waar heb je een array, misschien een integer array, en laten we zeggen dat het van maat 5, en je probeer scala beugel 5 raken. Dus als u probeert te schrijven naar die waarde, dat is niet een stuk van het geheugen dat u daadwerkelijk toegang hebben tot, en dus je gaat om deze fout te krijgen, zegt ongeldige write van maat 4. Valgrind gaat herkennen je bent proberen om het geheugen op ongepaste wijze te raken. 

En dat is het voor quiz0. Ik ben Rob Bowden, en dit is CS50.