ROB BOWDEN: Ahoj, já jsem Rob Bowden, a pojďme mluvit o quiz0. Takže, první otázka. To je otázka, kde jste potřebovali ke kódování čísla 127 v binární žárovky. Pokud byste chtěli, mohli byste dělat pravidelnou konverzi od bi-- nebo z desítkové do binární. Ale to asi bude vzít spoustu času. Myslím, že byste mohli přijít na to, OK, 1 je tam, 2 je tam, 4 je tam, 8 je tam. Jednodušší způsob, 127 128 minus jedna. To vlevo žárovka je 128-bit. Takže 127 je opravdu jen vše ostatních žárovek, protože to je vlevo žárovka minus 1. To je pro tuto otázku. 

Otázka první. Tak s 3 bity můžete představují 8 odlišné hodnoty. Proč je tedy 7 největší non-negativní desetinné číslo můžete reprezentovat? No, když jsme jen možné představují 8 odlišné hodnoty, poté, co budeme mít představuje 0 až 7. 0 zabírá jednu z hodnot. 

Otázka dva. S n bitů, kolik zřetelný Hodnoty můžete reprezentovat? Takže s n bitů, máte 2 Možné hodnoty pro každý bit. Takže máme dvě možné hodnoty pro první bit, 2 možné hodnoty za druhé, 2 možné, aby třetinu. A tak to je 2 krát 2 krát 2, a nakonec odpověď je 2 až n. 

Otázka tři. Co je 0x50 v binární? Takže pamatujte, že hexadecimální má velmi jednoduchý převod do dvojkové soustavy. Tak tady, jen je třeba se podívat na 5 a 0 nezávisle na sobě. Takže to, co je 5 v binární? 0101, to je 1 bit a 4-bitová. Co je 0 v binární? Není složité. 0000. Takže jen dát dohromady, a že je plný počet v binární. 01010000. A pokud byste chtěli byste mohli vzlétnout, že úplně vlevo nulu. Je to irelevantní. 

Takže alternativně, co je 0x50 v desítkové soustavě? Pokud byste chtěli, můžete could-- pokud jste více vyhovuje binární, můžete vzít, že binární odpověď a převést to do desítkové. Nebo bychom mohli jen vzpomenout že šestnáctkové. Takže je 0 v 0-tém místě, a 5 je ve 16 na první místo. Tak tady máme 5 krát 16 k První, plus 0 krát 16 na nulu, je 80. A pokud jste se podíval na Nárok na otázku, to byl CS 80, který byl druh nápověda k odpovědi na tento problém. 

Otázka pět. Máme tu Scratch skript, který je opakovat 4 krát arašídové máslo želé. Tak jak se nyní kód v C? No, máme here-- část tučně je jediná část, kterou má za úkol provést. Takže máme čtyři smyčky, která je opakování 4 doba, printf-ing arašídové máslo želé, s novou linkou, jak tento problém žádá. 

Otázka šest, další problém Scratch. Vidíme, že jsme v navždy smyčky. Říkáme, že proměnná i a zvyšování i o 1. Nyní chceme dělat, že v C existují více způsobů, jak to mohl udělat. Zde se stalo kód navždy smyčka jako while (true). Tak jsme se prohlásit, že proměnná i, jen jako bychom měli proměnné i poškrábání. Prohlásit, že proměnná i, a navždy while (true), říkáme, že proměnná i. Takže printf% Já-- nebo mohl jsi použít% d. Říkáme, že proměnná, a pak ji zvýšit, i ++. 

Otázka sedm. Teď chceme udělat něco velmi podobného Mario dot c od problému nastavit jednu. Chceme vytisknout tyto hashtagy, Chceme-li vytisknout pět o tři obdélníku těchto hash. Tak jak budeme dělat, že? No, my jsme vám celý banda kódu, a právě je třeba vyplnit ve funkci tiskového rastru. 

