Роб Боуден: Привіт, я Роб Боуден, і давайте поговоримо про quiz0. Так, перше питання. Це питання, де вам потрібно закодувати число 127 в бінарних цибулин. Якщо ви хотіли, ви могли б зробити звичайне перетворення від bi-- або, з десятковою в двійкову. Але що, ймовірно, буде взяти багато часу. Я маю на увазі, ви можете з'ясувати, що, ОК, 1 знаходиться в там, 2 знаходиться в там, 4 знаходиться в там, 8 знаходиться в там. Легше чином, 127 128 мінус один. Це крайня ліва лампочка 128-біт. Так 127 насправді просто все з інших лампочок, так ось крайня ліва лампочка мінус 1. Ось саме для цього питання. 

Питання одне. Отже з 3 битами можна представляють 8 різних значень. Чому ж тоді, 7 найбільшу невід'ємне десяткове ціле можна уявити? Ну, якщо ми можемо тільки представляють 8 різних значень, те, що ми збираємося бути представляють значення від 0 до 7. 0 займає одне із значень. 

Питання друге. З п бітів, скільки різних Значення можуть ви уявляєте? Так, з п бітів, у вас є 2 Можливі значення для кожного біта. Таким чином, ми маємо два можливих значення для перший біт, 2 можливих значення для другого, 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, який був частково натякнути відповіді на цю проблему. 

Питання п'ять. У нас є цей подряпин скрипт, який повторювати 4 рази арахісове масло желе. Отже, як же ми тепер код, що в C? Ну, у нас є here-- частина жирним шрифтом це єдина частина, потрібно було реалізовувати. Тому у нас є 4 петлі, який зациклення 4 раз, Printf-ки арахісове масло желе, з нового рядка, як проблема просить. 

Питання шість, ще одна проблема подряпин. Ми бачимо, що ми знаходимося в назавжди петлі. Ми говоримо, що змінна I а потім збільшуючи I на 1. Тепер ми хочемо зробити, що в С. Є декілька способів ми могли б зробити це. Тут ми випадково закодувати назавжди петля як деякий час (правда). Таким чином, ми оголошуємо змінну I, просто у нас був змінну я в порожньому. Оголосіть змінну I, і назавжди в той час як (правда), ми говоримо, змінну я. Так Printf% i-- або ви могли б використовувати% D. Ми говоримо, що змінна, і потім збільшити його, я ++. 

Питання сім. Тепер ми хочемо зробити щось дуже схоже Маріо точка з з проблеми встановіть один. Ми хочемо, щоб роздрукувати ці хештеги, ми хочемо, щоб надрукувати п'ять трьома прямокутника цих хешів. Так як ми збираємося це зробити? Ну, ми дамо вам цілий купа коду, і ви просто повинні заповнити функції друку сітки. 

Отже, що ж PrintGrid виглядати? Ну ти мимо Ширина і висота. Тому у нас є зовнішнє 4 цикл, який циклу по всіх рядках цей Сітка, що ми хочемо, щоб роздрукувати. Тоді у нас є між вкладений 4 петлі, це друк за кожного шпальти. Таким чином, для кожного рядка, ми друкуємо для кожен стовпець, один хеш. Потім в кінці рядка ми виводимо один нова лінія для переходу до наступного рядка. І ось саме для всієї сітки. 

Питання вісім. Функція як PrintGrid, як кажуть, є побічний ефект, але не повернення Значення. Поясніть відмінність. Так що це залежить від вас пам'ятати що побічним ефектом є. Ну, повернення value-- ми знаємо PrintGrid НЕ є значення, що повертається, так як тут він каже недійсними. Тому все, що не повертає насправді не нічого повертати. Так в чому ж побічний ефект? Ну, це побічний ефект є що-небудь, щось зберігається після кінцях функціональних що було не тільки що повернувся, і це було не просто з входів. 

