ROB Боудън: Здравейте, аз съм Роб Боудън, и нека да говорим за quiz0. Така че, на първо място въпрос. Това е въпрос, по който ви е необходимо, за да кодира броя 127 в двоичен крушки. Ако искате, бихте могли да направи редовен превръщането от bi-- или от десетична към двоична. Но това е най-вероятно ще да отнеме много време. Искам да кажа, бихте могли да разберете, че OK, един е в там, 2 е там, 4 е там, 8 е там. По-лесен начин, 127 е 128 минус един. Това най-лявата крушка е на 128-бита. Така че 127 е наистина просто всички от другите крушки, тъй като това е най-левият крушка минус 1. Това е всичко за този въпрос. 

Въпрос един. Така с 3 бита можете представляват 8 различни стойности. Защо, тогава, е 7, най-големият не-отрицателни десетичната число може да представлява? Е, ако ние само може да представляват 8 различни ценности, След това, което ще бъде представлява 0 до 7. 0 заема една от ценностите. 

Въпрос две. С п бита, колко важно стойности може да ви представляват? Така че, с п бита, имате 2 възможните стойности за всеки бит. Така че ние имаме две възможни стойности за Първият бит, два възможни стойности за втората, 2 възможно за трети. И така, това е два пъти по 2 пъти 2, и в крайна сметка отговорът е 2 до п. 

Въпрос три. Какво е 0x50 в двоичен? Така че не забравяйте, че шестнадесетичен има много ясно превръщане в двоичен. Така че тук, ние просто трябва да се търси в 5 и 0 самостоятелно. Така че това, което е 5 в двоичен? 0101, че е бит 1 и 4 бита. Какво е 0 в двоичен? Не е трудно. 0000. Така че просто ги съберете заедно, и това е пълният брой в двоичен. 01010000. И ако искате бихте могли излитане, че лявата нула. Това е без значение. 

Така че след като алтернатива, какво е 0x50 в десетична? Ако искате, можете could-- ако сте по-удобно с двоичен, можеш да вземеш, че двоичен отговор и конвертирате, че в десетични. Или бихме могли просто да си спомня че в шестнадесетичен вид. Така, че 0 е в 0-о място, и 5 е в 16 на първо място. Така че тук, ние имаме 5 пъти 16 към Първо, плюс 0 пъти 16 към нула, е 80. И ако ви погледна заглавие на въпроса, е CS 80, което е вид намек за отговора на този проблем. 

Въпрос пет. Ние имаме този Scratch скрипт, който е повтаря 4 пъти фъстъчено масло желе. И така, как ще правим сега код, че в C? Е, ние имаме here-- частта с удебелен шрифт е само частта, която трябваше да изпълни. Така че ние имаме 4 линия, която е примка 4 пъти, ФОРМАТ-Ing фъстъчено масло желе, с нов ред, тъй като проблемът изисква. 

Въпрос шест, друг Scratch проблем. Ние виждаме, че ние сме в завинаги контур. Ние казвате променливата I и след това се увеличаване и с 1. Сега искаме да направим това в C. Има множество начини, които биха могли да са направили това. Тук ще се случи с Кодекса на завинаги контур като докато (вярно). Така че ние декларираме променливата аз, просто като имахме променлива и в Scratch. Декларирайте променлива I, и завинаги докато (вярно), ние казваме променливата аз. Така ФОРМАТ% i-- или бихте могли да сте използвали% г. Ние казваме, че променлива, и след това нарастване, аз ++. 

Въпрос седем. Сега искаме да направим нещо много подобно Марио точка в от проблем зададете една. Искаме да отпечатате тези Hashtags, искаме да отпечатате пет от три правоъгълник от тези хешове. И така, как ние ще направим това? Е, ние ще ви даде цялата куп код, а ти просто трябва да попълните във функцията за печат решетка. 