Tak co PrintGrid vypadat? No vy jste v minulosti šířku a výšku. Takže máme vnější 4 smyčky, která je smyčkování přes všechny řádky tohoto grid, že chceme vytisknout. Pak máme mezi vnořené 4 smyčky, to je tisk v každém sloupci. Takže pro každý řádek, máme pro tisk každý sloupec, jeden hash. Pak se na konci řádku jsme vytisknout jeden nový řádek přejdete na další řádek. A to je pro celé sítě. 

Otázka osm. Funkce jako PrintGrid je řekl, aby mají vedlejší účinky, ale ne návrat hodnotu. Vysvětlete rozdíl. Takže to závisí na vás pamatovat co je to vedlejší účinek je. No, návrat value-- Víme PrintGrid není mít návratovou hodnotu, protože tady se říká, že neplatné. Takže vše, co se vrací void není opravdu nic vracet. Takže to, co je vedlejší efekt? No, vedlejším účinkem je něco, co trochu přetrvává po ukončením funkce že to není jen vrátil, a to nejen z vstupů. 

Tak, například, můžeme změnit globální proměnnou. To by byl vedlejší efekt. V tomto konkrétním případě, velmi důležitý vedlejší efekt tiskne na obrazovku. Takže to je vedlejším účinkem že PrintGrid má. Tiskneme tyto věci na obrazovce. A na co si vzpomenete že jako vedlejší efekt, protože to je něco, co přetrvává i po této funkce skončí. To je něco, co nespadá do působnosti této funkce, která v konečném důsledku se změnil, Obsah obrazovky. 

Otázka devět. Zvažte program níže, ke kterému čísla řádků byly přidány pro saké diskuse. Takže v tomto programu jsme jen volání getString, uložením do této proměnné s, a pak tisk této proměnné s. OK. Tak vysvětlují, proč je přítomna řada jednou. #include cs50 tečka h. Proč musíme #include cs50 dot h? Tak jsme volání GetString funkce, a GetString je definován v knihovně cs50. Takže pokud jsme neměli #include cs50 tečka h, bychom se dostali, že implicitní prohlášení chyby funkce GetString od kompilátoru. Takže musíme zahrnout library-- musíme zahrnout hlavičkový soubor, jinak kompilátor nebude uznávají, že GetString existuje. 

Vysvětlete, proč je přítomna řada dvě. Takže standardní io tečka h. Je to úplně stejné jak je výše uvedené problémy, s výjimkou toho, vypořádat se s GetString, mluvíme o printf. Takže pokud jsme neřekli potřebujeme zahrnout standardní io dot h, pak bychom nebyli schopni použít funkci printf, protože kompilátor by o tom vědět. 

Why-- jaký je význam o ztrátu v řadě čtyři? Tak a máme tady int main (void). To je jen říkám, že jsme nedostávají žádnou příkazového řádku Argumenty hlavní. Pamatujte si, že bychom mohli říci, int Hlavní int argc řetězec argv závorky. Tak jsme tady jen říct, void, že jsme ignorují argumenty příkazového řádku. 

Vysvětlení, s ohledem na paměti, přesně co GetString v řadě šest vrátí. GetString vrací blok paměť, pole znaků. Je to opravdu vrací ukazatel na první znak. Pamatujte si, že řetězec char hvězda. Takže s je ukazatel na první charakter v jakékoli řetězec že uživatel zadal na klávesnici. A že paměť se stane být malloced, tak, že paměť je v haldě. 

Otázka 13. Uvažujme programu níže. Takže vše, co tento program dělá je printf-ing 1 děleno 10. Takže když sestavil a vykonán, tento program výstupy 0.0, i když 1 děleno 10 je 0,1. Tak proč je to 0.0? No, je to proto, celočíselného dělení. Tak je celé číslo 1, 10 je celé číslo. Takže 1 děleno 10, vše je zacházeno jako celá čísla, a C, když budeme dělat celočíselné dělení, jsme zkrátit jakékoliv desetinnou čárkou. Takže 1 děleno 10 je 0, a pak se snažíme vytisknout to jako float, tak nula vytisknout jako plovák je 0.0. A to je důvod, proč jsme si 0.0. 