Так, наприклад, ми могли б змінити глобальну змінну. Це було б побічним ефектом. В даному конкретному випадку, дуже важливо побічний ефект друкує на екран. Так, що є побічним ефектом що PrintGrid має. Ми друкуємо ці речі на екран. І ви можете думати про що в якості побічного ефекту, так це те, що зберігається після ця функція закінчується. Це те, що виходить за рамки цієї функції, що, в кінцевому рахунку змінюється, Вміст екрану. 

Питання дев'ять. Розглянемо програму нижче, до яких номера рядків були додані до заради обговорення. Таким чином, в цій програмі ми просто називаючи GetString, зберігати його в цієї змінної х, а потім друк цієї змінної с. Добре. Так поясніть, чому лінія одна присутня. #include CS50 точка ч. Чому ми повинні #include CS50 точка годину? Ну ми називаємо Функцію GetString, і GetString визначається в бібліотеці CS50. Так що, якщо у нас не було #include CS50 точка ч, ми хотіли б отримати, що неявне оголошення помилки функції GetString від компілятора. Так що ми повинні включати в себе library-- ми повинні включити заголовний файл, або компілятор буде визнати, що GetString існує. 

Поясніть, чому лінія двох присутня. Так стандарт ю точка ч. Це точно так же, як попередній задачі, за винятком того, замість того, щоб мати справу з GetString, ми говоримо про Printf. Так що, якщо ми не говоримо, що потрібно включити стандартний IO точка годину, то ми не були б в змозі використовувати функцію PRINTF, бо компілятор не знаю про це. 

Why-- яке значення з анулюванню в четвертому рядку? Так от у нас Int основний (порожнечу). От тільки кажуть, що ми не отримують будь-якої командного рядка Аргументи основною. Пам'ятайте, що ми могли б сказати Int Основні INT ARGC рядок ARGV дужки. Так ось, ми просто скажемо, порожнеча сказати ми ігнорують аргументи командного рядка. 

Поясніть, по відношенню до пам'яті, точно що GetString відповідно шість повертається. GetString повертається блок пам'яті, масив символів. Це дійсно повернення покажчик на перший символ. Пам'ятайте, що рядок є символ зірки. Так с є покажчиком на перший характер в будь рядок що користувач ввів з клавіатури. І, що пам'ять, виявляється, malloced, так що пам'ять в купі. 

Питання 13. Розглянемо нижче програму. Так що все це робить програма є Printf-ки 1, поділеній на 10. Тому, коли складається і виконується ця програма виходи 0.0, навіть при тому, що 1 ділиться на 10 становить 0,1. Так чому ж це 0.0? Ну, це тому, що цілочисельного ділення. Так 1 являє собою ціле число, 10 є цілим числом. Так 1 ділиться на 10, все, трактується як цілі числа, і в C, коли ми робимо цілий підрозділ, ми усікти будь-яку десяткову точку. Так 1 ділиться на 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. І це досить близько, але для багатьох додатків вам не доведеться турбуватися про плаваючою комою неточність, бо ми просто не можемо уявити Все плаваючою точки точно. 

Питання 15. Розглянемо код. Ми просто друк 1 плюс 1. Так ні Хитрість тут. 1 плюс 1 дорівнює 2, і Потім ми друку, що. Це просто друкує 2. 

Питання 16. Тепер ми друку персонаж 1 плюс характер 1. Так чому ж це не друкувати одне й те саме? Ну персонаж 1 плюс характер 1, характер 1 має ASCII значення 49. Так що це насправді каже 49 плюс 49, і в кінцевому рахунку, це буде друкувати 98. Так що це не друкує 2. 

Питання 17. Завершити реалізацію непарних нижче таким чином, що функція повертає істину, якщо п непарне і помилково, якщо п парне. Це велика мета для мод оператора. Тому наша аргумент п, якщо н модулю 2 дорівнює 1, а що означає, що п ділиться на 2 мав залишок. Якщо п ділиться на 2 мав залишок, що означає, що п непарне, тому ми повернемося вірно. Інакше ми повернутися помилковим. Ви також могли б зробити п по модулю 2 рівних нулю, повернутися помилковим, інакше повертає істину. 

