ROB BOWDEN: Ahoj, ja som Rob Bowden, a poďme hovoriť o quiz0. Takže, prvá otázka. To je otázka, kde ste potrebovali na kódovanie čísla 127 v binárnej žiarovky. Ak by ste chceli, mohli by ste robiť pravidelnú konverziu od bi-- alebo z desiatkovej do binárnej. Ale to asi bude vziať veľa času. Myslím, že by ste mohli prísť na to, OK, 1 je tam, 2 je tam, 4 je tam, 8 je tam. Jednoduchší spôsob, 127 128 mínus jedna. To vľavo žiarovka je 128-bit. Takže 127 je naozaj len všetko ostatných žiaroviek, pretože to je vľavo žiarovka mínus 1. To je pre túto otázku. Otázka prvá. Tak s 3 bity môžete predstavujú 8 odlišné hodnoty. Prečo je teda 7 najväčší non-negatívne desatinné číslo môžete reprezentovať? No, keď sme len možné predstavujú 8 odlišné hodnoty, potom, čo budeme mať predstavuje 0 až 7. 0 zaberá jednu z hodnôt. Otázka dva. S n bitov, koľko zreteľný Hodnoty môžete reprezentovať? Takže s n bitov, máte 2 Možné hodnoty pre každý bit. Takže máme dve možné hodnoty pre prvý bit, 2 možné hodnoty za druhé, 2 možné, aby tretinu. A tak to je 2 krát 2 krát 2, a nakoniec odpoveď je 2 až n. Otázka tri. Čo je 0x50 v binárnej? Takže pamätajte, že hexadecimálne má veľmi jednoduchý prevod do dvojkovej sústavy. Tak tu, len je potrebné sa pozrieť na 5 a 0 nezávisle na sebe. Takže to, čo je 5 v binárnej? 0101, to je 1 bit a 4-bitová. Čo je 0 v binárnej? Nie je zložité. 0000. Takže len dať dohromady, a že je plný počet v binárnej. 01010000. A ak by ste chceli by ste mohli vzlietnuť, že úplne vľavo nulu. Je to irelevantné. Takže alternatívne, čo je 0x50 v desiatkovej sústave? Ak by ste chceli, môžete could-- ak ste viac vyhovuje binárne, môžete vziať, že binárne odpoveď a previesť to do desiatkovej. Alebo by sme mohli len spomenúť že šestnástkové. Takže je 0 v 0-tom mieste, a 5 je vo 16 na prvé miesto. Tak tu máme 5 krát 16 k Prvý, plus 0 krát 16 na nulu, je 80. A ak ste sa pozrel na Nárok na otázku, to bol SK 80, ktorý bol druh nápoveda k odpovedi na tento problém. Otázka päť. Máme tu Scratch skript, ktorý je opakovať 4 krát arašidové maslo želé. Tak ako sa teraz kód v C? No, máme here-- časť tučne je jediná časť, ktorú má za úlohu vykonať. Takže máme štyri slučky, ktorá je opakovanie 4 doba, printf-ing arašidové maslo želé, s novou linkou, ako tento problém žiada. Otázka šesť, ďalší problém Scratch. Vidíme, že sme v navždy slučky. Hovoríme, že premenná i a zvyšovanie aj o 1. Teraz chceme robiť, že v C existujú viac spôsobov, ako to mohol urobiť. Tu sa stalo kód navždy slučka ako while (true). Tak sme sa vyhlásiť, že premenná i, len ako by sme mali premennej i poškrabaniu. Vyhlásiť, že premenná i, a navždy while (true), hovoríme, že premenná i. Takže printf% Já-- alebo mohol si použiť% d. Hovoríme, že premenná, a potom ju zvýšiť, i ++. Otázka sedem. Teraz chceme urobiť niečo veľmi podobného Mario dot c od problému nastaviť jednu. Chceme vytlačiť tieto hashtag, Ak chceme vytlačiť päť o tri obdĺžnika týchto hash. Tak ako budeme robiť, že? No, my sme vám celý banda kódu, a práve je potrebné vyplniť vo funkcii tlačového rastra. Tak čo PrintGrid vyzerať? No vy ste v minulosti šírku a výšku. Takže máme vonkajšiu 4 slučky, ktorá je smyčkování cez všetky riadky tohto grid, že chceme vytlačiť. Potom máme medzi vnorené 4 slučky, to je tlač v každom stĺpci. Takže pre každý riadok, máme pre tlač každý stĺpec, jeden hash. Potom sa na konci riadku sme vytlačiť jeden nový riadok prejdete na ďalší riadok. A to je pre celé siete. Otázka osem. Funkcie ako PrintGrid je povedal, aby majú vedľajšie účinky, ale nie návrat hodnotu. Vysvetlite rozdiel. Takže to závisí na vás pamätať čo je to vedľajší účinok je. No, návrat value-- Vieme PrintGrid nie je mať návratovú hodnotu, pretože tu sa hovorí, že neplatné. Takže všetko, čo sa vracia void nie je naozaj nič vracať. Takže to, čo je vedľajší efekt? No, vedľajším účinkom je niečo, čo trochu pretrváva po ukončením funkcie že to nie je len vrátil, a to nielen z vstupov. Tak, napríklad, môžeme zmeniť globálnu premennú. To by bol vedľajší efekt. V tomto konkrétnom prípade, veľmi dôležitý vedľajší efekt tlačí na obrazovku. Takže to je vedľajším účinkom že PrintGrid má. Tlačíme tieto veci na obrazovke. A na čo si spomeniete že ako vedľajší efekt, pretože to je niečo, čo pretrváva aj po tejto funkcie skončí. To je niečo, čo nepatrí do pôsobnosti tejto funkcie, ktorá v konečnom dôsledku sa zmenil, Obsah obrazovky. Otázka deväť. Zvážte program nižšie, ku ktorému čísla riadkov boli pridané pre saké diskusie. Takže v tomto programe sme len volanie getString, uložením do tejto premennej s, a potom tlač tejto premennej s. OK. Tak vysvetľujú, prečo je prítomné množstvo raz. #include CS50 bodka h. Prečo musíme #include CS50 dot h? Tak sme volaní GetString funkcie, a GetString je definovaný v knižnici CS50. Takže ak sme nemali #include CS50 bodka h, by sme sa dostali, že implicitné vyhlásenia chyby funkcie GetString od kompilátora. Takže musíme zahrnúť library-- musíme zahrnúť hlavičkový súbor, inak kompilátor nebude uznávajú, že GetString existuje. Vysvetlite, prečo je prítomná rad dve. Takže štandardné io bodka h. Je to úplne rovnaké ako je vyššie uvedené problémy, s výnimkou toho, vysporiadať sa s GetString, hovoríme o printf. Takže ak sme nepovedali potrebujeme zahrnúť štandardné io dot h, potom by sme neboli schopní použiť funkciu printf, pretože kompilátor by o tom vedieť. Why-- aký je význam o stratu v rade štyri? Tak a máme tu int main (void). To je len hovorím, že sme nedostávajú žiadnu príkazového riadku Argumenty hlavné. Pamätajte si, že by sme mohli povedať, int Hlavné int argc reťazec argv zátvorky. Tak sme tu len povedať, void, že sme ignorujú argumenty príkazového riadku. Vysvetlenie, s ohľadom na pamäti, presne čo GetString v rade šesť vráti. GetString vracia blok pamäť, pole znakov. Je to naozaj vracia ukazovateľ na prvý znak. Pamätajte si, že reťazec char hviezda. Takže s je ukazovateľ na prvý charakter v akejkoľvek reťazec že užívateľ zadal na klávesnici. A že pamäť sa stane byť malloced, tak, že pamäť je v halde. Otázka 13. Uvažujme programu nižšie. Takže všetko, čo tento program robí je printf-ing 1 deleno 10. Takže keď zostavil a vykonaný, tento program výstupy 0.0, aj keď 1 deleno 10 je 0,1. Tak prečo je to 0.0? No, je to preto, celočíselného delenia. Tak je celé číslo 1, 10 je celé číslo. Takže 1 delené 10, všetko je zaobchádzané ako celé čísla, a C, keď budeme robiť celočíselné delenie, sme skrátiť akékoľvek desatinnou čiarkou. Takže 1 deleno 10 je 0, a potom sa snažíme vytlačiť to ako float, tak nula vytlačiť ako plavák je 0.0. A to je dôvod, prečo sme si 0.0. Uvažujme programu nižšie. Teraz sme tlač 0.1. Takže bez delení, sme len tlače 0,1, ale my sme ho tlače 28 desatinných miest. A my sme si to 0,1000, celá partia núl, 5 5 5, bla bla bla. Otázkou teda je, prečo to robí vytlačiť to, že namiesto toho, presne 0,1? Takže tu dôvod, prečo je teraz s plávajúcou desatinnou čiarkou nepresnosť. Pamätajte si, že plavák je iba 32 bitov. Takže môžeme predstavovať iba konečný počet plávajúce bodovej hodnoty s tými 32 bitov. No tam je nakoniec nekonečne Mnoho plávajúce bodové hodnoty, a tam je nekonečne veľa plávajúce bodové hodnoty v rozmedzí 0 až 1, a my sme samozrejme schopní predstavujú aj viac hodnôt, než to. Takže musíme prinášať obete, aby bolo možné reprezentovať väčšinu hodnoty. Takže hodnota ako 0,1, zrejme nemôžeme predstavovať, že presne. Takže namiesto toho, čo predstavuje 0,1 robíme najlepšie, čo môžeme reprezentovať túto 0.100000 5 5 5. A to je celkom blízko, ale pre mnoho aplikácií budete musieť starať o s plávajúcou desatinnou čiarkou nepresnosť, pretože sme jednoducho nemôže predstavovať všetko plávajúce body presne. Otázka 15. Zvážte pod kód. Sme len tlač 1 + 1. Takže tam nie je žiadny trik tu. 1 plus 1 vyhodnocuje 2, a potom tlačíte, že. To len vytlačí 2. Otázka 16. Teraz sme tlač znaku 1 plus 1 znak. Tak prečo to nie je vytlačiť to isté? No postava 1 plus znak 1 znak 1 má hodnotu ASCII 49. Tak toto je naozaj hovorí, 49 a 49, a nakoniec to bude tlačiť 98. Takže to netlačí 2. Otázka 17. Dokončiť vykonávanie nepárnych pod takým spôsobom, že funkcia vracia hodnotu true v prípade, n je nepárne a false, pokiaľ je n párne. To je skvelý účel pre mod operátora. Tak sme sa vziať naše argument n, ak n mod 2 sa rovná 1, dobre to znamená, že n delí o 2 mal zvyšok. Ak je n deleno 2 mal zvyšok, ktorý Znamená to, že n je nepárne, a tak sme sa vrátiť true. Inak sa vrátime false. Tiež to mohol urobiť n mod 2 rovná nula, vráti false, inak vráti hodnotu true. Zvážte rekurzívne funkcie nižšie. Takže ak n je menšie ako alebo rovný 1, vráti 1, iný návrat n-krát f n mínus 1. Takže to, čo je táto funkcia? No, je to len faktoriál funkcie. To je dobre zastúpená ako n faktoriál. Takže otázka 19 teraz, chceme tento rekurzívny funkciu. Chceme, aby to iteratívny. Tak ako to urobíme? No pre zamestnancov riešenie, a opäť je tu viac spôsobov, ako to mohol urobiť že sme sa začať s týmto produktom int sa rovná 1. A v celom tomto slučky for, ideme k násobenie produkt nakoniec skončiť s plnou faktoriálu. Takže pre int i sa rovná 2, aj je menšie alebo rovné n, i ++. Tie by mohli byť čudujete, prečo som sa rovná 2. No, pamätajte, že tu musíme uistite sa, že naša základňa prípad je v poriadku. Takže ak n je menšie alebo rovné 1, sme len vracia 1. Tak tu sme sa začať na i rovná 2. No, ak by som mal 1, potom the-- alebo ak n bola 1, potom pre sláčiky by sa vykonávať vôbec. A tak by sme len návrat produkt, ktorý je 1. Podobne, pokiaľ je n boli niečo menej ako 1-- keby to bolo 0, negatívne 1, whatever-- mohli by sme sa vracia 1, čo je presne to, čo rekurzívne verzia robí. Teraz, keď n je väčšie ako 1, potom budeme urobiť aspoň jednu iterácia tejto slučky. Takže povedzme, že n je 5, potom sme robiť časy produktu sa rovná 2. Takže teraz Produkt je 2. Teraz budeme robiť Časy produkt rovná 3. Teraz je to 6. Časy produktu sa rovná 4, teraz je to 24. Časy produktu sa rovná 5, teraz je to 120. Takže nakoniec vraciame 120, ktorý je správne 5 faktoriál. Otázka 20. To je ten, kde je nutné vyplniť V tejto tabuľke sa daný algoritmus, niečo, čo sme videli, že hodia tieto algoritmické beh Časy tieto asymptotickej dobu chodu. Takže to, čo je algoritmus, ktorý je omega 1, ale veľký O n? Takže tam môže byť nekonečne veľa odpovedí tu. Ten, ktorý sme videli asi najviac Často je len lineárne hľadanie. Takže v najlepšom prípade scenár, bod sme hľadá je začiatku zoznamu a tak v omega 1 krokov, Prvá vec, ktorú sme sa zistiť, práve sme okamžite vrátiť že sme našli položku. V najhoršom prípade, položka je na konci, alebo položka nie je v zozname vôbec. Takže musíme hľadať celý zoznam, všetky n prvky, a to je dôvod, prečo je o n. Takže teraz je to niečo, čo ich oboch omega n log n, a veľký O n log n. No najdôležitejšia vec sme tu videli, je zlúčiť druh. Takže zlúčiť druh, pamätajte, je nakoniec Theta n log n, v ktorom je definovaná theta ak obidva omega a veľké O sú rovnaké. Obaja n log n. Čo je to niečo, čo je omega N, O a N druhú? No, zase je tu viac možných odpovedí. Tu náhodou povedať Bublinkové triedenie. Vloženie sort by tiež pracovať tu. Pamätajte si, že bublina druh je, že optimalizácia, kde ak ste schopní sa dostať celý zoznam aby bolo nutné robiť všetky swapy, potom dobre, môžeme okamžite vrátiť, že Zoznam bol radené začať. Takže v najlepšom prípade, je to len omega n. Ak to nie je len pekne triedený zoznam začať s, potom máme O n na druhú swapy. A konečne, máme výber druhu pre n na druhú, ako omega a veľké O. Otázka 21. Čo je integer overflow? Tak znovu, podobne ako predtým, máme len konečne veľa bitov k predstavuje celé číslo, tak možno 32 bitov. Povedzme, že máme celé číslo so znamienkom. Potom nakoniec najvyššej kladné číslo môžeme reprezentovať je 2 až 31 mínus 1. Takže to, čo sa stane, keď sa snažíme potom prírastok, že číslo? No, my pôjdeme od 2 do 31 mínus 1, celú cestu až do negatívneho 2 do 31. Tak toto číslo pretečeniu keď budete mať zvyšovanie, a nakoniec nemôžete dostať sa vyššie, a to len zábaly celú cestu späť okolo na zápornú hodnotu. Čo o pretečeniu vyrovnávacej pamäti? Takže vyrovnávacia overflow-- Pamätáš si, čo buffer. Je to len kus pamäte. Niečo ako pole je vyrovnávacia pamäť. Takže buffer overflow je, keď pokuse o prístup k pamäti po skončení tohto poľa. Takže ak máte pole o veľkosti 5 a vami pri pokuse o prístup pole držiak 5 alebo 6 alebo držiak držiak 7, alebo niečo mimo koniec, alebo dokonca niečo below-- pole držiak negatívny 1-- všetky z nich sú pretečeniu vyrovnávacej pamäti. Vy sa dotknete pamäte v zlých cestách. Otázka 23. Takže v tomto ten, ktorý potrebujete realizovať strlen. A povieme vám, že môžete Predpokladáme, s nebude null, takže sa nemusíte vykonať akúkoľvek kontrolu NULL. A existuje niekoľko spôsobov, ako si to mohol urobiť. Tu sme len vziať jednoduchá. Začneme s protiprúdom, n. n je počítanie koľko znakov existujú. Takže začneme na 0, a potom sme iterovat cez celý zoznam. Je to držiak 0 rovná null zakončenie postava? Pamätajte si, že hľadáme null zakončenie znak určiť, ako dlho náš reťazec. Že sa chystá ukončiť všetky príslušné reťazec. Takže je to držiak 0 rovná do terminátora null? Ak tomu tak nie je, potom budeme pozrite sa na s držiakom 1, s držiakom 2. Ideme, kým sme nájsť zakončený nulovým znakom. Potom, čo sme našli, potom n obsahuje celková dĺžka reťazca, a my môžeme len vrátiť to. Otázka 24. Takže to je ten, kde sa majú robiť kompromis. Takže jedna vec je dobrá v jednom cesta, ale v čom je to zlé? Tak tu, zlúčiť druh inklinuje byť rýchlejší ako bubliny druhu. Potom, čo povedal that-- dobre, tam tu viac odpovedí. Ale hlavné je, že bublina druh je omega n pre triedený zoznamu. Pamätajte si, že tabuľky sme práve videli predtým. Takže bublina radí omegou n, najlepší scenár je, že je schopný len tak cez zoznam raz, určiť hej toto je už triedené a návrat. Triedenie zlučovaním, bez ohľadu na to, čo robíte, je omega n log n. Tak pre triedený zoznam, bublinková druh to bude rýchlejšie. Čo je teraz prepojený zoznamy? Takže spájať zoznam môže zväčšiť a zmenšiť aby sa zmestili toľko prvkov podľa potreby. Mať hovoril, that-- tak obvykle priame porovnanie bude spojený zoznam s radom. Takže aj keď pole môže ľahko zväčšiť a zmenšiť aby sa zmestili čo najviac prvkov podľa potreby, spájať zoznam v porovnaní s array-- An pole má náhodný prístup. Môžeme index do niektorého Najmä prvok poľa. Takže pre spájať zoznam, nemôžeme stačí ísť do piateho elementu, musíme prejsť od začiatku až sa dostaneme do piateho elementu. A to sa deje, aby sa zabránilo nás od niečo ako binárne vyhľadávanie. Keď už hovoríme o binárne vyhľadávanie, binárne vyhľadávanie má tendenciu byť rýchlejší ako lineárny vyhľadávania. Mať hovoril, that-- tak, jedno možné vec je to, že nemôžete urobiť binárne hľadať v spojových zoznamov, môžete to urobiť len na poliach. Ale pravdepodobne dôležitejšie, nemôžete robiť binárne vyhľadávanie na poli, ktoré nie je zoradená. Vopred budete potrebovať vyriešiť polia, a až potom môže urobíte binárne vyhľadávanie. Takže ak vaša vec nie je triedený začať, potom lineárne hľadanie môže byť rýchlejší. Otázka 27. Takže zvážte program nižšie, ktorá bude v ďalšej snímku. A to je ten, kde sme bude chcieť výslovne uviesť, hodnoty pre rôzne premenné. Tak sa poďme pozrieť na to. Takže prvom riadku. Máme int x = 1. To je jediná vec, čo sa stalo. Takže v prvom riadku, vidíme v našej Tabuľka, že y, a, b, a TMP sú zatemnenie. Takže to, čo je x? Tak sme len nastaviť ju na hodnotu 1. A potom riadok dva, dobre, vidíme, že y je nastavené na 2, a tabuľka je už vyplniť pre nás. Takže x je 1 a y je 2. Teraz, riadok tri, my sme teraz vnútri funkcie pamäti. Čo sme sa prejsť k výmene? Minuli sme ampersand x pre a ampersand y za b. V prípade, že problém skôr uviedol, že adresa x je 0x10, a adresa y je 0x14. Tak a a b sa rovnajú 0x10 a 0x14, resp. Teraz na riadku tri, čo sú x a y? No, nič sa nezmenilo o x a y v tomto bode. Aj keď sú vnútri hlavného rámu zásobníka, majú stále rovnaké Hodnoty, ktoré predtým. Nemáme zmenil nejaké pamäti. Takže x je 1, y je 2. Dobrá. Takže teraz sme si povedali, int tmp rovná hrať. Takže na linke štyri, všetko je rovnaké, okrem zvýšiť. Sme sa zmenili hodnoty o ničom tmp. Sme nastaviť tmp rovno hrať. Čo je to hviezda? No, body x, teda hviezda bude rovné x, čo je 1. Takže všetko je skopírovaný dole, a TMP je nastavená na hodnotu 1. Teraz ďalší riadok. Hviezda rovná hviezda b. Takže súlade opäť five-- dobre, všetko je rovnaký, s výnimkou, čo hviezda je. Čo je to hviezda? No, my sme len povedali hviezda je x. Takže meníme x rovnakého hviezdy b. Čo je to hviezda b? y. b body y. Takže hviezda b je y. Takže sme nastavenie x rovná y, a všetko ostatné je rovnaké. Vidíme teda, v ďalšom riadku, že x je teraz 2, a zvyšok sú práve skopírovali nadol. Teraz, v ďalšom riadku, hviezda b sa rovná tmp. No, my práve povedal hviezda b je y, takže sme nastavenie y rovné tmp. Všetko ostatné je rovnaké, takže všetko, čo dostane kopírované. Sme nastavení y sa rovná tmp, čo je jeden, a všetko ostatné je rovnaké. Teraz konečne, riadok sedem. Sme späť v hlavnej funkcie. Sme po swapu je hotová. Prišli sme a, b, a tmp, ale nakoniec sme sa nemení žiadne hodnoty na nič v tomto bode, sme len skopírovať x a y nadol. A vidíme, že x a y sú Teraz 2 a 1 miesto 1 a 2. Swap bol úspešne vykonaný. Otázka 28. Predpokladajme, že sa stretnete chybové správy Nižšie počas úradných hodín budúci rok ako CA alebo TF. Poradiť, ako opraviť každý z týchto chýb. Tak nedefinovaný odkaz na getString. Prečo by ste vidieť? No, ak študent používa GetString v ich kóde, majú riadne Hash súčasťou CS50 dot h zahrnúť knižnice CS50. No, čo sa im Potrebujete opraviť túto chybu? Čo musíte urobiť, pomlčka lcs50 na príkazový riadok, keď sú kompiláciu. Takže v prípade, že neprejde zvonenie pomlčka lcs50, sú nebude mať skutočný kód, ktorý implementuje getString. Otázka 29. Implicitne vyhlásení knižničný funkcie strlen. No to teraz, oni nemajú urobil správny hash patrí. V tomto konkrétnom prípade, súbor hlavičky treba započítať, je reťazec bodka h, vrátane reťazca bodka h, teraz student-- teraz kompilátor má prístup k vyhlásenie o strlen, a vie, že váš kód používa strlen správne. Otázka 30. Viac percent konverzie než dátových argumentov. Tak čo je to? Dobre si pamätám, že tieto percent signs--, ako sú relevantné pre printf. Takže printf môžeme percent-- by sme mohli niečo vytlačiť ako percento aj spätné lomítka n. Alebo môžeme vytlačiť ako percenta aj, priestor, percenta aj, priestor, percenta aj. Takže pre každý z nich znaky percenta, musíme odovzdať premennú na konci printf. Takže keď povieme printf Paren percent aj spätné lomítka n úzke zátvorka, No, môžeme povedať, že sme do tlače celé číslo, ale potom sme neprejdú printf číslo skutočne vytlačiť. Tak tu viac percent konverzie dát než argumenty? To hovorí, že máme celá partia percent, a nemáme dostatok premenné skutočne vyplniť v týchto percent. A potom určite pre otázku 31, definitívne stratil 40 bytov v jednom bloku. Tak to je chyba Valgrind. To hovorí, že niekde v kóde, máte prídel, ktorý je 40 byty veľké, takže si malloced 40 bajtov, a nikdy ju oslobodil. S najväčšou pravdepodobnosťou stačí nájsť nejaký únik pamäte, a zistiť, kde je potrebné oslobodiť tento blok pamäte. A otázka 32, neplatný zápis o veľkosti 4. Opäť je to chyba Valgrind. To nemusí robiť s úniky teraz pamäti. To je najviac likely-- myslím, že je to akési neplatné pamäte práv. A s najväčšou pravdepodobnosťou je to nejaký druh pretečeniu vyrovnávacej pamäti. Kde máte pole, možno číslo poľa, a poďme hovoria, že je to o veľkosti 5, a skúste sa dotknúť poľa držiaka 5. Takže ak sa pokúsite napísať, že hodnota, to nie je kus pamäti že ste skutočne majú prístup, a takže budete mať túto chybu, hovorí neplatný zápis o veľkosti 4. Valgrind bude poznať, že ste snaží sa dotknúť pamäť nevhodne. A to je pre quiz0. Som Rob Bowden, a to je CS50.