Uvažujme programu níže. Teď jsme tisk 0.1. Takže bez celočíselném dělení, jsme jen tisku 0,1, ale my jsme ho tisku 28 desetinných míst. A my jsme si to 0,1000, celá parta nul, 5 5 5, bla bla bla. Otázkou tedy je, proč to dělá vytisknout to, že místo toho, přesně 0,1? 

Takže zde důvod, proč je nyní s plovoucí desetinnou čárkou nepřesnost. Pamatujte si, že plovák je pouze 32 bitů. Takže můžeme představovat pouze konečný počet plovoucí bodové hodnoty s těmi 32 bitů. No tam je nakonec nekonečně Mnoho plovoucí bodové hodnoty, a tam je nekonečně mnoho plovoucí bodové hodnoty v rozmezí 0 až 1, a my jsme samozřejmě schopni představují i ​​více hodnot, než to. Takže musíme přinášet oběti, aby bylo možné reprezentovat většinu hodnoty. 

Takže hodnota jako 0,1, zřejmě nemůžeme představovat, že přesně. Takže místo toho, což představuje 0,1 děláme nejlepší, co můžeme reprezentovat tuto 0.100000 5 5 5. A to je docela blízko, ale pro mnoho aplikací budete muset starat o s plovoucí desetinnou čárkou nepřesnost, protože jsme prostě nemůže představovat vše plovoucí body přesně. 

Otázka 15. Zvažte pod kód. Jsme jen tisk 1 + 1. Takže tam není žádný trik zde. 1 plus 1 vyhodnocuje 2, a pak tisknete, že. To jen vytiskne 2. 

Otázka 16. Teď jsme tisk znaku 1 plus 1 znak. Tak proč to není vytisknout totéž? No postava 1 plus znak 1 znak 1 má hodnotu ASCII 49. Tak tohle je opravdu říká, 49 a 49, a nakonec to bude tisknout 98. Takže to netiskne 2. 

Otázka 17. Dokončit provádění lichých pod takovým způsobem, že funkce vrací hodnotu true v případě, n je liché a false, pokud je n sudé. To je skvělý účel pro mod operátora. Tak jsme se vzít naše argument n, pokud n mod 2 se rovná 1, dobře to znamená, že n dělí o 2 měl zbytek. Je-li n děleno 2 měl zbytek, který Znamená to, že n je liché, a tak jsme se vrátit true. Jinak se vrátíme false. Také to mohl udělat n mod 2 rovná nula, vrátí false, jinak vrátí hodnotu true. 

Zvažte rekurzivní funkce níže. Takže pokud n je menší než nebo roven 1, vrátí 1, jiný návrat n-krát f n minus 1. Takže to, co je tato funkce? No, je to jen faktoriál funkce. To je dobře zastoupena jak n faktoriálem. 

Takže otázka 19 teď, chceme tento rekurzivní funkci. Chceme, aby to iterativní. Tak jak to uděláme? No pro zaměstnance řešení, a opět je tu více způsobů, jak to mohl udělat že jsme se začít s tímto produktem int se rovná 1. A v celém tomto smyčky for, jdeme k násobení produkt nakonec skončit s plnou faktoriálu. Takže pro int i se rovná 2, i je menší nebo rovno n, i ++. 

Ty by mohly být divíte, proč jsem se rovná 2. No, pamatujte, že zde musíme ujistěte se, že naše základna případ je v pořádku. Takže pokud n je menší než nebo rovno 1, jsme jen vrací 1. Tak tady jsme se začít na i rovná 2. No, pokud bych měl 1, pak the-- nebo pokud n byla 1, potom pro smyčce by se provádět vůbec. A tak bychom jen návrat produkt, který je 1. Podobně, pokud je n byly něco méně než 1-- kdyby to bylo 0, negativní 1, whatever-- mohli bychom se vrací 1, což je přesně to, co rekurzivní verze dělá. 