Розглянемо рекурсивную функцію нижче. Таким чином, якщо N менше або дорівнює 1, повертають 1, ще повернення п раз е н мінус 1. Так що ж таке ця функція? Ну, це просто факторіала. Це красиво представлені як н факторіала. 

Так питання 19 зараз, ми хочемо, щоб скористатися цією рекурсивної функції. Ми хочемо зробити це ітеративний. Так як же нам це зробити? Ну для персоналу Рішення, і знову є кілька способів ви могли б зробити що ми починаємо з цього Int продукту дорівнює 1. І протягом усього цього для петлі, ми збираємося щоб бути множення продукт в кінцевому рахунку, в кінцевому підсумку з повною факторіала. Так що для междунар я дорівнює 2, я це менше або дорівнює N, I ++. 

Ви можете здивуватися, чому я дорівнює 2. Ну, пам'ятаєте, що тут ми повинні переконатися, що наш базовий варіант є правильним. Таким чином, якщо N менше або дорівнює 1, ми просто повернення 1. Так ось тут, у нас починаються я дорівнює 2. Ну, якби я був один, то the-- або якщо н були 1, то для петлі не виконуватиметься взагалі. І так, ми були б просто повернення продукт, який є 1. Точно так же, якщо н були що-небудь менш 1-- якби це було 0, негативний 1, whatever-- ми б досі повертаються 1, а це саме те, що рекурсивна версія робить. 

Тепер, якщо п більше 1, то ми збираємося робити щонайменше один ітерації цього циклу. Так скажімо, п 5, то ми збираюся робити раз продукту дорівнює 2. Так що тепер продукт 2. Тепер ми збираємося зробити раз продукт дорівнює 3. Тепер це 6. Раз продукту дорівнює 4, тепер це 24. Раз продукту дорівнює 5, тепер це 120. Отже, в кінцевому рахунку, ми повертаємося 120, яка є правильною 5 факторіала. 

Питання 20. Це те місце, де ви повинні заповнити В цій таблиці з будь даний алгоритм, все, що ми бачили, що підходить ці алгоритмічний пробіг раз ці асимптотические раз бігти. Так що являє собою алгоритм, є омегою 1, але більша O п? Так не може бути безкінечно багато відповідей тут. Той, який ми бачили, ймовірно, найбільш часто це просто лінійний пошук. 

Таким чином, в кращому випадку, Сценарій, пункт ми шукаю знаходиться на початок списку і так омега 1 кроків, Перше, що ми перевіряємо, ми просто негайно повернутися що ми знайшли пункт. В гіршому випадку, елемент знаходиться в кінці, або деталь немає в списку взагалі. Тому ми повинні шукати Весь список, все п елементи, і саме тому це о н. 

Так що тепер це щось, це і омега н лог н, і велика O н лог н. Ну найбезпосередніший стосунок річ ми бачили тут зливаються роду. Так зливаються роду, пам'ятайте, в кінцевому рахунку, тета н лог п, де тета визначається якщо обидва омега і великий виведення однакові. Обидва п § п. 

Щось, що це омега п, і 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, S кронштейна 2. Ми не продовжуємо, поки ми знайти нульовий термінатор. Після того, як ми знайшли його, то п містить загальна довжина рядка, і ми можемо просто повернути це. 

Питання 24. Так що це те місце, де ви повинні зробити компроміс. Так що, одне добре в одному спосіб, але яким чином це погано? Так от, сортування злиттям, як правило, швидше, ніж бульбашкового сортування. Сказавши that-- добре, є кілька відповідей тут. Але головний з них, що бульбашкова сортування є омегою п для відсортованого списку. 

