ROB BOWDEN: Hi, ek is Rob Bowden, en laat ons praat oor quiz0. So, die eerste vraag. Dit is die vraag waar wat jy nodig het om die nommer te kodeer 127 in die binêre bolle. As jy wil, kan jy die gereelde omskakeling doen uit bi-- of uit desimale binêre. Maar dit is waarskynlik gaan 'n baie tyd te neem. Ek bedoel, jy kan uit te vind dat, OK, 1 is daar, 2 is daar, 4 is daar, 8 is daar in. Makliker manier, 127 128 minus een. Dit linker gloeilamp is die 128-bit. So 127 is eintlik net al van die ander gloeilampe, want dit is die linker gloeilamp minus 1. Dit is dit vir die vraag. 

Vraag een. So met 3 stukkies wat jy kan verteenwoordig 8 verskillende waardes. Waarom dan, is 7 die grootste nie-negatiewe desimale heelgetal jy kan verteenwoordig? Wel, as ons kan net verteenwoordig 8 verskillende waardes, dan wat ons gaan wees verteenwoordig is 0 tot 7. 0 neem een ​​van die waardes. 

Vraag twee. Met N stukkies, hoeveel duidelike waardes kan jy verteenwoordig? So, met N stukkies, jy het 2 moontlike waardes vir elke bietjie. So het ons 2 moontlike waardes vir die eerste bietjie, 2 moontlike waardes vir die tweede, 2 moontlik vir die derde. En so dit is 2 keer 2 keer 2, en Uiteindelik is die antwoord is 2 tot die n. 

Vraag drie. Wat is 0x50 in binêre? So onthou dat heksadesimale het 'n baie eenvoudige omskakeling na binêre. So hier het ons net nodig het om te kyk na 5 en die 0 onafhanklik. So, wat is 5 in binêre? 0101, dit is die 1 bietjie en die 4 bietjie. Wat is 0 in binêre? Nie lastig. 0000. So net sit hulle saam, en dit is die volle getal in binêre. 01.010.000. En as jy wil jy kan af dat linker nul. Dit is irrelevant. 

So dan alternatiewelik, Wat is 0x50 in desimale? As jy wil, kan jy could-- as jy meer gemaklik met die binêre, jy kan dat binêre antwoord neem en sit dit in desimaal. Of ons kan net onthou dat heksadesimale. Sodat 0 is in die 0-de plek, en die 5 is in die 16 tot die eerste plek. So hier het ons 5 keer 16 aan die eerste, plus 0 keer 16 tot die nul, 80. En as jy kyk na die titel op die vraag, dit was CS 80, wat was soort van 'n wenk aan die antwoord op hierdie probleem. 

Vraag vyf. Ons het hierdie Scratch script, wat herhaal 4 keer grondboontjiebotter gelei. So hoe kan ons nou kode wat in C? Wel, ons het here-- die deel in vet is die enigste deel wat jy het om te implementeer. So het ons 'n 4 lus wat is herhaling 4 tye, printf-ing grondboontjiebotter jellie, met 'n nuwe lyn as die probleem vra. 

Vraag ses ander Scratch probleem. Ons sien dat ons in 'n ewig lus. Ons sê die veranderlike i en dan die verhoog i deur 1. Nou wil ons dit doen in C. Daar is verskeie maniere waarop ons kon dit gedoen het. Hier het ons gebeur die die kode vir ewig lus as 'n rukkie (ware). So verklaar ons die veranderlike i, net soos ons moes veranderlike i in krap. Verklaar die veranderlike i, en vir ewig terwyl (true), sê ons die veranderlike i. So printf% i-- of jy kan gebruik het% d. Ons sê dat veranderlike, en dan inkrementeer, ek ++. 

Vraag sewe. Nou wil ons iets baie soortgelyks te doen Mario dot c van die probleem wat een. Ons wil hierdie hashtags te druk, Ons wil druk 'n vyf deur drie reghoek van hierdie twee velde. So hoe gaan ons dit doen? Wel, ons gee jou 'n hele n klomp van die kode, en jy net het in die gedrukte rooster funksie te vul. 