Така че това, което се PrintGrid изглежда? Ами вие сте миналото ширина и височина. Така че ние имаме един външен 4 линия, която е примка над всички редове на това мрежа, която ние искаме да разпечатате. Тогава ние имаме между вложени 4 цикъла, това е печат върху всяка колона. Така че за всеки ред се печатат за всяка колона, един хашиш. След това в края на редицата ние отпечатате Един нов ред за да отидете на следващия ред. И това е за цялата мрежа. 

Въпрос осем. A функция като PrintGrid се казва, че имат страничен ефект, но не и връщане стойност. Обяснете разликата. Така че това зависи от вас си спомни това, което е страничен ефект е. Е, връщане value-- знаем PrintGrid не има връщане стойност, тъй като точно тук се казва невалидни. Така че всичко, което се връща невалидни наистина не върне нищо. Така че това, което е страничен ефект? Е, страничен ефект е нищо, че нещо продължава след края на функционални това не беше просто се върна, и това не е само от входовете. 

Така, например, бихме могли промени глобална променлива. Това щеше да е страничен ефект. В този конкретен случай, много важен страничен ефект отпечатва на екрана. Така че това е страничен ефект че PrintGrid има. Ние отпечатайте тези неща на екрана. И можеш да се сетиш че като страничен ефект, тъй като това е нещо, което продължава след края на тази функция. Това е нещо, извън обхвата на тази функция, която в крайна сметка се променила, съдържанието на екрана. 

Въпрос девет. Помислете за програмата по-долу, за кои договорени номера са добавени за името на дискусия. Така че в тази програма, ние сме просто призовава GetString, го приберете В тези променливи S, и след това отпечатване на тази променлива и. OK. Така обясни защо първа линия е налице. #include cs50 точка ч. Защо ние трябва да #include cs50 точка з? Ами ние се обаждате на GetString функция, и GetString се определя в cs50 библиотеката. Така че, ако ние не разполагаме с #include cs50 точка з, ние ще се получи, че имплицитно декларация на грешка GetString функция от компилатора. Така че ние трябва да се включи library-- ние трябва да включва заглавната част на файла, или в противен случай компилаторът не ще признае, че GetString съществува. 

Обяснете защо втора линия е налице. Така стандарт IO точка ч. Това е точно същото, като предходната задача, с изключение вместо да се занимават с GetString, ние не говорим за ФОРМАТ. Така че, ако ние не казваме, че трябва да включват стандартни IO точка з, тогава ние не ще бъде в състояние За да използвате функцията ФОРМАТ, защото компилаторът няма да знаят за него. 

Why-- какво е значението на анулира в съответствие с четири? Така че тук имаме INT главната (недействителни). Това е просто казвам, че ние не се получава никакви командния ред аргументи на Майн. Не забравяйте, че ние може да се каже инт Основните INT argc струнен argv скоби. Така че тук ние просто кажем нищожен да кажем, пренебрегваме аргументи от командния ред. 

Обяснете, по отношение на паметта, точно какво GetString в съответствие шест възвръщаемост. GetString се завръща блок памет, набор от символи. Това е наистина връщане на указател към първия символ. Не забравяйте, че низ е знак звезда. Така и е указател към първа герой в каквато и да е низ е че потребителят влезе в клавиатурата. И този спомен се случва да бъде malloced, така, че паметта е в купчината. 

Въпрос 13. Помислете за програмата по-долу. Така че всичко, тази програма се прави е ФОРМАТ-Ing 1 делено на 10. Така че, когато се съставя и изпълнява тази програма изходи 0.0, въпреки че 1 е разделена на 10 0.1. Така че, защо го е 0.0? Е, това е така, защото от целочислено деление. Така 1 е цяло число, 10 е цяло число. Така че едно делено на 10, всичко се третира като цели числа, и в C, когато правим целочислено деление, ние съкращава всяка десетична точка. Така един разделен от 10 се 0, а след това ние се опитваме да отпечатате, че като плувка, така нулева отпечатва като плувка е 0.0. И това е защо ние получаваме 0.0. 