Пам'ятайте, що стіл, який ми тільки що бачили раніше. Так міхур сортує омегу н, в кращому випадку є його можливість просто перейти Список відразу, визначити агов це справа вже сортуються, і повернення. не злиття роду, незалежно від того, що ви робите, є омега н лог н. Так для відсортованого списку, міхур роду буде швидше. 

Тепер те, що про пов'язані списків? Так зв'язаний список може збільшуватися і зменшуватися щоб відповідати стільки елементів, скільки необхідно. Сказавши that-- так Зазвичай пряме порівняння буде пов'язаний список з масивом. Таким чином, навіть при тому, що масиви можуть легко нарощувати і змінювати щоб відповідати як багато елементів в міру необхідності, пов'язано список порівняно з array-- ап Масив має довільний доступ. Ми можемо індекс в будь Зокрема елемент масиву. 

Так що для зв'язаного списку, ми не можемо просто піти в п'ятий елемент, ми повинні пройти від початку поки ми не отримаємо до п'ятого елемента. І що відбувається, щоб перешкодити нам робити щось на зразок бінарного пошуку. Говорячи про бінарного пошуку, бінарний пошук як правило, швидше, ніж лінійний пошук. Сказавши that-- так, єдино можливим є те, що ви не можете зробити бінарний пошук по зв'язкові списки, Ви можете зробити це тільки з масивами. Але, ймовірно, ще більш важливо, Ви не можете зробити бінарний пошук на масиві, яка не сортується. Щирі вам може знадобитися для сортування масив, і тільки потім можна ви бінарний пошук. Так що, якщо ваша річ НЕ відсортованого для початку, Потім лінійний пошук може бути швидше. 

Питання 27. Так вважають програму нижче, який буде в наступному слайді. І це те місце, де ми знаходимося захоче явно вказати значення для різних змінних. Отже, давайте поглянемо на що. 

Так шикуються один. У нас є інтервал х дорівнює 1. Це єдине, що трапилося. Таким чином, на першій лінії, ми бачимо в нашому Таблиця, що у, а, б, і TMP все затемнені. Так що ж таке х? Ну ми просто встановити його рівним 1. А потім вибудовуються два, ну, ми бачимо, що у встановлений у 2, і таблиця вже заповнюється для нас. Так х представляє 1 і Y 2. 

Тепер, лінія три, ми зараз всередині функції підкачування. Що ми пройти, щоб поміняти? Ми пройшли амперсанд х для і амперсанд у до б. Де проблема раніше зазначено, що адреса X є 0x10, а також адресу у є 0x14. Так і б дорівнюють 0x10 і 0x14, відповідно. 

Тепер на третій лінії, якими є хну? Ну, нічого не змінилося о х і у в цій точці. Навіть при тому, що вони всередині основного кадру стека, вони досі те ж саме Значення раніше. Ми не змінили будь-яку згадку. Так х дорівнює 1, у дорівнює 2. Добре. Так що тепер ми сказали INT TMP одно зірка. Таким чином, на четвертому рядку, все, те ж саме для TMP винятком. Ми не змінили які-небудь значення ні про що для TMP крім. Ми створюємо TMP рівну зірка. Що таке зірка? Ну, а точки х, так зірки збирається рівній х, який є 1. Так що все копіюється вниз, і TMP встановлюється в 1. 

Тепер наступний рядок. Зірка дорівнює зоряний б. Так по лінії five-- добре знову, все це те ж саме, за винятком всі зірки є. Що таке зірка? Ну, ми тільки що сказали, зірка є х. Таким чином, ми міняємо х на рівну зірки б. Що таке зірка б? у. б вказує на у. Так зірка б це у. Так ми встановлюємо х одно у, а все інше те ж саме. Отже, ми бачимо в наступному ряду, що х є зараз 2, а решта просто копіюються вниз. 