So wat beteken PrintGrid lyk? Wel, jy is verby die breedte en die hoogte. So ons het 'n buitenste 4 lus, dis herhaling oor al die rye van hierdie rooster wat ons wil uit te druk. Dan het ons die inter-sub-4 lus, dit is die druk oor elke kolom. So vir elke ry, ons druk vir elke kolom, 'n enkele hash. Dan aan die einde van die ry ons druk 'n enkele nuwe lyn te gaan na die volgende ry. En dit is dit vir die hele rooster. 

Vraag agt. 'N funksie soos PrintGrid word gesê 'n newe-effek, maar nie 'n terugkeer waarde. Verduidelik die onderskeid. So dit hang van jou onthou wat 'n newe-effek is. Wel, 'n terugkeer value-- ons weet PrintGrid nie het terugkeer waarde, aangesien hier sê dit nietig. So iets wat terugkeer nietig nie regtig terugkeer nie. So, wat is die newe-effek? Wel, 'n newe-effek is iets wat soort van voortduur na die funksie eindig dit was nie net terug, en dit was nie net uit die insette. 

So, byvoorbeeld, kan ons verander 'n globale veranderlike. Dit sou 'n newe-effek wees. In hierdie spesifieke geval, 'n baie belangrik newe-effek is die druk op die skerm. So dit is 'n newe-effek dat PrintGrid het. Ons druk hierdie dinge aan die skerm. En jy kan dink wat as 'n newe-effek, want dit is iets wat voortduur na hierdie funksie eindig. Dit is iets wat buite die omvang van hierdie funksie wat uiteindelik word verander, die inhoud van die skerm. 

Vraag nege. Oorweeg die onderstaande program, waaraan lyn nommers is bygevoeg vir ter wille van die bespreking. So in hierdie program ons is net roep GetString, om dit te stoor in hierdie veranderlike s, en dan druk dat veranderlike s. OK. So verduidelik waarom lyn een is teenwoordig. # include cs50 dot h. Hoekom moet ons cs50 dot h te include? Wel ons is die roeping van die GetString funksie, en GetString word gedefinieer in die cs50 biblioteek. So as ons het nie # include cs50 dot h, Ons wil hê dat die implisiete verklaring kry van die GetString funksie fout uit die samesteller. Dus moet ons die library-- te sluit Ons moet die kop lêer in te sluit, of anders sal die samesteller sal nie erken dat GetString bestaan. 

Verduidelik waarom lyn twee is teenwoordig. So standaard io dot h. Dit is presies dieselfde as die vorige probleem, behalwe in plaas van die hantering van GetString, ons praat oor die printf. So as ons nie sê dat ons moet standaard io dot h in te sluit, dan sou ons nie in staat wees om die printf funksie te gebruik, omdat die samesteller sou nie weet nie. 

Why-- wat is die betekenis van nietig in lyn vier? So hier het ons int main (void). Dit is net te sê dat ons is nie om enige opdrag lyn argumente na. Onthou dat ons kan sê int hoof int argc string argv hakies. So hier het ons net sê nietig ons om te sê ignoreer command line argumente. 

Verduidelik, met betrekking tot die geheue, presies wat GetString in lyn ses opbrengste. GetString terugkeer 'n blok van geheue, 'n verskeidenheid van die karakters. Dit is regtig 'n terugkeer wyser na die eerste karakter. Onthou dat 'n string is 'n char ster. So s is 'n verwysing na die eerste karakter in ongeag die string is dat die gebruiker aangegaan op die sleutelbord. En dat die geheue gebeur malloced word, sodat die geheue is in die hoop. 

Vraag 13. Oorweeg die program hieronder. So al hierdie program is om te doen is printf-ing 1 gedeel deur 10. So wanneer saamgestel en uitgevoer word, hierdie program uitsette 0.0, selfs al 1 gedeel deur 10 is 0.1. So hoekom is dit 0,0? Wel, dit is omdat van heelgetal afdeling. So 1 'n heelgetal is, 10 is 'n heelgetal. So 1 gedeel deur 10, alles behandel word as heelgetalle, en in C, wanneer ons dit doen heelgetal afdeling, ons afgestomp enige desimale punt. So 1 gedeel deur 10 is 0, en dan moet ons probeer wat om te druk as 'n vlot, so nul gedruk as 'n float is 0.0. En dit is hoekom ons 0.0. 