Помислете за програмата по-долу. Сега ние сме печат 0.1. Така че не целочислено деление, ние просто печат 0.1, но ние сме го печат до 28 знака след десетичната запетая. И ние се получи това 0.1000, цял куп нули, 5 5 5, бла бла бла. Така че въпросът тук е защо го прави отпечатате, че вместо точно 0.1? 

Така че тук причината е сега плаваща запетая неточности. Не забравяйте, че на плувка е само на 32 бита. Така че ние само може да представлява определен брой на стойности с плаваща запетая с тези 32 бита. Ами там е в крайна сметка безкрайно много числа с плаваща запетая, и има безкрайно много плаващ точка стойности между 0 и 1, и очевидно ние сме в състояние да представляват още повече стойности от това. Така че ние трябва да се правят жертви, за да да бъде в състояние да представлява най-много ценности. 

Така че една стойност, като 0.1, очевидно ние не можем да декларирате, че точно. Така че, вместо да представлява 0.1 правим най-добре можем да представим тази 0.100000 5 5 5. И това е доста близо, но за много приложения трябва да се тревожи за плаваща запетая неточност защото ние просто не може да представлява всички плаващи точки точно. 

Въпрос 15. Помислете кода по-долу. Ние просто печат 1 плюс 1. Така че няма трик тук. 1 плюс 1 оценява на 2, и тогава ние сме печат това. Това просто отпечатва 2. 

Въпрос 16. Сега ние сме печат характера 1 плюс 1 характер. Така че, защо това не е така отпечатване на едно и също нещо? Ами характера 1 плюс характер 1, характерът 1 има стойност ASCII 49. Така че това е наистина каза 49 плюс 49, и в крайна сметка това ще отпечата 98. Така че това не се отпечатва 2. 

Въпрос 17. Завършване на изпълнението странно долу по такъв начин, че функцията връща истина, ако п е странно и невярно, ако N е четно. Това е една велика цел за Министерството на отбраната оператора. Така че ние се аргумент нашата п ако п мод 2 е равно на 1, и това означава, че N разделен от 2 има остатък. Ако п разделен от 2 има остатък, че означава, че н е странно, така че ние се върнете вярно. Иначе ние се върне фалшиви. Вие също може да са направили н моден две равни нула, връщане фалшиви, иначе се върне вярно. 

Помислете за рекурсивно функцията по-долу. Така че, ако п е по-малка или равна на 1, върнете 1, друго връщане н пъти е на п минус 1. Така че каква е тази функция? Е, това е само факторен функция. Това е добре представена като п факторен. 

Така че въпрос 19 сега, ние искаме да вземе това рекурсивни функции. Искаме да направим това повтарящ се. И така, как да го направим? Ами за персонала решение, и отново има много начини може да са го направили че, ние започваме с този инт продукт се равнява на 1. И през тази за линия, отиваме да се умножи продукт в крайна сметка свърши с пълната факториел. Така че за инт и е равно на 2, и е по-малко от или равно на N, I ++. 

Може би се чудите защо аз се равнява на две. Е, не забравяйте, че тук трябва да се уверете се, че нашата база случай е правилно. Така че, ако п е по-малко от или равно 1, ние сме просто връщане 1. Така че тук, ние започнем да се равнява на две. Ами ако аз бяха 1, след the-- или ако п са 1, а след това в продължение на линия не изпълнява изобщо. И така, ние просто ще връщане продукт, който е един. По същия начин, ако п са нищо по-малко от 1-- ако е 0, отрицателна 1, whatever-- ние пак ще се върне 1, което е точно това, което рекурсивни версия се прави. 

