Роб Боуден: Привет, я Роб Боуден, и давайте поговорим о 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 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.