Oorweeg die program hieronder. Nou kan ons die druk van 0.1. Sodat daar geen heelgetal afdeling, ons is maar net die druk van 0.1, maar ons druk dit tot 28 desimale plekke. En ons kry hierdie 0,1000, 'n hele klomp nulle, 5 5 5, blah blah blah. So die vraag hier is hoekom doen dit druk dat, in plaas van presies 0,1? 

So die rede hier is nou drywende punt onakkuraatheid. Onthou dat 'n float is slegs 32 stukkies. So kan ons net 'n beperkte aantal verteenwoordig drywende punt waardes met dié 32 stukkies. Wel, daar is uiteindelik oneindig baie swaai punt waardes, en daar is oneindig baie swaai punt waardes tussen 0 en 1, en ons is natuurlik in staat te verteenwoordig nog meer waardes as dit. Dus het ons opofferings te maak om in staat wees om die meeste waardes te verteenwoordig. 

So 'n waarde soos 0,1, blykbaar Ons kan nie voorgee dat presies. So in plaas van wat ons doen om die 0,1 beste wat ons kan verteenwoordig hierdie 0.100000 5 5 5. En dit is redelik naby, maar vir 'n baie aansoeke jy hoef te bekommer oor drywende punt onakkuraatheid, want ons kan net nie verteenwoordig al swaai punte presies. 

Vraag 15. Oorweeg die kode hieronder. Ons is net die druk van 1 plus 1. So daar is geen truuk hier. 1 plus 1 evalueer tot 2, en dan is ons druk nie. Dit druk net 2. 

Vraag 16. Nou kan ons die karakter druk 1 plus die karakter 1. So hoekom doen dit nie druk die dieselfde ding? Wel, die karakter 1 plus die karakter 1, die karakter 1 het ASCII waarde 49. So is dit regtig sê 49 plus 49, en Uiteindelik gaan druk 98. So dit beteken nie druk 2. 

Vraag 17. Voltooi die implementering van vreemde hieronder in so 'n manier dat die funksie gee terug waar as N is vreemd en vals as n ewe is. Dit is 'n groot doel vir die mod-operateur. So neem ons ons argument n, As n mod 2 is gelyk aan 1, goed dit beteken dat n verdeelde deur 2 het 'n res. As N gedeel deur 2 het 'n res, wat beteken dat n is vreemd, so ons terugkeer waar. Anders moet ons terugkeer vals. Jy kan ook gedoen het N mod 2 gelykes nul, terugkeer vals, anders terugkeer waar. 

Oorweeg die rekursiewe funksie hieronder. So as n minder as of gelyk aan 1, terug 1 anders terugkeer n keer f van N minus 1. So, wat is hierdie funksie? Wel, dit is net die faktoriaal funksie. Dit is mooi verteenwoordig as N faktoriaal. 

So Vraag 19 nou, ons wil neem hierdie rekursiewe funksie. Ons wil dit iteratiewe te maak. So, hoe doen ons dit? Wel, vir die personeel oplossing, en weer daar verskeie maniere waarop jy kon gedoen het dat ons begin met hierdie int produk gelyk 1. En deur hierdie lus, ons gaan word vermenigvuldig produk om uiteindelik eindig met die volle faktoriaal. So vir int i gelyk aan 2, i is minder as of gelyk aan n, i ++. 

Jy mag dalk wonder hoekom ek gelyk 2. Wel, onthou dat ons hier te maak seker dat ons basis geval korrek is. So as n minder as of gelyk 1, ons is net terug 1. So hier het ons begin by i gelyk aan 2. Wel, as ek was 1, dan the-- of As N 1 was, dan is die lus sou dit nie uitvoer nie. En so sou ons net terugkeer van die produk, wat is 1. Net so, as n was niks minder as 1-- As dit was 0, negatiewe 1, whatever-- wil ons nog terugkeer 1, dit is presies wat die rekursiewe weergawe doen. 