Сега, ако п е по-голямо от 1, след това отиваме да се направи най-малко един повторение на този цикъл. Така че нека да кажем, че п е 5, а след това ние сме ще направим пъти продукта е равно на 2. Така че сега продукт е 2. Сега отиваме да се направи пъти продуктови равнява на три. Сега е шест. Пъти на продукта е равно на четири, сега е 24. Пъти на продукта е равно на 5, сега е 120. Така че след това в крайна сметка, ние сме връщане 120, който е правилно 5 факторен. 

Въпрос 20. Това е тази, в която трябва да попълните в тази таблица с даден алгоритъм, всичко, което сме виждали, че вписва тези алгоритмични серия пъти тези асимптотичната тичам пъти. И така, какво е алгоритъм, който е омега 1, но голям О п? Така че може да има безкрайно много отговори тук. Този, който сме виждали, вероятно най- често е само линейно търсене. 

Така че в най-добрия случай сценарий, елементът сме търсите е в началото на списъка и така на омега на 1 стъпки, първото нещо, което ние проверяваме, ние просто се връщат незабавно че ние открихме елемента. В най-лошия случай, елементът е в края, или елемент не е в списъка на всички. Така че ние трябва да се търси целия списък, всички п елементи, и това е защо е о п. 

Така че сега това е нещо, което е едновременно омега на п дневник п и големия О п дневник п. Ами най-подходящото нещо, сме виждали тук е слеят вид. Така се сливат нещо, не забравяйте, е в крайна сметка Theta п Вход N, където тета е определена ако омега както и голям О са еднакви. Както п влезете п. 

Какво е нещо, което е омега от N, О и п квадрат? Е, пак има множество възможни отговори. Тук ние се случи да се каже балон вид. Сортиране чрез вмъкване също ще работи тук. Не забравяйте, че балон на сортиране е, че оптимизация, където ако сте в състояние да получи през целия списък без да е необходимо да се направи всички суапове, след това, добре, ние може веднага да се върне, че списъкът е сортирано да се започне. Така че в най-добрия случай, това е просто омега на п. Ако това не е просто една добре сортирано списък, за да започнем с това, тогава имаме O н квадрат суапове. И накрая, ние имаме избор сортиране за п квадрат, както и омега голям O. 

Въпрос 21. Какво е цяло число преливник? Е отново, подобно на по-рано, имаме само краен брой битове да представлява цяло число, Така че може би 32 бита. Да кажем, че имаме подписан число. След това в края на краищата най-високата положително число можем да представим е 2 до 31 минус 1. Така че това, което се случва, ако се опитаме да след това нарастване, че число? Е, ние ще тръгнем от 2 до 31 минус 1, по целия път до отрицателен 2 до 31. Така че това число е преливане когато държите увеличаване, и в крайна сметка не можеш получите по-висока и тя просто обгръща целия път обратно около с отрицателна стойност. 

Какво ще кажете за препълване на буфера? Така буфер overflow-- помня какво буфер е. Това е просто парче от памет. Нещо като масив е буфер. Така препълване на буфера е, когато когато се опитвате да получите достъп до паметта след края на този масив. Така че, ако имате масив с размер 5 и пробвате достъп до конзолата масив 5 или 6 или скоба скоба 7, или нещо повече за край, или дори нещо below-- скоба масив отрицателен 1-- всички от тях са препълване на буфера. Вие докосвате памет в лоши отношения. 

Въпрос 23. Така че в това, което трябва да приложат strlen. И ние ви кажа, че можете да Предполагам, и няма да бъде нула, така че не е нужно да се направя някоя проверка за нищожна. И има много начини бихте могли да са направили това. Тук ние просто приемете ясно. Започваме с брояч, п. п е брои колко символа са там. Така че ние започваме на 0, а след това обхождане на целия списък. 

Има и скоба 0 равна на нула терминатор характер? Не забравяйте, че търсим нулевата терминатор характер за да се определи колко време ни е низ. Това ще прекрати всяка съответна низ. Така е и конзола 0 равен до нула терминатор? Ако не е, тогава ние ще Посетете и скоба 1, а скоба 2. Ние не спирай, докато ние намерите нула терминатор. След като сме го намерили, тогава п съдържа общата дължина на низа, и само можем да се върнем това. 