Nyní, když n je větší než 1, pak budeme udělat alespoň jednu iterace této smyčky. Takže řekněme, že n je 5, pak jsme dělat časy produktu se rovná 2. Takže teď Produkt je 2. Teď budeme dělat Časy produkt rovná 3. Teď je to 6. Časy produktu se rovná 4, teď je to 24. Časy produktu se rovná 5, nyní je to 120. Takže nakonec vracíme 120, který je správně 5 faktoriálem. 

Otázka 20. To je ten, kde je nutné vyplnit V této tabulce se daný algoritmus, něco, co jsme viděli, že hodí tyto algoritmické běh Časy tyto asymptotické dobu chodu. Takže to, co je algoritmus, který je omega 1, ale velký O n? Takže tam může být nekonečně mnoho odpovědí zde. Ten, který jsme viděli asi nejvíce Často je jen lineární hledání. 

Takže v nejlepším případě scénář, bod jsme hledá je začátku seznamu a tak v omega 1 kroků, První věc, kterou jsme se zjistit, právě jsme okamžitě vrátit že jsme našli položku. V nejhorším případě, položka je na konci, nebo položka není v seznamu vůbec. Takže musíme hledat celý seznam, všechny n prvky, a to je důvod, proč je o n. 

Takže teď je to něco, co je oba omega n log n, a velký O n log n. No nejdůležitější věc jsme tu viděli, je sloučit druh. Takže sloučit druh, pamatujte, je nakonec Theta n log n, kde je definována theta pokud oba omega a velké O jsou stejné. Oba n log n. 

Co je to něco, co je omega N, O a N druhou? No, zase je tu více možných odpovědí. Tady náhodou říci Bublinkové řazení. Vložení sort by také pracovat zde. Pamatujte si, že bublina druh je, že optimalizace, kde pokud jste schopni se dostat celý seznam aniž by bylo nutné dělat veškeré swapy, pak dobře, můžeme okamžitě vrátit, že Seznam byl řazeny začít. Takže v nejlepším případě, je to jen omega n. Pokud to není jen hezky tříděný seznam začít s, pak máme O n na druhou swapy. A konečně, máme výběr druhu pro n na druhou, jak omega a velké O. 

Otázka 21. Co je integer overflow? Tak znovu, podobně jako dříve, máme jen konečně mnoho bitů k představuje celé číslo, tak možná 32 bitů. Řekněme, že máme celé číslo se znaménkem. Pak nakonec nejvyšší kladné číslo můžeme reprezentovat je 2 až 31 minus 1. Takže to, co se stane, když se snažíme pak přírůstek, že číslo? No, my půjdeme od 2 do 31 minus 1, celou cestu až do negativního 2 do 31. Tak tohle číslo přetečení když budete mít zvyšování, a nakonec nemůžete dostat se výš, a to jen zábaly celou cestu zpět kolem na zápornou hodnotu. 

Co o přetečení vyrovnávací paměti? Takže vyrovnávací overflow-- Pamatuješ si, co buffer. Je to jen kus paměti. Něco jako pole je vyrovnávací paměť. Takže buffer overflow je, když pokusu o přístup k paměti po skončení tohoto pole. Takže pokud máte pole o velikosti 5 a vámi při pokusu o přístup pole držák 5 nebo 6 nebo držák držák 7, nebo něco mimo konec, nebo dokonce něco below-- pole držák negativní 1-- všechny z nich jsou přetečení vyrovnávací paměti. Vy se dotknete paměti ve špatných cestách. 

Otázka 23. Takže v tomto ten, který potřebujete realizovat strlen. A řekneme vám, že můžete Předpokládáme, s nebude null, takže se nemusíte provést jakoukoli kontrolu NULL. A existuje několik způsobů, jak jsi to mohl udělat. Zde jsme jen vzít jednoduchá. Začneme s protiproudem, n. n je počítání kolik znaků existují. Takže začneme na 0, a pak jsme iterovat přes celý seznam. 

Je to držák 0 rovná null zakončení postava? Pamatujte si, že hledáme null zakončení znak určit, jak dlouho náš řetězec. Že se chystá ukončit veškeré příslušné řetězec. Takže je to držák 0 rovna do nulového ukončovacího znaku? Pokud tomu tak není, pak budeme podívejte se na s držákem 1, s držákem 2. Jedeme, dokud jsme najít zakončen nulovým znakem. Poté, co jsme našli, pak n obsahuje celková délka řetězce, a my můžeme jen vrátit to. 