Nou, as n groter as 1, dan is ons gaan ten minste een om te doen iterasie van hierdie lus. So kom ons sê N 5 is, dan is ons gaan produk keer te doen is gelyk aan 2. So nou produk is 2. Nou het ons gaan doen produk tye gelyk aan 3. Nou is dit 6. Produk tye gelyk aan 4, nou is dit 24. Produk tye gelyk aan 5, nou is dit 120. So dan uiteindelik, ons terugkeer 120, wat korrek 5 faktoriaal. 

Vraag 20. Dit is die een waar jy hê om te vul in hierdie tabel met enige gegewe algoritme, iets wat ons gesien het, wat pas hierdie algoritmiese run keer hierdie asimptotiese run tye. So, wat is 'n algoritme wat is omega van 1, maar groot O van n? So kan daar oneindig wees baie antwoorde hier. Die een wat ons het waarskynlik die meeste gesien dikwels net lineêre soek. 

So in die beste geval scenario, die item is ons soek, is by die begin van die lys en so in omega van 1 stappe, die eerste ding wat ons gaan, Ons het net dadelik terug dat ons die item. In die ergste geval scenario, die item is aan die einde, of die orde is nie in die lys nie. So ons het om te soek die hele lys, alle n elemente, en dit is waarom dit is o van n. 

So nou is dit iets wat beide omega van N log N, en 'n groot O van n log n. Wel, die mees relevante ding Ons het hier gesien is saamsmelt soort. So saamsmelt soort, onthou, uiteindelik Theta N log N, waar theta word gedefinieer indien beide omega en 'n groot O is dieselfde. Beide N teken n. 

Wat is iets wat omega van N, en O van n vierkant? Wel, weer daar verskeie moontlike antwoorde. Hier gebeur ons om te sê borrel soort. Invoeging soort sal ook hier werk. Onthou dat borrel soort het dat die optimalisering waar, As jy in staat is om te kry deur die hele lys sonder om te doen enige swaps, dan, wel, ons kan onmiddellik dat Die lys is gesorteer te begin. So in die beste geval, dit is net omega van n. As dit is nie net 'n mooi gesorteer lys om te begin, dan het ons O van n vierkant verteenwoordig. En uiteindelik, ons het seleksie soort vir n vierkant, sowel omega en 'n groot O. 

Vraag 21. Wat is integer oorloop? Weer goed, soortgelyk aan vroeër, ons het net eindig baie stukkies 'n heelgetal te verteenwoordig, so miskien 32 stukkies. Kom ons sê ons het 'n getekende heelgetal. Dan uiteindelik die hoogste positiewe getal kan ons verteenwoordig 2 aan die 31 minus 1. So wat gebeur as ons probeer om te dan inkrementeer dat heelgetal? Wel, ons gaan om te gaan van 2 tot 31 minus 1, al die pad af na 'n negatiewe 2 aan die 31. So hierdie integer oorloop is wanneer jy hou die verhoog, en uiteindelik kan jy nie kry 'n hoër en dit net vou al die pad terug om 'n negatiewe waarde. 

Wat van 'n buffer oorloop? So 'n buffer overflow-- onthou wat 'n buffer is. Dit is net 'n stuk van die geheue. Iets soos 'n skikking is 'n buffer. So 'n buffer oorloop is wanneer jy probeer om die geheue te bekom na die einde van die skikking. So as jy 'n verskeidenheid van grootte 5 en jy probeer skikking bracket om toegang te verkry 5 of bracket 6 of bracket 7, of enigiets buite die einde, of selfs enigiets below-- verskeidenheid bracket negatiewe 1-- almal is buffer oorloop. Jy raak geheue in slegte maniere. 

Vraag 23. So in hierdie een wat jy nodig het strlen te implementeer. En ons vertel dat jy kan aanvaar s sal nie nul wees nie, sodat jy nie hoef te doen 'n tjek vir nul. En daar is verskeie maniere jy kon dit gedoen het. Hier het ons net die eenvoudige. Ons begin met 'n toonbank, n. N is tel hoeveel karakters daar is. So het ons begin by 0, en dan moet ons Itereer oor die hele lys. 

Is s bracket 0 gelyk is aan die nul terminator karakter? Onthou ons is op soek na die nul terminator karakter om te bepaal hoe lank ons ​​string is. Dit gaan staak enige relevante string. So is s bracket 0 gelyke om die nul terminator? As dit is nie, dan is ons gaan kyk na s bracket 1, s bracket 2. Ons hou gaan totdat ons vind die nul terminator. Sodra ons dit gevind het, dan N bevat die totale lengte van die string, en ons kan net terug nie. 