Тепер в наступному рядку, зірка б дорівнює TMP. Ну, ми тільки що сказали, зірка Ь у, так ми встановлюємо у одно TMP. Все інше те ж саме, таким чином, все копіюється вниз. Ми встановлюємо у рівну TMP, який є один, а все інше те ж саме. 

Тепер, нарешті, лінія сім. Ми повернулися в головній функції. Ми після заміни закінчена. Ми втратили A, B, і TMP, але в кінцевому рахунку ми Не зміна значень ні про що в цей момент, ми просто скопіювати хну вниз. І ми бачимо, що х і у Тепер 2 і 1 замість 1 і 2. Своп успішно виконала. 

Питання 28. Припустимо, що ви зіткнулися з повідомлення про помилки нижче протягом робочого дня в наступному році, як Каліфорнія або TF. Порадьте, як виправити кожен з цих помилок. Так визначено посилання на GetString. Чому ви могли б бачити це? Ну, якщо студент використовує GetString в своєму коді, вони правильно хеш включені CS50 точка ч, щоб включити бібліотеку CS50. 

Ну, те, що вони потрібно виправити цю помилку? Вони повинні зробити тире lcs50 на командного рядка, коли вони компіляції. Так що, якщо вони не проходять брязкіт тире lcs50, вони не матиме фактичне Код, який реалізує GetString. 

Питання 29. Побічно оголошенні бібліотека функцій STRLEN. Ну це зараз, у них їсти не зроблено належне хеш включають. В даному конкретному випадку, файл заголовка вони повинні включати в себе це рядок точка ч, і в тому числі рядка точка ч, в даний час student-- тепер компілятор має доступ до заяви STRLEN, і він знає, що ваш код правильно використовуючи STRLEN. 

Питання 30. Ще відсотків перетворення ніж аргументів даних. Так що ж це? Ну, пам'ятаєте, що ці відсотки signs-- як вони ставляться до PRINTF. Таким чином, в Printf ми могли б відсотків, що ми могли б надрукувати що-небудь як відсотків я зворотну косу риску н. Або ми могли б надрукувати, як відсоток I, простір, відсотків я, простір, відсотків я. Таким чином, для кожного з тих, знаки відсотка, ми повинні передати змінну в кінці Printf. 

Так що, якщо ми говоримо, PRINTF дужка відсотків я зворотну косу риску н тісні Хлопець, добре, ми говоримо, що ми в друк ціле, але тоді ми не проходять Printf ціле число насправді друкувати. Так ось більше відсотків перетворення, ніж аргументів даних? Це говорить, що у нас є ціла купа відсотків, і у нас немає достатньої кількості змінних насправді заповнити ці відсотки. 

І тоді, безумовно, у відповідь на питання 31, виразно втратив 40 байт в одному блоків. Так що це помилка Valgrind. Це говорить, що десь в коді, у вас є розподіл, який 40 байт великий, так що ви malloced 40 байт, і ви ніколи не звільнив його. Швидше за все вам просто потрібно щоб знайти витік пам'яті, і знайти, де вам потрібно звільнити цей блок пам'яті. 

І питання 32, недійсним запису про розмір 4. Знову ж таки це помилка Valgrind. Це не потрібно робити з витоками пам'яті тепер. Це, скоріше likely-- Я маю на увазі, що це свого роду недійсних прав пам'яті. І, швидше за все, це який- роду переповнення буфера. Де у вас є масив, може бути, цілочисельний масив, і давайте кажуть, що це з розміру 5, і ви спробуйте доторкнутися масиву кронштейн 5. Так що, якщо ви спробуєте написати, що Значення, це не шматок пам'яті що у вас дійсно є доступ до, і так що ви збираєтеся отримати цю помилку, кажучи неприпустимий записи розміром 4. Valgrind збирається визнати ти прагнучи торкнутися пам'ять недоречно. 

І ось саме для quiz0. Я Роб Боуден, і це CS50.