Otázka 24. Takže to je ten, kde se mají dělat kompromis. Takže jedna věc je dobrá v jednom cesta, ale v čem je to špatné? Tak tady, sloučit druh inklinuje být rychlejší než bubliny druhu. Poté, co řekl that-- dobře, tam zde více odpovědí. Ale hlavní je, že bublina druh je omega n pro tříděný seznamu. 

Pamatujte si, že tabulky jsme právě viděli dříve. Takže bublina řadí omegou n, nejlepší scénář je, že je schopen jen tak přes seznam jednou, určit hej tohle je už tříděny a návrat. Merge sort, bez ohledu na to, co děláte, je omega n log n. Tak pro tříděný seznam, bublinková druh to bude rychlejší. 

Co je nyní propojen seznamy? Takže spojový seznam může zvětšit a zmenšit aby se vešly tolik prvků podle potřeby. Mít říkal, that-- tak obvykle přímé srovnání bude spojen seznam s řadou. Takže i když pole může snadno zvětšit a zmenšit aby se vešly co nejvíce prvků podle potřeby, spojový seznam ve srovnání s array-- An pole má náhodný přístup. Můžeme index do některého Zejména prvek pole. 

Takže pro spojový seznam, nemůžeme stačí jít do pátého elementu, musíme projít od začátku až se dostaneme do pátého elementu. A to se děje, aby se zabránilo nás od něco jako binární vyhledávání. Když už mluvíme o binární vyhledávání, binární vyhledávání má tendenci být rychlejší než lineární vyhledávání. Mít říkal, that-- tak, jedno možné věc je to, že nemůžete udělat binární hledat v spojových seznamů, můžete to udělat jen na polích. Ale pravděpodobně důležitější, nemůžete dělat binární vyhledávání na poli, které není seřazena. Předem budete potřebovat vyřešit pole, a teprve potom může uděláte binární vyhledávání. Takže pokud vaše věc není tříděný začít, pak lineární hledání může být rychlejší. 

Otázka 27. Takže zvažte program níže, která bude v další snímek. A to je ten, kde jsme bude chtít výslovně uvést, hodnoty pro různé proměnné. Tak se pojďme podívat na to. 

Takže prvním řádku. Máme int x = 1. To je jediná věc, co se stalo. Takže v prvním řádku, vidíme v naší Tabulka, že y, a, b, a TMP jsou zatemnění. Takže to, co je x? Tak jsme jen nastavit ji na hodnotu 1. A pak řádek dva, dobře, vidíme, že y je nastaveno na 2, a tabulka je již vyplnit pro nás. Takže x je 1 a y je 2. 

Nyní, řádek tři, my jsme teď uvnitř funkce paměti. Co jsme se projít k výměně? Minuli jsme ampersand x pro a ampersand y za b. V případě, že problém dříve uvedl, že adresa x je 0x10, a adresa y je 0x14. Tak a a b se rovnají 0x10 a 0x14, resp. 

Nyní na řádku tři, co jsou x a y? No, nic se nezměnilo o x a y v tomto bodě. I když jsou uvnitř hlavního rámu zásobníku, mají stále stejné Hodnoty, které předtím. Nemáme změnil nějaké paměti. Takže x je 1, y je 2. Dobrá. Takže teď jsme si řekli, int tmp rovná hrát. Takže na lince čtyři, všechno je stejné, kromě zvýšit. Jsme se změnili hodnoty o ničem tmp. Jsme nastavit tmp rovnou hrát. Co je to hvězda? No, body x, tedy hvězda bude rovné x, což je 1. Takže všechno je zkopírován dolů, a TMP je nastavena na hodnotu 1. 