Vraag 24. So, dit is die een waar jy het die handel af te maak. So een ding is goed in een manier, maar hoe is dit sleg? So hier, saam te smelt soort geneig is om te wees vinniger as borrel soort. Dit gesê that-- Wel, daar is verskeie antwoorde hier. Maar die belangrikste een is dat borrel soort is omega van N vir 'n gesorteerde lys. 

Onthou dat tafel het ons net vroeër gesien het. So borrel sorteer omega van N, die beste scenario is dit in staat is om te gaan net oor die lys weer, bepaal hey hierdie ding is reeds gesorteer, en terugkeer. Merge soort, maak nie saak wat wat jy doen, is omega van N log N. So vir gesorteerde lys, borrel soort gaan vinniger. 

Nou wat van geskakelde lyste? So 'n geskakelde lys kan groei en krimp soveel elemente te pas soos nodig. Dit gesê that-- so gewoonlik die direkte vergelyking gaan wees om 'n verband lys met 'n verskeidenheid. So selfs al skikkings kan maklik groei en krimp soveel elemente aan te pas as dit nodig is, 'n geskakelde lys in vergelyking met 'n array-- 'n skikking het ewetoeganklike. Ons kan kruip in 'n spesifieke element van die skikking. 

So vir 'n geskakelde lys, kan ons nie gaan net na die vyfde element, Ons het om oor te steek van die begin af totdat ons na die vyfde element. En wat gaan ons om te verhoed om iets te doen soos binêre soek. Praat van binêre soek, binêre soek geneig is om vinniger as lineêre soek wees. Dit gesê that-- so, een moontlike ding is dat jy nie binêre kan doen soek op geskakelde lyste, jy kan dit net op skikkings. Maar waarskynlik meer belangrik, jy kan dit nie doen binêre soek op 'n skikking wat nie gesorteer. Upfront jy dalk nodig het om te sorteer die skikking, en dan slegs kan jy doen binêre soek. So as jou ding is nie gesorteer om te begin, dan lineêre soek dalk vinniger wees. 

Vraag 27. So kyk na die program hieronder, wat sal wees in die volgende skuif. En dit is die een waar ons is gaan om te wil uitdruklik die waardes vir die verskillende veranderlikes. So laat ons kyk na dit. 

So lyn een. Ons het int x is gelyk aan 1. Dit is die enigste ding wat gebeur het. So op lyn een, sien ons in ons tafel, y, a, b, en tmp is al bewussyn verloor. So, wat is x? Wel, ons het net stel dit gelyk aan 1. En dan word twee, goed, sien ons dat y is ingestel op 2, en die tafel is reeds gevul in vir ons. So x is 1 en y 2. 

Nou, lyn drie, het ons nou is binne-in die ruil-funksie. Wat het ons verby te ruil? Ons geslaag ampersand x a, en ampersand y vir b. Waar die probleem vroeër verklaar dat die adres van x is 0x10, en die adres van y is 0x14. So A en B is gelyk aan 0x10 en 0x14, onderskeidelik. 

Nou op lyn drie, wat x en y? Wel, niks het verander oor x en y op hierdie punt. Selfs al is hulle binne 'n hoof stapel raam, hulle nog steeds dieselfde het waardes wat hulle gedoen het voor. Ons het nie verander nie die geheue. So x is 1, y 2. Alle regte. So nou het ons gesê int tmp gelyk om 'n ster. So op reël vier, alles is dieselfde, behalwe vir tmp. Ons het nie enige waardes verander van enigiets behalwe vir tmp. Ons is besig tmp gelyk om 'n ster. Wat is 'n ster? Wel, 'n punte x, So ster 'n gaan gelyk x, wat is 1. So alles is gekopieer af, en tmp is ingestel op 1. 

Nou is die volgende reël. Star 'n gelyk ster b. So deur die lyn five-- weer goed, alles is dieselfde, behalwe alles ster 'n is. Wat is 'n ster? Wel, ons het net gesê star a x. So ons is besig om x te gelyk ster b. Wat is ster b? y. b punte y. So ster b y. So ons is die opstel van x gelyk aan y, en alles is dieselfde. So sien ons in die volgende ry dat x is nou 2, en die res is net gekopieer. 