Въпрос 24. Така че това е тази, в която Трябва да се направи компромис. Така че едно нещо е добро в едно начин, но по какъв начин това е лошо? Така че тук, се слеят вид тенденция да да бъде по-бързо от балон вид. Като каза that-- добре, има са няколко отговора тук. Но главното е, че балон сортиране е омега на п за сортиран списък. 

Не забравяйте, че на маса ние просто видяхме по-рано. Така балон сортира омега на п, в най-добрия случай е, че е в състояние само да отидем списъка веднъж определи Ей това нещо е вече сортирано и връщане. Сортиране чрез сливане, без значение какво което правите, е омега на п дневник п. Така че за сортиран списък, балон нещо ще бъде по-бързо. 

Сега какво ще кажеш за свързани списъци? Така свързан списък може да расте и да се намалят за да се поберат най-много елементи, както е необходимо. Като каза that-- така обикновено прякото сравнение ще бъде свързан списък с масив. Така че, въпреки че масиви може лесно да растат и да се свие за да се поберат най-много елементи колкото е необходимо, списък свързан в сравнение с array-- на масив има произволен достъп. Ние можем индекс във всеки специално елемент на масива. 

Така че за свързан списък, не можем да просто отидете на петия елемент, ние трябва да преминават от началото докато стигнем до петия елемент. И това няма да ни попречи правиш нещо като двоично търсене. Говорейки за двоично търсене, двоично търсене има тенденция да бъде по-бързо, отколкото линейно търсене. Като каза that-- Така че, един възможен нещо е, че не можеш да направиш двоичен търсене на свързани списъци, можете да го направите само за масиви. Но може би по-важното е, не можеш да направиш двоично търсене на масив, който не е сортиран. Авансово може да се наложи да се справи масива, и едва след това може да правиш двоично търсене. Така че, ако нещо не е сортирани да започнем с това, след това линейно търсене може да бъде по-бързо. 

Въпрос 27. Така че помислете програмата по-долу, който ще бъде в следващия слайд. И това е тази, в която ние сме ще искате да посочва изрично стойностите за различните променливи. Така че нека да погледнем това. 

Така се подредят един. Имаме INT х е равен на 1. Това е единственото нещо, което се е случило. Така че в един ред, ние виждаме в нашия маса, че Y, А, В, и TMP всички затъмнен вън. Така че това, което е х? Ами ние просто го определя като равна на 1. И след това втора линия, добре, ние виждаме, че у е до 2, и таблицата е вече попълва за нас. Така че х е 1 и Y е 2. 

Сега, третия ред, ние сме сега вътре функция суап. Какво можем да премине, за да сменяте? Минахме амперсанд х за А, и амперсанд у за б. Когато проблема по-рано посочва, че адресът на х е 0x10, както и адреса на у е 0x14. Така че А и Б са равни 0x10 и 0x14, съответно. 

Сега в третия ред, какви са х и у? Е, нищо не се е променило за х и у в този момент. Въпреки че те са във вътрешността на главен стека рамка, те все още имат едни и същи стойности са направили преди. Ние не са променени всяка памет. Така че х е 1, Y е 2. Добре. Така че сега ние казахме инт ПТУ равна на звезда а. Така че в четвърти ред, всичко е същата, с изключение на ТМР. Ние не са се променили всички ценности от нищо друго, освен за ПТУ. Ние сме за създаване ПТУ равна на звезда а. Какво е звезда? Е, на пункта до х, така звезда ще се равнява х, което е едно. Така че всичко се копира надолу и ПТУ е 1. 