Nyní další řádek. Hvězda rovná hvězda b. Takže souladu opět five-- dobře, všechno je stejný, s výjimkou, co hvězda je. Co je to hvězda? No, my jsme jen řekli hvězda je x. Takže měníme x rovného hvězdy b. Co je to hvězda b? y. b body y. Takže hvězda b je y. Takže jsme nastavení x rovno y, a všechno ostatní je stejné. Vidíme tedy, v dalším řádku, že x je nyní 2, a zbytek jsou právě zkopírovali dolů. 

Nyní, v dalším řádku, hvězda b se rovná tmp. No, my právě řekl hvězda b je y, takže jsme nastavení y rovno tmp. Vše ostatní je stejné, takže vše, co dostane kopírovány. Jsme nastavení y se rovná tmp, což je jeden, a všechno ostatní je stejné. 

Nyní konečně, řádek sedm. Jsme zpátky v hlavní funkce. Jsme po swapu je hotová. Přišli jsme a, b, a tmp, ale nakonec jsme se nemění žádné hodnoty na nic v tomto bodě, jsme jen zkopírovat x a y dolů. A vidíme, že x a y jsou Nyní 2 a 1 místo 1 a 2. Swap byl úspěšně proveden. 

Otázka 28. Předpokládejme, že se setkáte chybové zprávy Níže během úředních hodin příští rok jako CA nebo TF. Poradit, jak opravit každý z těchto chyb. Tak nedefinovaný odkaz na getString. Proč by jste vidět? No, pokud student používá GetString v jejich kódu, mají řádně Hash součástí cs50 dot h zahrnout knihovny cs50. 

No, co se jim Potřebujete opravit tuto chybu? Co musíte udělat, pomlčka lcs50 na příkazový řádek, když jsou kompilaci. Takže v případě, že neprojde zvonění pomlčka lcs50, jsou nebude mít skutečný kód, který implementuje getString. 

Otázka 29. Implicitně vyhlášení knihovní funkce strlen. No to teď, oni nemají udělal správný hash patří. V tomto konkrétním případě, soubor záhlaví je třeba započítat, je řetězec tečka h, včetně řetězce tečka h, nyní student-- nyní kompilátor má přístup k prohlášení o strlen, a ví, že váš kód používá strlen správně. 

Otázka 30. Více procent konverze než datových argumentů. Tak co je to? Dobře si pamatuji, že tyto procent signs--, jak jsou relevantní pro printf. Takže printf můžeme percent-- bychom mohli něco vytisknout jako procento i zpětná lomítka n. Nebo můžeme vytisknout jako procenta i, prostor, procenta i, prostor, procenta i. Takže pro každý z nich znaky procenta, musíme předat proměnnou na konci printf. 

Takže když řekneme printf paren procent i zpětná lomítka n úzké závorka, No, můžeme říci, že jsme do tisku celé číslo, ale pak jsme neprojdou printf číslo skutečně vytisknout. Tak tady více procent konverze dat než argumenty? To říká, že máme celá parta procent, a nemáme dostatek proměnné skutečně vyplnit v těchto procent. 

A pak určitě pro otázku 31, definitivně ztratil 40 bytů v jednom bloku. Tak to je chyba Valgrind. To říká, že někde v kódu, máte příděl, který je 40 byty velké, takže si malloced 40 bajtů, a nikdy ji osvobodil. S největší pravděpodobností stačí najít nějaký únik paměti, a zjistit, kde je třeba osvobodit tento blok paměti. 

A otázka 32, neplatný zápis o velikosti 4. Opět je to chyba Valgrind. To nemusí dělat s úniky nyní paměti. To je nejvíce likely-- myslím, že je to jakési neplatné paměti práv. A s největší pravděpodobností je to nějaký druh přetečení vyrovnávací paměti. Kde máte pole, možná číslo pole, a pojďme říkají, že je to o velikosti 5, a zkuste se dotknout pole držáku 5. Takže pokud se pokusíte napsat, že hodnota, to není kus paměti že jste skutečně mají přístup, a takže budete mít tuto chybu, říká neplatný zápis o velikosti 4. Valgrind bude poznat, že jste snaží se dotknout paměť nevhodně. 

A to je pro quiz0. Jsem Rob Bowden, a to je CS50.