Nou in die volgende lyn, ster b is gelyk aan tmp. Wel, ons het net gesê ster b y, so ons is die opstel van y gelyk aan tmp. Alles is dieselfde, sodat alles raak gekopieer. Ons is die opstel van y gelyk aan TMP, wat een, en alles is dieselfde. 

Nou uiteindelik, lyn sewe. Ons is terug in die belangrikste funksie. Ons is na ruil klaar is. Ons het verloor A, B, en tmp, maar uiteindelik het ons is nie die verandering van enige waardes enigiets op hierdie punt, Ons het net kopieer x en y neer. En ons sien dat x en y nou 2 en 1 in plaas van 1 en 2. Die omruil het suksesvol uitgevoer word. 

Vraag 28. Veronderstel dat jy teëkom die fout boodskappe hieronder gedurende kantoorure volgende jaar as 'n GR of TF. Adviseer oor hoe om elk van hierdie foute op te los. So ongedefinieerde verwysing na GetString. Hoekom kan jy sien dit? Wel, as 'n student die gebruik van GetString in hulle kode, hulle het behoorlik ingesluit hash cs50 dot h die cs50 biblioteek in te sluit. 

Wel, wat doen hulle moet hierdie fout op te los? Hulle moet 'n bietjie lcs50 by die te doen command line wanneer hulle die opstel van. So as hulle nie slaag nie klang Dash lcs50, hulle is gaan nie die werklike te hê kode wat implemente GetString. 

Vraag 29. Onvoorwaardelik verklaar biblioteek funksie strlen. Wel, dit nou, hulle het nie gedoen om die behoorlike hash sluit. In hierdie spesifieke geval, die kop lêer wat hulle nodig het in te sluit is string dot h, en met string dot h, nou die student-- nou die samesteller het toegang tot die verklarings van strlen, en weet dat jou kode gebruik StrLen korrek. 

Vraag 30. Meer persent doelskoppe as data argumente. So, wat is dit? Wel onthou dat hierdie persent signs-- hoe hulle betrokke te printf. So in printf ons kan percent-- ons iets druk soos persent i agteroorskuinsstreep n. Of ons kan druk soos persent i, ruimte, persent i, ruimte, persent i. So vir elk van dié persent tekens, moet ons 'n veranderlike te slaag aan die einde van printf. 

So as ons sê printf hakie persent Ek agteroorskuinsstreep n noue paren, Wel, ons sê dat ons gaan 'n heelgetal te druk, Maar dan moet ons printf nie slaag nie 'n heelgetal te eintlik druk. So hier meer persent doelskoppe as data argumente? Dit sê dat ons 'n hele klomp van Procenten, en ons het nie genoeg veranderlikes het nie om werklik vul die persente. 

En dan beslis vir vraag 31, beslis verloor 40 grepe in een blokke. So dit is 'n Valgrind fout. Dit word gesê dat iewers in jou kode, jy het 'n toekenning wat 40 grepe groot sodat jy malloced 40 grepe, en jy nooit bevry nie. Heel waarskynlik het jy net nodig sommige geheugenlek te vind, en vind waar jy nodig het om te vry om hierdie blok van die geheue. 

En die vraag 32, ongeldig skryf van grootte 4. Weereens is dit 'n Valgrind fout. Dit hoef nie te doen met die geheue lekkasies nou. Dit is die meeste likely-- Ek bedoel, is dit 'n soort van ongeldig geheue regte. En waarskynlik dit is 'n soort buffer oorloop. Waar jy 'n skikking, miskien 'n heelgetal skikking, en laat ons sê dit is van groot 5, en jy probeer skikking bracket 5 aan te raak. So as jy probeer om dit te skryf waarde, dit is nie 'n stuk van die geheue dat jy eintlik toegang te hê, en so jy gaan hierdie fout te kry, sê ongeldig skryf van grootte 4. Valgrind gaan om te erken dat jy probeer geheue te onvanpas raak. 

En dit is dit vir quiz0. Ek is Rob Bowden, en dit is CS50.