Сега на следващия ред. Star един равнява звезда б. Така по ред five-- и отново, всичко е една и съща независимо освен звезда е. Какво е звезда? Е, ние току-що каза звезда е х. Така че ние променяме х на равно звезда б. Какво е звезда б? у. б точки на ш. Така звезда б е ш. Така че ние сме за създаване х равно на х, и всичко останало е същото. Така ние виждаме в следващия ред, че х е сега 2, а останалите са просто копира надолу. 

А в следващия ред, звезда б равнява ПТУ. Е, ние току-що каза звездата б е ш, така че ние сме за създаване у равна на ПТУ. Всичко останало е същото, така че всичко бива копиран надолу. Ние сме за създаване у равна на TMP, което е един, и всичко останало е същото. 

Сега най-накрая, линия седем. Ние сме обратно в основната функция. Ние сме след суап е завършен. Ние загубихме а, б, и ПТУ, но в крайна сметка ние не се променят всички стойности от нищо в този момент, ние просто копирайте х и у надолу. И ние виждаме, че X и Y са сега 2 и 1 вместо 1 и 2. Размяната е изпълнена успешно. 

Въпрос 28. Да предположим, че се натъкнете съобщения за грешки долу в работно време през следващата година като CA или TF. Съветва как да се определи всеки един от тези грешки. Така неопределено позоваване на GetString. Защо може да видите това? Е, ако студентът е с помощта GetString в кода си, те са правилно с # включени cs50 точка Н за включване на cs50 библиотеката. 

Е, това, което правят трябва да се определи тази грешка? Те трябва да се направи пробив lcs50 в командния ред, когато компилирате. Така че, ако те не преминават трясък тире lcs50, те са няма да имат реален код, който реализира GetString. 

Въпрос 29. Мълчаливо се обявява библиотека функция strlen. Е това сега, те не са направи правилното хеш включва. В този конкретен случай, заглавната част на файла те трябва да се включат е низ точка з, включително низ точка ч, сега на student-- сега компилатор има достъп до декларации за strlen, и тя знае, че вашият код използва strlen правилно. 

Въпрос 30. Повече процента реализации от аргументи данни. И така, какво е това? Добре си спомням, че те процента signs-- как те са свързани с ФОРМАТ. Така че в ФОРМАТ можем да percent-- можем да отпечатате нещо като процент и обратно наклонена черта п. Или можем да отпечатате като процента аз, пространство, на сто и, пространство, процента аз. Така за всяка от тези процента признаци, от които се нуждаем да премине променлива в края на ФОРМАТ. 

Така че, ако ние кажем ФОРМАТ скоба процента и обратно наклонена черта н близки скоба, добре, да кажем, че ние сме щеше да отпечатате цяло число, но след това не преминават ФОРМАТ цяло число действително да отпечатате. Така че тук повече процента реализации, отколкото аргументи данни? Това се казва, че ние имаме цял куп процента, и ние не разполагат с достатъчно променливи действително да запълни в тези проценти. 

И тогава определено, за въпрос 31, определено губи 40 байта в един блок. Така че това е грешка Valgrind. Това се казва, че някъде в кода си, имате разпределение, което е 40 байта голям, така че можете malloced 40 байта, и никога няма да го остави. Най-вероятно просто трябва да намери някаква памет течове, и да намерят мястото, където трябва да се освободи този блок памет. 

И въпрос на 32 г. невалиден запис с размер 4. Отново това е грешка Valgrind. Това не трябва да направите, с изтичане на памет предприятието. Това е най-likely-- Искам да кажа, това е някаква невалидни права памет. И най-вероятно това е някакъв сортиране на препълване на буфера. Когато имате един масив, може би цяло число масив, и нека казват, че е на площ 5, и се опитват да се докоснат масив конзола 5. Така че, ако се опитате да пише, че стойност, която не е част от паметта които всъщност имат достъп до тях, и така че започваш да се получи тази грешка, казва невалиден запис с размер 4. Valgrind ще признае, че сте се опитва да се докоснат памет неподходящо. 

И това е всичко за quiz0. Аз съм Роб Боудън, а това е CS50.