>> [Играет музыка]
>> ANDI Пэн: Добро пожаловать в неделю 3 раздела.
Спасибо, что вы, ребята, все приходящие на в этом более раннее время начала сегодня.
Мы получили хороший, немного интимная группа сегодня.
Так что надеюсь, мы доберемся до отделка, пожалуй, рано,
немного пораньше.
Так быстро, просто некоторые Анонсы повестке дня сегодня.
Прежде чем мы начнем, мы собираюсь просто перейти
некоторые краткие материально-технических вопросов, PSET вопросы, Инструктаж, такие вещи, как, что.
И тогда мы будем нырять прямо в.
Мы будем использовать отладчик GDB под названием, чтобы начать развенчание наш код, который Дэвид
объяснил в лекции в другой день.
Мы пойдем в течение четырех видов рода.
Мы пойдем на них довольно быстро так как они довольно интенсивно.
Но знайте, что все слайды и Исходный код всегда онлайн.
Так что не стесняйтесь, в вашем прочтении, чтобы вернуться назад и взглянуть на это.
>> Мы пойдем через асимптотическая обозначения, которые
это просто причудливый способ сказать "время автономной работы",
где у нас есть большой O, которая Дэвид объяснил в лекции.
И у нас также есть Omega, который это нижняя граница времени выполнения.
И мы будем говорить немного больше в глубине о том, как эти работы.
И, наконец, мы пойдем по бинарного поиска, потому что многие из вас, кто уже
взглянул на ваших psets, наверное, знаете, что что это вопрос, который находится в вашем PSET.
Таким образом, вы будете все будут счастливы что мы рассмотрим это сегодня.
>> И, наконец, за ваш раздел обратной связи, я на самом деле
осталось около 15 минут при конец просто перейти
логистика pset3, какие-либо вопросы, может быть, немного руководством, если хотите,
прежде чем мы начнем программирование.
Так давайте попробуем получить через материал довольно быстро.
И тогда мы можем провести некоторое время принимая больше вопросов для PSET.
ХОРОШО.
>> Быстро, поэтому лишь немногие Анонсы прежде чем мы начнем сегодня.
Во-первых, добро пожаловать, чтобы сделать это через два ваших psets.
Я взглянул на your-- Да, давайте получить аплодисменты для этого одного.
На самом деле, я был очень, действительно впечатлен.
Я оцениваются первый PSET для вас, ребята на прошлой неделе и вы, ребята, сделали невероятное.
>> Стиль был на момент кроме нескольких замечаний.
Убедитесь, что вы всегда Комментируя свой код.
Но ваши psets были на точке.
И держать его.
И это хорошо для грейдера в видеть, что вы, ребята, положить
как много усилий в вашем стиле и ваш дизайн в коде
что мы хотели бы, чтобы вы видите.
Так я передаю по моей благодарности для остальных ТП.
>> Однако есть Несколько вопросов тант
Я просто хочу, чтобы перейти на что как бы жизнь
и много другого ТП «живет немного легче.
Во-первых, я заметил это мимо week-- как многие из вас
были работает на check50 код, прежде чем представить?
ХОРОШО.
Таким образом, каждый должен делать check50, because-- secret-- мы на самом деле
запустить check50 как часть нашей правоте скрипты для тестирования кода.
Так что, если ваш код не удается check50, по всей вероятности,
это, вероятно, будет потерпеть неудачу также наш чек.
Иногда вы, ребята, есть правильные ответы.
Мол, в жадные, некоторые из у вас есть правильные цифры,
Вы просто распечатать некоторые дополнительные вещи.
И, что дополнительный материал на самом деле не проходит проверку,
потому что компьютер не знаю, что он ищет.
И так будет просто запустить через, видеть, что ваш вывод не
соответствует тому, что мы ожидаем ответ быть, и отметьте, что это неправильно.
>> И я знаю, что произошло в некоторые из ваших случаях на этой неделе.
Так что я вернулся и вручную regraded код каждого.
В будущем, хотя, Пожалуйста, убедитесь, что
что вы работаете проверить 50 на коде.
Потому что это своего рода боли в ТП чтобы вернуться и вручную реклассификацию
каждый PSET для каждого один, немного пропустил экземпляр.
Так что я не снимал ни одного очка.
Я думаю, что, может быть, снял один или два для проектирования.
В будущем, хотя, если Вы не справляются check50,
точки будут приняты от правильности.
>> Кроме того, в psets за пятницам в полдень.
Я думаю, что есть семь минут в конце льготного периода, что мы даем вам.
За время Гарвардского, они позволили семь минут поздно, чтобы всем.
Так вот в Йельском университете, мы будем придерживаться, что хорошо.
Но довольно много, в 12:07, если ваш PSET это не в том,
это будет отмечен как поздно.
И поэтому, хотя она отмечается а поздно, я TA--
прежнему будет классификации ваши psets.
Таким образом, вы все еще будете видеть сорт появляются.
Тем не менее, известно, что в конец семестра,
все поздние psets будет просто автоматически обнуляется с помощью компьютера.
>> Мы делаем это по двум причинам.
Один из них, иногда мы получаем извинился, как отговорки деканатов,
позже, что я не знаю, о еще.
Таким образом, мы хотели, чтобы убедиться, что мы классификации все только в том случае, как, я
отсутствует простить декана.
А во-вторых, имейте в ум, вы все еще можете
падение один PSET, что обладает полными точки размах.
И таким образом, мы хотели, чтобы оценка все ваши psets только
чтобы убедиться, что ваш осциллографа есть и вы пытаетесь их.
Таким образом, даже если это поздно, вы все еще будете получить кредит для области видимости точек, я думаю.
>> Так Мораль история, сделать Убедитесь, что ваш psets в по времени.
И если они не находятся в на время, знаю, что это не здорово.
Да, прежде чем я двигаться дальше, кто-нибудь есть любые вопросы, касающиеся обратной связи Pset?
Да.
>> АУДИТОРИЯ: Вы сказали, мы может упасть один из psets?
>> ANDI Пэн: Да.
Так что в целом девять psets в течение семестра.
И если у вас есть область points-- так просто сфера,
довольно много, вы попыткой выполнения Проблема, вы положить в время,
вы показываете, что вы имеете продемонстрировали вы читали спецификации.
Это довольно много возможностей.
И если вы выполняете Сфера точки, мы
может упасть самая низкая одним из полном объеме.
Так вот в ваших интересах, чтобы заполнить и попробовать все PSET.
>> Даже если upload-- ни один из им работать, загружать их все.
И тогда мы будем, мы надеемся, смогут дать вам некоторые из этих точек обратно.
Круто.
Другие вопросы?
Отлично.
>> Во-вторых, офис hours-- несколько быстрые заметки о рабочих часов.
Итак, сначала приходят в начале недели.
Никто не когда-нибудь в Приёмные часы по понедельникам.
Christabel пришли к Приёмные часы прошлой ночью.
Да, Christabel.
И что мы имеем в офисе часов прошлой ночью, Christabel?
>> АУДИТОРИЯ: У нас было мороженое.
>> ANDI Пэн: Так что это правильно, мы должны были мороженое на офисных часов вчера вечером.
Хотя я не могу обещать вам, что мы будем иметь мороженое в рабочее время
каждую неделю, что я могу обещать вам, является то, что будет значительно
лучше студент соотношение TA.
Как законно, это как три к одному.
Принимая во внимание, что с контрастируют Четверг, у вас есть около 150
действительно подчеркнул детей и не мороженое.
И это просто не продуктивно для всех.
Так Мораль этой истории в том, прийти пораньше в рабочее время и хорошие вещи
случится.
>> Кроме того, быть готовыми, чтобы задать вопросы.
Вы знаете?
Независимо от того, ТА, я думаю, говорили,
мы получали пару студентов которые приходят в четверг на, вроде бы, 10:50
не прочитав спецификацию будучи, как мне помочь, помоги мне.
К сожалению, в тот момент, есть не так много мы можем сделать, чтобы помочь вам.
Так что приезжайте в начале недели.
Приходите пораньше, чтобы рабочее время.
Будьте готовы задавать вопросы.
Убедитесь, что вы, как студент, находятся там, где
Вы должны быть так, что ТП может направлять вас вместе
что и часы офиса должны быть выделены для.
>> Во-вторых, так что я знаю профессоров хотел удивить нас с тестами.
Я был профессором те как, йо, кстати,
помните, что среднесрочный у вас есть следующий понедельник.
Да, я не знаю, о том, что среднесрочный.
Так что я собираюсь быть, что ТА что напоминает вам все, что викторину
0-- потому что, вы знаете, мы CS.
Теперь, когда мы сделали массивы, вы получите почему это викторина 0, не викторины 1, а?
ХОРОШО.
О, я получил некоторые смешки на том, что один.
ХОРОШО.
>> Так викторины 0 будет 14 октября, если Вы находитесь в разделе понедельник-среду
и 15 октября, если вы находитесь в раздел вторник-четверг.
Это не распространяется на тех из вас, в Гарварде
who-- Я думаю, вы все будете принимать ваши опросы на 14-м.
>> Так что, да, на следующей неделе, если Дэвид, в лекции, идет,
да, так об этом Тест на следующей неделе, вы все
не будут шокированы, потому что вы пришли в разделе
и вы знаете, что ваш Тест 0 в течение двух недель.
И мы будем иметь отзыв сессий и все.
Так что не беспокойтесь о бояться за это.
Любые вопросы before-- какие-либо вопросы на всех касающимся технических вопросов,
классификации, офисная часов, секции?
Да.
>> АУДИТОРИЯ: Так викторины будет на лекции?
>> ANDI Пэн: Да.
Так викторины, я думаю, 60 минут, выделенные в этом временном интервале
что вы будете просто взять в лекционном зале.
Таким образом, вы не должны прийти в на, вроде бы, случайного 7:00 PM.
Все хорошо.
Да.
Круто.
>> Все в порядке.
Итак, мы собираемся, чтобы ввести понятие для вас
На этой неделе, что Дэвид уже вроде из затронули в лекции на прошлой неделе.
Это называется GDB.
И, как многие из вас, в то время как в курс написания psets,
заметил большую кнопку, которая говорит "Отладка" на верхней части IDE?
ХОРОШО.
Так что теперь мы на самом деле получить, чтобы раскопать тайна какой то кнопки на самом деле
делает.
И я гарантирую вам, что это красивая, красивая вещь.
>> Так до сих пор, я думаю, там было две вещи
студенты были, как правило, делать при отладке psets.
Один из них, они либо добавить в Е () - так каждые несколько линий,
они добавляют в Е () - ой, что это переменная?
О, что это переменная now-- и вы вроде увидеть прогрессирование
ваш код, как это работает.
Или второй способ сделать детей что они просто написать целую вещь
а затем перейти, как это в конце концов.
Надеюсь, это работает.
Я гарантирую вам, GDB лучше чем оба из этих методов.
Да.
Так что это будет ваш новый лучший друг.
Потому что это красивая вещь которые визуально отображает как
что ваш код делает в определенный момент
а также то, что все ваши переменные проведения,
как то, что их значения, в этой конкретной точке.
И таким образом, вы можете действительно установить точки останова в коде.
Вы можете запустить через линию за линией.
И GDB будет просто для Вы, отображается для вас,
то, что все ваши переменные которые, что они делают,
что происходит в коде.
И таким образом, это так легче увидеть
что вместо происходит из-тов PRINTF или записывая свои заявления.
>> Таким образом, мы будем делать пример этом позже.
Таким образом, это кажется немного абстрактным.
Не беспокойтесь, мы не будем делать примеры.
И так, по существу, три крупнейших, Наиболее используемые функции вам нужно в GDB
являются Далее, перешагнуть и шаг в кнопки.
Я собираюсь возглавить есть, на самом деле, прямо сейчас.
>> Так может вы, ребята, все видеть, что или я должен увеличить немного?
В спину, вы можете видеть, что?
Должен ли я увеличить?
Только немного?
Ладно, круто.
Там мы идем.
ХОРОШО.
>> Так что я, вот, моя Реализация для жадный.
И в то время как многие из вас, ребята писали жадные в то время как петли form--, что
это вполне приемлемо способ сделать it-- другой способ сделать это, чтобы просто
разделить на модулю.
Потому что тогда вы можете иметь свой значение, а затем иметь свой остаток.
И тогда вы можете просто добавить все это вместе.
Ли логика, что я делаю здесь смысл для всех,
прежде чем мы начнем?
Вид?
Круто.
Отлично.
Это довольно сексуальная часть кода, я бы сказал.
Как я уже сказал, Давид, в лекции, через некоторое время,
вы все начинаете видеть код как что-то, что красиво.
И иногда, когда вы видите красивый Код, это такой замечательный ощущение.
>> Так, однако, в то время как этот код очень красиво, это не работает должным образом.
Так что давайте работать check50 на этом.
Проверьте 50 20-- уп.
2?
Это pset2?
Да.
О, pset1.
ХОРОШО.
Таким образом, мы работать check50.
>> И, как вы, ребята, можете посмотреть здесь, это неспособность пару случаев.
И для некоторых из вас, в Конечно делать свои проблемные наборы,
вы, как, ах, почему оно не работает.
Почему это работает для некоторых значения, но не для других?
Ну, GDB будет помочь вам понять почему эти входы не работали.
>> ХОРОШО.
Итак, давайте посмотрим, одно из проверяет меня неудачу в check50
был входное значение 0,41.
Таким образом, правильный ответ, что вы должны получать это 4.
Но вместо того, что я распечатки это 3-н, что неверно.
Так что давайте просто запустить вручную, просто убедитесь, что check50 работает.
Давайте сделаем ./greedy.
Ой, я должен сделать жадный.
Там мы идем.
Теперь ./greedy.
>> Сколько причитается?
Давайте сделаем 0.41.
И да, мы видим здесь что это вывод 3
когда правильный ответ, В самом деле, должно быть 4.
Так что давайте ввести GDB и посмотреть, как мы может идти о фиксации этой проблемы.
>> Итак, первый шаг в всегда отладки кода
это установить точку останова, или точка, в которой вы
хочу компьютера или отладчик, чтобы начать смотреть.
Так что, если вы действительно не знаю, что ваша проблема,
Обычно, типичный, что мы хотим, чтобы сделать, это установить точку останова на наш основной.
Так что, если вы, ребята, можете видеть это красная кнопка рядом,
Да, это было мне установив останова для главной функции.
Я нажмите что.
>> И тогда я могу пойти к моей кнопки Debug.
Я ударил эту кнопку.
Позвольте мне отдалиться, если я могу.
Там мы идем.
Таким образом, мы имеем здесь, панель справа.
Я извиняюсь, ребята в спину, вы не могу видеть очень хорошо.
Но по сути, все это право панель делает
является отслеживание и выделенный линия, которая является строка кода
что компьютер в данный момент, а также все ваши переменные
здесь.
>> Итак, вы получили центов, монеты, п, объявлены на разные вещи
в этот момент.
Не беспокойтесь, потому что у нас нет на самом деле не инициализации их к любым переменным еще.
Таким образом, в вашем компьютере, ваш Компьютер просто видя,
ой, 32767 был последний используемая функция этого пространства памяти в моем компьютере.
И так вот где центов в настоящее время.
Но ни что когда-то вы не запустите код, она должна стать инициализации.
>> Так давайте пройдем, линию линия, то, что здесь происходит.
ХОРОШО.
Так здесь являются три кнопки, которые я только что объяснил.
Вы должны играть, или функцию Run, Кнопка, у вас есть Шаг за кнопку,
и у вас также есть Шаг в кнопки.
И, по существу, все три им просто пройти через код
и делать разные вещи.
>> Так обычно, когда вы отладки, мы не хотим, чтобы просто нажать Play,
потому Игра будет просто запустить код к концу этого.
И тогда у вас не будет на самом деле знаю, что ваша проблема
есть, если вы не установите несколько точек останова.
Если вы установите несколько точек останова, это будет просто автоматически
бежать от одной точки останова, к другому, чтобы в следующий.
Но в этом случае мы в только, что один, потому что мы
хочу работать наш путь сверху вниз вниз.
Итак, мы собираемся, чтобы игнорировать эту кнопку сейчас для целей этой программы.
>> Так Шаг над функцией только переступает каждой строки
и говорит вам, что компьютер делает.
Шаг в функции идет в реальной функции
это на строке кода.
Так, например, как Е (), , которая является функцией, верно?
Если бы я хотел, чтобы физически шаг в функции Е (),
Я бы на самом деле идти в части Код, где Е () была написана и посмотреть,
что там происходит.
>> Но, как правило, мы предполагаем, что код, который мы даем вам работы.
Мы предполагаем, что Е () работает.
Мы предполагаем, что GetInt () работает.
Таким образом, нет никакой необходимости шаг в этих функций.
Но если есть функции что вы пишете сами
что вы хотите, чтобы проверить , что происходит,
Вы хотели бы шаг в этой функции.
>> Так что сейчас мы только собираемся перешагнуть этот кусок кода.
Итак, давайте посмотрим.
О, печать, "О Хай, как много изменений причитается? "
Мы не волнует.
Мы знаем, что работает, таким образом, мы шаг за нее.
>> Так п, которая является нашим поплавок, что мы в initialized-- или declared--
наверху, мы теперь равная, что GetFloat ().
Итак, давайте перешагнуть что.
И мы видим, на Нижняя здесь, программа
побуждает меня к входу значение.
Итак, давайте Введите значение мы хотим проверить здесь, что 0,41.
Отлично.
>> Так что теперь N-- вы, ребята, видите здесь, на bottom-- это
stored--, потому что мы еще не округляется, это
хранятся в этом, как гигант поплавок, который 0,4099999996,
который находится достаточно близко к нашему Цели, прямо сейчас, до 0,41.
И тогда мы увидим в дальнейшем, как мы продолжать продвижение по программе,
После здесь, н стало округлые и центов стала 41.
Отлично.
Итак, мы знаем, что работа нашей округления в.
Мы знаем, что у нас есть правильное число центов,
так что мы знаем, что это на самом деле не проблема.
>> Таким образом, мы по-прежнему шагать в этой программе.
Мы идем сюда.
И так после этой строки кода, мы должны знать, сколько четверти у нас есть.
Мы перешагнуть.
И вы видите, мы, на самом деле, есть один четверть, потому что мы вычитали 25
из нашего начального значения 41.
И у нас есть 16 остается нашим центов.
>> Понимает ли все, как программа пошагового
и почему центов стала 16 и почему, в настоящее время, монеты стал 1?
Все следующее, что логика?
Круто.
Так, как в данный момент, Рабочая программа, верно?
Мы знаем, что это именно делать то, что мы хотим.
И мы на самом деле не должны распечатать, ах, какой
является центов на данный момент, что монеты в этой точке.
>> Мы продолжаем идти по программе.
Переступить.
Круто.
Мы идем по десять центов.
Отлично.
Мы видим, что это заняло от $ 0.10 за копейки.
И теперь у нас есть две монеты.
Правильно.
>> Перейдем гроши, и мы видим что мы получили, оставшиеся центов.
Хм, это странно.
До здесь программы, я должен был чтобы вычли мои гроши.
Может быть, я просто не был делает эту строку право.
И, увы, вы можете увидеть здесь, потому что мы знаем,
что мы вступаем через линии 32 и 33,
вот где наша программа неправильно было переменные работать.
Таким образом, мы можем посмотреть и увидеть, о, Я вычитания центов здесь,
но я на самом деле не добавляя к моей стоимости монеты.
Я добавляю к центов.
И я не хочу, чтобы добавить к центов, я хочу, чтобы добавить к монетам.
Так что, если мы меняем что монеты, мы получили рабочую программу.
Я могу запустить check50.
Вы можете просто выйти из GDB права здесь и затем запустить check50 снова.
Я мог бы просто сделать это.
Я должен сделать жадный.
0,41.
И вот, это печать из правильного ответа.
>> Итак, как вы, ребята, можете видеть, GDB это действительно мощный инструмент
когда у нас так много кода происходит, и так много переменных
что это трудно для нас, как человеку, чтобы отслеживать.
Компьютер, в GDB отладчик, имеет возможность
чтобы отслеживать все.
Я знаю, в Visionaire, вы, ребята, вероятно, возможно, попали некоторые ошибки сегментации
потому что вы бежали вне границ вашего массива.
В примере Цезаря, это именно то, что я здесь реализована.
>> Так что я забыл, чтобы проверить что бы произошло, если бы я
не имеют два аргумента командной строки.
Я просто не ставили в этом чеке.
И поэтому, если я бегу Debug-- я поставил мой останова направо там.
Я бегу Debug.
>> ХОРОШО.
Да.
Так на самом деле, GDB должен был , что сказал мне, что
был сбой сегментации там.
Я не знаю, что происходит тут, но, когда я побежал,
она работает.
При запуске строк кода через и GDB может просто внезапно бросить на вас,
идти и смотреть то, что красный ошибка.
Это вам скажу, эй, ты была ошибку сегментации,
Это означает, что вы пытались получить доступ пространство в массиве, что не существует.
Да.
>> Таким образом, в следующей проблеме установленные на этой неделе, вы, ребята,
вероятно, будет много переменные с плавающей вокруг.
Вы не собираетесь быть уверены, что Все они имеют в виду в определенный момент.
Так GDB действительно поможет вам в выясняя то, что они все сравнявшись
и быть в состоянии видеть, что визуально.
Кто путать от того, как либо из этого работал?
Круто.
Все в порядке.
Таким образом, после того, что мы собирается погрузиться
в четыре различных типы сортов на этой неделе.
Как многие из вас, прежде всего, прежде чем мы начнем,
прочитал всю спецификацию для pset3?
ХОРОШО.
Я горжусь вами, ребята.
Вот как половина класса, который значительно больше, чем в прошлый раз.
>> Так что здорово, потому что, когда мы говорим о содержании
в lecture-- или извините, в section-- Мне нравится
связать много, что назад к тому, что это PSET
и как вы хотите, чтобы осуществить, что в вашем PSET.
Так что, если вы приходите, имеющих читать спецификации, он будет
будет намного проще для вас, чтобы понять, то, что я говорю о том, когда я говорю,
эй, это может быть действительно хорошее место для реализации такого рода.
Так что те, из вас, кто читал особое_разрешение знаю, что, как часть вашего PSET,
Вы будете иметь, чтобы написать тип рода.
Так что это может быть очень полезно для многих из вас сегодня.
>> Таким образом, мы начнем с того, по сути, самый простой тип
из рода, выбор рода.
Типичный алгоритм как мы идти об этом
is-- Давид через них все в лекция, так что я буду быстро двигаться вдоль
here-- существу, вы есть массив значений.
И тогда вы найдете маленький несортированный значение
и вы поменять это значение с первый несортированный значение.
А потом вы просто повторять с остальной части списка.
>> И вот наглядное объяснение о том, как это будет работать.
Так, например, если мы должны были начать с массивом из пяти элементов, индекс
От 0 до 4, с 3, 5, 2, 6, и 4 значения помещен в array-- это прямо сейчас,
мы просто будем считать, что они все без сортировки
потому что мы не испытали в противном случае.
>> Так как выбор рода будет работа, что бы прежде
проходят через полностью в несортированных массива.
Было бы выбрать наименьшее значение.
В этом случае, 3, правый Теперь, является наименьшим.
Он получает до 5.
Нет, 5 не больше than-- или извините, не менее 3 than--.
Таким образом, минимальное значение по-прежнему 3.
И тогда вы получите 2.
Компьютер видит, ой, 2 меньше, чем 3.
Теперь 2 должно быть минимальное значение.
И так 2 свопы с этой первой величины.
>> Таким образом, после одного прохода, мы действительно видим что 2 и 3 меняются местами.
И мы только собираемся продолжать делать Это снова с остальной частью массива.
Итак, мы собираемся, чтобы просто запустить через Последние четыре индексы массива.
Мы увидим, что 3 следующий минимальное значение.
Итак, мы собираемся, чтобы поменять что с 4.
И тогда мы просто будем продолжать не проходит через до, в конце концов, вы
попасть в отсортированном массиве, в котором 2, 3, 4, 5, 6 и все сортируются.
Все понимают ли логику о том, как работает выбор рода?
>> Вы просто есть какой-то минимального значения.
Вы отслеживать, что это такое.
И всякий раз, когда вы найдете его, вы поменять его с первым значением в array--
или, не первый value-- следующее значение в массиве.
Круто.
>> Итак, как вы, ребята, вроде видел из мельком,
мы собираемся псевдокод это.
Так что, если вы, ребята, в задней хотите образуют группу, каждый в таблице
могут образовывать мало партнера, я собираюсь чтобы дать вам, ребята, как три минуты
просто говорить через логика, на английском языке,
о том, как мы могли бы реализовать псевдокод написать выбора рода.
И есть конфеты.
Пожалуйста, приходите и получите конфету.
Если вы находитесь в спине и вы хотите конфеты, я могу бросить конфеты на вас.
На самом деле, сделать you-- прохладно.
Ой, извини.
ХОРОШО.
>> Так что, если мы хотели бы, а класс, записи псевдокод
о том, как можно было бы подойти эта проблема, просто не стесняйтесь.
Я просто ходить, а в порядке, спросите группы
на следующей строке что мы должны делать.
Так что, если вы, ребята, хотите, чтобы начать выключен, то, что первое, что
делать, когда вы пытаетесь осуществить способ решить эту программу
выборочно отсортировать список?
Давайте предположим, что мы только что есть массив, ладно?
>> АУДИТОРИЯ: Вы хотите, чтобы создать некоторые рода [неразборчиво], что вы
проходит через весь массиве.
>> ANDI Пэн: Право.
Таким образом, вы будете хотеть, чтобы итерации через каждый пространства, правильно?
Так здорово.
Если вы, ребята, хотите, чтобы дать мне Следующий line-- да, в спину.
>> АУДИТОРИЯ: Проверьте их все для самых маленьких.
>> ANDI Пэн: Там мы идем.
Поэтому мы хотим, чтобы пройти и проверить видеть, что минимальное значение, верно?
Я собираюсь сокращать, что "мин."
Что вы, ребята, хотите делать после Вы нашли минимальное значение?
>> АУДИТОРИЯ: [неразборчиво]
ANDI Пэн: Так что вы собираетесь хотят переключить его с первого этом массиве,
правильно?
Это начало, я собираюсь сказать.
Все в порядке.
Так что теперь вы поменялись первым Один из них, что вы хотите сделать после этого?
Так что теперь мы знаем, что это одно здесь должны быть наименьшее значение, не так ли?
Тогда у вас есть дополнительный отдых массива, что это несортированный.
Так что вы хотите сделать здесь, если вы ребята, хотите, чтобы дать мне следующую строку?
АУДИТОРИЯ: Итак вы хотите перебрать через оставшуюся часть массива.
ANDI Пэн: Да.
И так, что же переборе вид подразумевает мы, наверное, нужно?
Какой тип--
>> АУДИТОРИЯ: О, дополнительная переменная?
ANDI Пэн: Возможно другой цикл, не так ли?
Таким образом, мы, вероятно, захотят для перебора through-- здорово.
И тогда вы будете идти назад и вероятно, проверить минимум раз
правильно?
И вы собираетесь повторять это, потому что петли только собирается
держать работает, верно?
>> Итак, как вы, ребята, можете видеть, мы просто общий псевдокод
о том, как мы хотим, чтобы эта программа смотреть.
Это итерация здесь, то, что мы как правило, нужно написать в коде
если мы хотим, чтобы итерации через Массив, какой тип структуры?
Я думаю, Кристабель уже говорил это раньше.
>> Зала: для петли.
>> ANDI Пэн: для цикла?
В точку.
Так это, наверное, будет цикл.
Что такое проверка здесь собирается значит?
Как правило, если вы хотите, чтобы проверить если что-то что-то else--
>> АУДИТОРИЯ: Если.
>> ANDI PENG: если, верно?
А потом своп здесь, мы будем перейти позже, потому что Давида
прошел через это в лекции, а также.
А потом второй итерации implies--
>> АУДИТОРИЯ: Еще цикл.
>> ANDI Пэн: --another цикл, точно.
Так что, если мы ищем на это правильно, мы
можно увидеть, что мы, вероятно, понадобится вложенный цикл
с условным заявлением в там а затем фактическое кусок кода, который это
собирается поменять значения.
Так что я просто вообще написано псевдокод код здесь.
И тогда мы на самом деле происходит физически, как класс,
попытаться осуществить это сегодня.
Давайте вернемся в этот IDE.
>> Ой-ой.
Почему это не-- там.
ХОРОШО.
Извините, позвольте мне попытаться увеличить немного больше.
Там мы идем.
Все, что я делаю здесь, я создал Программа называется "выбор / sort.c."
Я создал массив из девяти Значения, 4, 8, 2, 1, 6, 9, 7, 5, 3.
В настоящее время, как вы можете Понимаете, они не упорядочены.
н будет число, говорит вам сумму значений
у вас есть в вашем массиве.
В этом случае, у нас есть девять значений.
И я только что получил цикл здесь что выводит несортированный массив.
>> И в конце концов, я также получил для цикл, который печатает его снова.
Так, теоретически, если эта программа работает правильно, в конце концов,
Вы должны увидеть печатный цикл в котором 1, 2, 3, 4, 5, 6, 7, 8,
9 все правильно в порядке.
>> Таким образом, мы получили наш псевдокод здесь.
Кто-нибудь хочет, целью которых я просто пойду просить volunteers--
скажите мне точно, что если ввести мы хотим, чтобы, во-первых, просто итерации
по начало этого массива?
Что строка кода я вероятно, здесь нужно?
>> АУДИТОРИЯ: [неразборчиво]
>> ANDI Пэн: Да, чувствую, бесплатно, целью которых извините, вам
не должны стоять up-- чувство свободно поднять свой голос немного.
>> АУДИТОРИЯ: Для INT я равна 0--
>> ANDI Пэн: Да, хорошо.
>> АУДИТОРИЯ: я меньше длины массива.
>> ANDI Пэн: Так что имейте в против здесь, потому что мы
не есть функция, которая говорит нам длина массива,
у нас уже есть Значение, которое хранит, что.
Правильно?
Еще одна вещь, чтобы держать в mind-- в массиве
из девяти значений, какие индексы?
Давайте просто скажем, этот массив 0 до 3.
Вы видите, что последний Индекс самом деле 3.
Это не 4, хотя есть четыре значения в массиве.
>> Так здесь, мы должны быть очень осторожны, того, что наше условие для длины
будет.
>> АУДИТОРИЯ: не было бы н минус 1?
ANDI Пэн: Это происходит п минус 1, точно.
Имеет ли это смысл, почему это п минус 1, все?
Это потому, что массивы равны нулю, индексированные.
Они начинаются с 0 и запустить до н минус 1.
Да, это немного сложнее.
ХОРОШО.
А потом--
АУДИТОРИЯ: Isnt'1, что уже позаботились, хотя,
, просто не говорю "меньше или равно "и просто говорю" менее "?
>> ANDI Пэн: Это очень хороший вопрос.
Так да.
Но также, таким образом, что мы реализации проверки право,
вам нужно сравнить два значения.
Таким образом, вы на самом деле хотите, чтобы оставить "на" пустой.
Потому что, если вы сравните это одно, вы не собираетесь
есть что-нибудь после него сравнить, правда?
Да.
Так я ++.
Давайте добавим наши скобки в.
Упс.
Отлично.
Таким образом, мы имеем начало нашей внешней петли.
Так что теперь мы, вероятно, хотите, чтобы создать переменную для хранения
трек наименьшим значением, верно?
Кто-нибудь хочет, чтобы дать мне строка кода, которая будет это делать?
Что нам нужно, если мы собираемся хотят, чтобы сохранить что-нибудь?
>> Правильно.
Может быть, лучше, что название будет be-- "Темп" полностью works--
может быть, более метко назвал бы, если мы хотим, чтобы маленький value--
>> АУДИТОРИЯ: Мин.
ANDI Пэн: мин, там мы идем.
мин будет хорошо.
И вот что нам делать хочу, чтобы инициализировать его?
Это немного сложнее.
Потому что сейчас на начало этого массива,
Вы еще не смотрели ни на что, не так ли?
Так что, автоматически, если мы только на я равна 0,
то, что мы хотим, чтобы инициализировать наш первый минимальное значение для?
АУДИТОРИЯ: я.
ANDI Пэн: я, точно.
Christabel, почему мы хотим инициализировать его я?
>> АУДИТОРИЯ: Потому что, ну, мы, начиная с 0.
Так, потому что мы не имеем ничего, чтобы сравнить это, минимум будет в конечном итоге 0.
>> ANDI Пэн: Точно.
Таким образом, она совершенно точно.
Потому что у нас на самом деле не посмотрел на что-нибудь еще,
мы не знаем, что наша минимальное значение.
Мы хотим, чтобы просто инициализировать его я, что, в настоящее время, прямо здесь.
И, как мы по-прежнему двигаться вниз этот массив,
мы увидим, что, друг с Дополнительный проход, я увеличивает.
И так в этой точке, я, вероятно, будет
хотят быть минимальным, потому что это будет что угодно
начало неотсортированной массива.
Круто.
>> Так что теперь мы хотим, чтобы добавить для цикла здесь это
собирается повторять через несортированный или остальная часть этого массива.
Кто-нибудь хочет, чтобы дать мне строка кода, которая будет это делать?
Hint-- что нам нужно здесь?
Что собирается идти в этом для цикла?
Да.
АУДИТОРИЯ: Таким образом, мы хотели бы иметь различный число,
потому что мы бежим до конца массива вместо I, так что, возможно
J.
>> ANDI Пэн: Да, J звучит хорошо для меня.
Равно?
>> АУДИТОРИЯ: Так бы я плюс 1, потому что Вы начинаете на следующей значения.
А потом к end-- так снова, J является меньше, чем п минус 1, а затем J ++.
ANDI Пэн: Отлично.
>> А потом здесь, мы собираемся хотите чтобы проверить, если наше условие выполняется,
правильно?
Потому что вы хотите, чтобы изменить минимальное значение
если это на самом деле меньше, чем вы сравниваете его, верно?
Так что мы собираемся хотите здесь?
Проверьте, чтобы видеть.
Какой вид заявления мы, вероятно, будет
ти хотите использовать, если мы хочу кое-что проверить?
>> АУДИТОРИЯ: если заявление.
>> ANDI PENG: если заявление.
Так if-- и то, что будет условие, что мы хотим в
нашей, если заявление?
>> АУДИТОРИЯ: Если значение J меньше, чем значение i--
>> ANDI Пэн: Точно.
Так if-- так что это массив называется "массив".
Отлично.
Так что, если array-- что это было?
Повтори.
>> АУДИТОРИЯ: Если массив-J меньше Массив-я, то мы бы изменить мин.
Таким образом, мин будет к.
>> ANDI Пэн: Имеет ли это смысл?
ХОРОШО.
А теперь сюда, мы на самом деле хотим реализовать обмен, верно?
Так Напомним, что в лекции, что Давид, когда он пытался обменять the--, что было
it-- апельсиновый сок и milk--
>> АУДИТОРИЯ: Это было отвратительно.
>> ANDI Пэн: Да, это было своего рода брутто.
Но это было довольно хорошо Концепция демонстрации время.
Так что думайте о ваших ценностей здесь.
Вы получили массив из мин, массив I,
или то, что мы пытались поменять здесь.
И вы, вероятно, не может залить их в друг с другом, в то же время, так?
Так что мы собираемся чтобы нужно создать здесь
для того, чтобы правильно поменять значения?
>> АУДИТОРИЯ: временная переменная.
>> ANDI Пэн: временная переменная.
Так давайте сделаем Int темп.
Смотри, это было бы лучше Время, целью которых эй, что это было?
ХОРОШО.
Так что это было бы лучше время назвать переменную "Темп".
Так давайте сделаем Int темп.
Что мы собираемся SET TEMP равную здесь?
АУДИТОРИЯ: Мин?
ANDI Пэн: Это немного сложнее.
Это на самом деле не имеет значения, в конце концов.
Это не имеет значения, что заказ вы решите поменять в
так долго, как вы делаете, что вы отслеживать то, что вы подкачки.
>> АУДИТОРИЯ: Это может быть массив я.
>> ANDI Пэн: Да, давайте сделаем массив-I.
И тогда то, что следующая строка кода мы хотим иметь здесь?
АУДИТОРИЯ: массив я равна массива-J.
ANDI Пэн: И, наконец?
АУДИТОРИЯ: массив J равна массива я.
АУДИТОРИЯ: Или массива J равно Массив-temp-- или температуры.
>> ANDI Пэн: ОК.
Так что давайте работать и посмотрим, если он будет работать.
Где, что происходит?
О, что это проблема.
Смотри, на линии 40, мы пытается использовать массив-J?
Но где J существует только в?
>> АУДИТОРИЯ: В течение цикла.
ANDI Пэн: Право.
Так что мы собираемся нужно сделать?
>> АУДИТОРИЯ: Определить его пределами the--
АУДИТОРИЯ: Да, я думаю, вы должны использовать другой, если заявление, не так ли?
Так как, если minimum-- Все в порядке, дайте мне подумать.
>> ANDI Пэн: Ребята, попробуйте взглянуть Давайте
см, что это то, что мы можем сделать здесь?
>> АУДИТОРИЯ: ОК.
Таким образом, если минимальная не равна j-- так что если минимальная еще i--
то мы бы не поменять.
>> ANDI Пэн: Значит ли это, равно я?
Что вы хотите сказать здесь?
>> АУДИТОРИЯ: Или да, если минимум не равное I, да.
ANDI Пэн: ОК.
Ну, что решает, вроде, наши проблемы.
Но это еще не решить Проблема что произойдет, если j-- так J
не существует вне его, то, что Вы хотите, чтобы мы с ним делать?
Объявить его пределами?
Давайте попробуем это работает.
Ой-ой.
Наша рода не работает.
>> Как вы можете видеть, нашу начальную Массив были те значения.
И после этого он должен иметь был в 1, 2, 3, 4, 5, 6, 7, 8, 9.
Это не работает.
Ах.
Что мы делаем?
АУДИТОРИЯ: Отладка.
ANDI Пэн: Ладно, мы можем попробовать.
Мы можем отладить.
Осмотрите немного.
Давайте установим нашу точку останова.
Давайте like-- OK.
>> Так, потому что мы уже знаем, что эти линии, 15 через 22,
которые working--, потому что все, что я делаю просто перебирая и printing--
Я могу идти вперед и пропустить это.
Давайте начнем с линии 25.
ООП позвольте мне избавиться от этого.
>> АУДИТОРИЯ: Так точки останова где начинается отладка?
ANDI Пэн: Или остановок.
АУДИТОРИЯ: Или остановок.
ANDI Пэн: Да.
Вы можете установить точки останова и несколько он может просто прыгать от одного к другому.
Но в этом случае мы не знаем, где ошибка происходит.
Таким образом, мы просто хотим начать сверху вниз.
Ага.
ХОРОШО.
>> Так эта линия здесь, мы можем вмешаться.
Вы можете увидеть здесь, мы получили массив.
Те значения что в массиве.
Вы видите, что, как индекс 0, соответствует value-- о,
Я собираюсь попробовать, чтобы увеличить.
К сожалению, это действительно трудно чтобы see-- по индексу массива 0,
мы имеем значение 4 и Затем так далее, и так далее.
У нас есть локальные переменные.
Сейчас я равна 0, что мы хотим, чтобы это было.
>> И так давайте держать пошаговое.
Наш минимальный равен 0, которые мы также хотим, чтобы это было.
И тогда мы входим наш второй для цикл, если массив J меньше, чем массив-I,
который его не было.
Так же вы видите, как что пропустил что?
>> АУДИТОРИЯ: так должно, если Минимальный все that-- не следует, что
быть внутри первым цикл?
ANDI Пэн: Нет, потому что Вы все еще хотите, чтобы проверить.
Вы хотите, чтобы сделать сравнение каждый Время, даже после запуска через него.
Вы не просто хотите, чтобы сделать это на первом проход.
Вы хотите, чтобы сделать это с каждый проход снова.
Итак, вы хотите, чтобы проверить Ваше состояние внутри.
Таким образом, мы только собираемся держать работает через здесь.
Я дам вам подсказку парням.
Это связано с тем, что при Вы проверяете ваш условный,
Вы не проверяя для правильного индекса.
Так что сейчас вы проверка Индекс массива J меньше, чем массив
Индекс I.
Но то, что ты делаешь на начало для цикла?
Вы не установив J, равный I?
>> Да, так что мы на самом деле можем выйти из отладчика здесь.
Итак, давайте взглянем на нашем псевдокоде.
For-- мы собираемся начать в я равна 0.
Мы собираемся идти до н минус 1.
Давайте проверим, мы имели это право?
Да, это было в порядке.
>> Итак внутри здесь, мы создадим минимальное значение
и установить, что в I равны.
Разве мы это делаем?
Да, это сделал.
В настоящее время в нашей внутренней петли для, мы собирается делать J равна я в п минус 1.
Разве мы это делаем?
В самом деле, мы сделали это.
>> Так, однако, что мы здесь сравнения?
>> АУДИТОРИЯ: J + 1.
ANDI Пэн: Точно.
И тогда вы будете хотеть, чтобы установить минимальная равна J плюс 1, а.
Так что я прошел через это очень быстро.
Как вы, ребята понимают почему это J + 1?
ХОРОШО.
>> Таким образом, в вашем массиве, в Ваш первый проход через,
Ваш цикл, для Int я равна 0, давайте просто
предположить, что это не была изменена еще.
У нас есть массив, полностью, всего четыре несортированные элементы, верно?
Поэтому мы хотим, чтобы инициализировать я равняться 0.
И я намерен просто проходят через эту петлю.
И поэтому в первом проходе, мы собираемся инициализировать переменную "мин"
что также равно I, потому что мы не иметь минимальное значение.
Так вот в настоящее время равен 0, а также.
И тогда мы будем идти до конца.
И мы хотим, чтобы итерации снова.
Теперь, когда мы нашли, что наш минимальный есть, мы хотим, чтобы перебора
снова, чтобы увидеть, если это сравнение, не так ли?
Так J, вот, идет на равное I, который является 0.
И потом, если массив J плюс я, что это тот, который дальше снова, как менее
чем то, что ваш текущий минимум значение, вы хотите поменять местами.
>> Так что давайте просто сказать, что мы получил, как, 2, 5, 1, 8.
Прямо сейчас, я равна 0 и J равен 0.
И это наша минимальное значение.
Если массив-J плюс i-- так что если один это после того, что мы, глядя на
больше, чем один перед этим, это станет минимум.
>> Так вот, мы видим, что 5 не меньше, чем.
Так это будет, чтобы не быть 5.
Мы видим, что 1 меньше, чем 2, не так ли?
Итак, теперь мы знаем, что наша минимум будет значение индекса на 0, 1, 2.
Да?
А потом, когда вы получаете здесь, Вы можете поменять правильные значения.
>> Так что, когда вы, ребята, просто имея J раньше, вы не глядя на то
после этого.
Вы искали на то же самое значение, что
Поэтому он просто ничего не делал.
Имеет ли это смысл для всех, Поэтому нам нужно что плюс 1 там?
ХОРОШО.
Теперь давайте просто запустить через него, чтобы сделать что остальная часть кода является правильным.
Почему, что случилось?
Ах, это мин прямо здесь.
Мы сравнивали неверное значение.
О нет.
>> Ах да, здесь мы были обмен неправильные значения, а также.
Потому что мы искали в I и J.
Те, кого мы проверяли.
Мы на самом деле хотим, чтобы поменять местами Минимальный ток минимум,
с тем, что один снаружи.
И, как вы, ребята, можете увидеть вниз здесь, у нас есть отсортированный массив.
Это просто было сделать с тот факт, что, когда
мы проверяли Значения, которые мы сравнивали,
мы не смотрели на правильные значения.
Мы искали в том же самом здесь, на самом деле не его замены.
Вы должны смотреть на один следующий к нему, а затем вы можете поменять.
Так вот то, что было своего рода прослушивание наш код, прежде чем.
И то, что я сделал здесь есть все, отладчик мог бы сделать для вас
Я просто сделал это на доска, потому что это легче
чтобы увидеть, а не пытаться для увеличения масштаба отладчика.
Имеет ли это смысл для всех?
Круто.
>> Все в порядке.
Мы можем двигаться дальше к разговору о асимптотическая обозначения, которые
это просто фантазии способ сказать выполнения всех этих видов.
Так что я знаю Дэвида, в лекции, коснулся автономной работы.
И он пошел через весь формуле о том, как рассчитать время автономной работы.
Не беспокойтесь об этом.
Если вы действительно любопытно о том, как это работает,
не стесняйтесь говорить со мной после раздела.
Мы можем пройти через формулы вместе.
Но все вы, ребята, должны действительно знаю, что п в квадрате более 2
это то же самое, как н в квадрате.
Потому что наибольший номер, показатель растет больше всего.
И так для наших целей, Все мы заботимся о
является то, что гигантский номер, который растет.
>> Так что в лучшем случае выполнения отборочного рода?
Если вы собираетесь иметь для перебора списка
а затем перебора остальные этого списка,
сколько раз Вы собираетесь вероятно,
в худшем case-- в лучшем случае, sorry-- запустить через?
Может быть, лучше спросить чтобы спросить, что это худший случай
выполнения отборочного рода.
АУДИТОРИЯ: п в квадрате.
ANDI Пэн: Это н квадрат, правильно.
Так простой способ думать об этом, как, в любое время у вас есть два вложенных циклов для,
это будет н в квадрате.
Потому что не только ты проходящей через раз,
у вас есть, чтобы вернуться и бежать через него
снова внутри для каждого значения.
Таким образом, в этом случае, вы работаете п раз н квадрат, который is-- извините,
п раз п, равен п в квадрате.
>> И вроде тоже немного уникальным в том смысле
что это не имеет значения, если эти Значения уже в порядке.
Он по-прежнему собирается запустить через любом случае.
Давайте просто сказать, что это был 1, 2, 3, 4.
Независимо от того, является ли он в порядок, это все равно бы пробежал
и до сих пор проверяется минимальное значение.
Это сделало бы такое же количество проверок
каждый раз, даже если он на самом деле не трогать.
>> Таким образом, в таком случае, лучшим и худшим Время автономной работы фактически эквивалентны.
Таким образом, ожидаемый выполнения селекционного сорта,
которые мы обозначаем символом тета, тета, в данном случае,
Также будет н квадрат.
Все эти три будет н квадрат.
Это все понятно, почему среда выполнения п квадрате?
>> Все в порядке.
Так что я просто хочу, чтобы быстро бежать через остальную часть сортов.
Алгоритм пузырь sort-- помните,
это было первым Дэвид подошел в лекции.
По сути, вы шаг через весь список
и вы swap-- вас всего Сравнение двух одновременно.
И если это больше, чем вы просто поменять их местами.
Так что, если это больше, вы бы поменять.
Я получил официальное право здесь.
>> Так что давайте просто сказать, что вы были 8, 6, 4, 2.
Вы бы сравнить 8 и 6.
Вы должны были бы поменять их местами.
Вы бы сравнить 8 и 4.
Вы должны были бы поменять их местами.
Если у вас есть, чтобы поменять 8 и 2, изменить их.
Таким образом, в таком смысле, вы можете видеть, сыграна в течение длительного периода времени,
как значения рода пузырь концы, который является, почему мы называем его
пузырьковая сортировка.
>> Мы просто запустить через раз на наш второй проход, и наш третий проход,
и наш четвертый проход.
По сути, пузырьковая сортировка работает только до тех пор, пока не делают никаких больше свопы.
Так что в этом смысле, это просто общая псевдокод для него.
Не беспокойтесь, это не все будет на сайте.
Мы не должны на самом деле пойти по этому поводу.
>> Мы просто инициализировать счетчик переменная, которая начинается с 0.
И мы перебора всего массива.
И если одно значение, если это is-- значение больше, чем данное значение,
Вы собираетесь поменять их местами.
И тогда ты просто продолжать идти.
И вы собираетесь рассчитывать.
И вы только собираетесь продолжать делать это в то время счетчик больше
чем 0, что означает, что каждый раз, когда у вас есть, чтобы поменять,
Вы знаете, вы хотите пойти назад и еще раз проверить.
Вы хотите, чтобы держать проверку, пока вы не знаете, что вы не должны поменять больше.
>> Так что самый лучший и худший Дело среда выполнения для пузырьковой сортировки?
И hint-- это на самом деле отличается от выбора вида в смысле
что эти два ответы не совпадают.
Подумайте о том, что будет происходить в случай, если он был уже отсортирован.
И думать о том, что произойдет, если он был
в случае, в котором он не был отсортирован.
И вы можете запустить вид через что, почему происходит.
Я дам вам, ребята, как, 30 секунд, чтобы думать об этом.
>> ХОРОШО.
Кто-нибудь есть предположение, что в в худшем случае время выполнения пузырьковой сортировки является?
Да.
>> АУДИТОРИЯ: было бы, как, п раз п минус 1 или что-то подобное?
Мол, каждый раз, когда он работает, это просто, как один своп менее
что бы это ни было.
>> ANDI Пэн: Да, так Вы совершенно правы.
И это тот случай, когда ваш Ответ на самом деле более сложная
чем мы должны дать.
Так это будет run-- Я собираюсь стереть все это здесь.
Все ли хорошо?
Могу ли я стереть это?
ХОРОШО.
Вы собираетесь работать через п раз в первый раз, не так ли?
И они собираются запустить через п минус 1 во второй раз, верно?
И тогда вы будете держать происходит, п мой 2, и так далее.
Дэвид сделал это в лекции, где, если вы добавили все эти ценности,
Вы получаете то, что это like-- yeah-- более 2, что существенно снижает просто
до п квадрате.
Вы собираетесь получить странно доля там.
И так просто знаю, что п квадрате всегда
имеет приоритет над фракцией.
И поэтому в этом случае худшего выполнения будет н в квадрате.
Если бы это было в порядке убывания порядок, думаю, вам,
должны сделать своп каждый раз.
>> Что бы, потенциально, в лучшем случае выполнения?
Давайте просто сказать, что если список уже был в порядке, что бы во время выполнения будет?
>> АУДИТОРИЯ: п.
ANDI Пэн: Это н, точно.
И почему это п?
АУДИТОРИЯ: потому что вы просто должны проверить на каждом раз.
ANDI Пэн: Точно.
Таким образом, в лучшем выполнения, если этот список был уже
sorted-- скажем 1, 2, 3, 4-- вы просто пройти, вы бы проверить,
вы увидите, ох, все они оправдались.
У меня не было, чтобы поменять.
Я задолбался.
Таким образом, в этом случае, это просто п или количество шагов, которые вы просто
должен был проверить в первом списке.
>> И после этого, мы теперь попал сортировка вставками, где
алгоритм, по существу, разделить это в отсортированном и несортированных части.
А потом один за другим, неотсортированной значения
вставляется в соответствующих позиции в начале списка.
>> Так, например, у нас есть Список 3, 5, 2, 6, 4 снова.
Мы знаем, что это в настоящее время несортированный, потому что мы только что
начал смотреть на него.
Мы смотрим и мы знаем, что первое значение сортируется, верно?
Если вы только глядя на массив Размер одного, вы знаете, что это сортируется.
>> Итак, мы знаем, что Остальные четыре несортированный.
Мы идем через, и мы видим, что значение.
Давай вернемся.
Смотрите, что значение 5?
Мы смотрим на него.
Мы сравниваем его до 3.
Мы знаем, что это больше, чем 3, так что мы знаем, что это сортируется.
Таким образом, мы теперь знаем, что первые два сортируются, а последние три не являются.
>> Мы взглянем на 2.
Сначала мы проверяем его 5.
Это меньше, чем 5?
Это не.
Таким образом, мы должны держать глядя вниз.
Тогда вы проверить 2 от 3.
Это меньше, чем?
Нет.
Таким образом, вы знаете, что 2 должен быть вставлен в передней и 3 и 5
оба должны быть вытеснены.
Сделайте это снова 6 и 4.
И мы просто следите существу, где мы просто проверить, проверить, проверить.
И пока это не в праве должность, мы бы просто
вставьте его в правильном положении, который является, где имя пришел.
>> Так что это просто алгоритм, псевдокод таковой, вроде,
о том, как мы будет осуществлять сортировка вставками.
Псевдокод здесь.
Это все в Интернете.
Не беспокойтесь, если вы, ребята, пытаясь скопировать это вниз.
Итак, еще раз, то же самое, что question-- будет лучшим и худшим автономной работы
для вставки рода?
Это очень похоже на последний вопрос.
Я дам вам, ребята, как, 30 секунд, чтобы думать об этом, а также.
>> ОК ли кто-то хочет дать мне худший выполнения?
Да.
>> АУДИТОРИЯ: п в квадрате.
>> ANDI Пэн: Это н квадрате.
И почему это п квадрате?
>> АУДИТОРИЯ: Потому что в обратный порядок, у вас есть
пройти через п раз п, is--
ANDI Пэн: Да, именно так.
Так же, как и в пузырьковой сортировки.
Если этот список в порядке убывания, вы
придется проверить первый раз.
А потом с каждым дополнительная стоимость, вы
придется проверить его против каждый значение, верно?
И так в целом, вы собираетесь сделать А.Н. раз н-пасс другой п пройти, что
в п квадрате.
Что можно сказать о лучшем случае?
Да.
>> АУДИТОРИЯ: N минус 1, поскольку Первый уже в квадрат.
>> ANDI Пэн: Так, близко.
Ответ на самом деле п.
Поскольку в то время как Первый сортировать, она не может его actually--
мы просто повезло, в что пример, что 2
произошло наименьшее число.
Но не всегда будет так.
Если 2 уже отсортированы в начале но вы посмотрите, и есть 1 здесь,
1 будет поднять его.
И это будет в конечном до того столкнулся в любом случае.
>> Таким образом, в лучшем случае, это на самом деле просто будет н.
Если у вас есть 1, 2, 3, 4, 5, 6, 7, 8, вы
собирается запустить через что весь список сразу
чтобы проверить, если все в порядке.
Это все ясно, на работающем раз отбора, а?
Я знаю, что иду через это очень быстро.
Но точно знаю, что, если вы знаете, общие понятия, вы должны быть хорошо.
ХОРОШО.
Так что я просто дам вам, ребята, может быть, как, минуту, чтобы поговорить с вашими соседями
на то, что лишь некоторые из основных отличий
между этими типами сортов.
Мы пойдем над тем в ближайшее время.
АУДИТОРИЯ: О, хорошо.
ANDI Пэн: Да.
ХОРОШО.
Прохладный, давайте вновь созвать как класс.
ХОРОШО.
Так что это было своего рода открытый вопрос в том смысле,
что есть много ответов на них.
И мы будем идти над некоторыми из них кратко.
Я просто хотел, чтобы вы, ребята думая о том, что дифференцированный
все три типа сортов.
И услышал я, также, большой question-- что же сортировки слиянием сделать?
Большой вопрос, потому что это то, что мы в следующем покрытия.
>> Так объединить рода является один вид, что функции
очень по-разному от других видов.
Как вы, ребята, можете see-- сделал Давид, что демо
где он все круто шумы, видя, как объединить
Сортировать побежал, как бесконечно быстрее, чем двух других типов?
ХОРОШО.
Так это потому, что слияние Сортировать реализует этот разрыв
и завоевать концепцию, что мы говорили о многом в лекции.
В том смысле, что мы хотели бы работать умнее, а не труднее, когда вы разделите
и завоевать проблемы, и сломать их вниз, а затем положить их вместе,
хорошие вещи всегда происходят.
>> Так так, что сливаются Сортировать по существу работает
является то, что делит несортированный массив пополам.
А потом он получил две половинки массивов.
И это как раз те сортирует две половинки.
Он просто держит деления пополам, в половина, пополам, пока все не будет отсортирован
а затем рекурсивно ставит все это вместе.
>> Так что это действительно абстрактной.
Так что это просто немного псевдокода.
Имеет ли это смысл в так, как это работает?
Так что давайте просто сказать, у вас есть массив п элементов, правильно?
Если п меньше, чем 2, вы можете вернуться.
Потому что вы знаете, что, если есть только одна вещь, она должна быть отсортированы.
В противном случае, вы сортировать левую половину, а затем отсортировать правую половину,
и тогда вы сливаются.
>> Так в то время как выглядит на самом деле легко, в действительности, думать об этом это
вид трудно. Потому что вы, как ну вот вроде работает на себя.
Правильно?
Это работает на себя.
Так что в этом смысле, Дэвид коснулся на рекурсии в классе.
И это понятие мы поговорим о более.
Это что это, эти две линии Здесь, на самом деле это просто программа
говорю это, чтобы запустить себя с другой вход.
Таким образом, вместо запуска себя с полнота п элементов,
Вы можете разбить его вниз в левая половина и правая половина
а затем запустить его снова.
>> И тогда мы будем смотреть на него визуально, потому что я визуальный ученик.
Это работает лучше для меня.
Таким образом, мы будем смотреть на наглядном примере здесь.
>> Скажем, мы имеем массив, шесть Элементы, 3, 5, 2, 6, 4, 1, не отсортированы.
Ладно, есть много на этой странице.
Так что, если вы, ребята, можете посмотреть на Первый шаг здесь, 3, 5, 2, 6, 4, 1,
Вы можете разделить его пополам.
У вас есть 3, 5, 2, 6, 4, 1.
Вы знаете, что это вам aren't-- не знаю, если они сортируются или нет,
так вы держите разбивая их в половине, пополам, пополам, пока в конце концов,
у вас есть только один элемент.
И один элемент всегда сортируются, верно?
>> Итак, мы знаем, что 3, 5, 2, 4, 6, 1, сами по себе, сортируются.
И теперь мы можем положить их обратно вместе.
Таким образом, мы знаем 3, 5.
Ставим их вместе.
Мы знаем, что это отсортированный.
В 2-х до сих пор там.
Мы можем поставить 4 и 6 вместе.
Мы знаем, что это сортируется, таким образом, мы положить, что вместе.
А 1 есть.
>> А потом вы просто посмотрите на эти две половинки прямо здесь.
Вы имеете 3, 5, 2, 2, 3, 5.
Вы можете просто сравнить начало всего.
Потому что вы знаете, что это сортируется и вы знаете, что это сортируется.
Тогда вы не должны даже сравнить 5, вы просто сравнить 3.
А 2 меньше, чем 3, так Вы знаете, 2 необходимо перейти в конец.
>> То же самое там.
1-необходимо перейти сюда.
А потом, когда вы идете, чтобы положить эти два значения вместе,
Вы знаете, что это сортируется и Вы знаете, что сортируется.
Так то 1 и 2, 1 составляет менее 2.
Это говорит о том, что 1 должны пойти на конце этого
даже не глядя на 3 или 5.
А потом в 4, вы можете просто проверить, что идет прямо здесь.
Вы не должны смотреть на 5.
То же самое с 6.
Вы знаете, что это просто 6-- не должны быть рассмотрены.
>> И поэтому в этом пути, вы только спасти себя
много шагов, когда вы сравниваете.
Вы не должны сравнивать каждый Элемент с другими элементами.
Вы просто сравните против тех что вам нужно, чтобы сравнить ее с.
Так что вроде абстрактной концепции.
Не беспокойтесь, если это не достаточно удара вас прямо еще.
Но, как правило, это как сортировка слиянием работает.
Вопросы, простых вопросов, прежде, чем я двигаться дальше?
Да.
>> АУДИТОРИЯ: Так вы сказали, что вы берете 1, а затем 4 и 6
и положил их в.
Так не those-- не Вы ищете на них
как отдельные элементы, а не как в целом?
ANDI Пэн: Да.
Так, что происходит является то, что вы в основном
создают совершенно новый массив.
Таким образом, вы знаете, что, вот, у меня есть два массива размером 3, верно?
Таким образом, вы знаете, что мой отсортированный массив должен иметь шесть элементов.
Таким образом, вы просто создать Новый объем памяти.
Так вы вроде как будучи расточительным памяти,
но это не имеет значения потому что это так мало.
Таким образом, вы смотрите на 1 и вы посмотрите на 2.
И вы знаете, что 1 меньше, чем 2.
Таким образом, вы знаете, что 1 должны идти в начало всех тех.
>> Вы даже не нужно смотреть на 3 и 5.
Таким образом, вы знаете, 1 идет туда.
Тогда вы в основном отрубить 1.
Это, вроде бы, умер для нас.
Тогда мы просто должны 2, 3, 5, а затем 4 и 6.
И тогда вы знаете, что вы сравнить 4 и 2,
ой, 2 должны пойти туда.
Таким образом, вы хлопнуть 2 вниз, рубите его.
Тогда вы просто есть 3 и 5 в 4 и 6.
И вы просто держать его измельчение пока вы не положить их в массиве.
>> АУДИТОРИЯ: Так ты просто всегда Сравнивая [неразборчиво]?
>> ANDI Пэн: Точно.
Так что в этом смысле, вы просто сравнение, по сути,
один номер против другой номер.
И потому что вы знаете что это сортируется, вам
не придется искать через все номера.
Вы просто должны посмотреть на первый.
И тогда вы можете просто хлопнуть их вниз, потому что вы знаете,
они принадлежат, где они должны принадлежать.
Да.
Хороший вопрос.
>> И потом, если любой из вас немного амбициозный,
не стесняйтесь, чтобы посмотреть на этот код.
Это на самом деле физическая реализация
о том, как мы должны написать сортировки слиянием.
И вы можете видеть, это очень мало.
Но идеи, лежащие в это довольно сложная.
Так что, если вы чувствуете, как рисунок на это в выполнении домашних заданий сегодня, не стесняйтесь.
>> ХОРОШО.
Так и Давид подошел это в лекции.
Что в лучшем случае Время автономной работы, в худшем случае время автономной работы,
и ожидаемые автономной работы от сортировки слиянием?
Через пару секунд, чтобы подумать.
Это довольно трудно, но вид интуитивным, если вы думаете об этом.
Все в порядке.
>> Зала: в худшем случае п п журнала?
ANDI Пэн: Точно.
И почему это п п войти.
>> АУДИТОРИЯ: Разве это не потому, что он становится экспоненциально быстрее,
так что это, как функции, которые а просто быть п
квадрат или что-то?
ANDI Пэн: Точно.
Таким образом, причина, по которой выполнения на это н журнала
п because--, что ты делать во всех этих шагов?
Вы просто рубить его пополам, верно?
И поэтому, когда мы делаем войти, все, что он делает
делит проблему пополам, в два раза, в два раза, в более половины.
И в этом смысле, вы можете вид из устранить линейную модель
что мы использовали.
Потому что, когда вы нарезать вещи в половине, это журнал.
Вот только математический способ представления его.
>> И, наконец, в конце, вы просто сделать один последний пас через
поставить все из них в порядке, верно?
И так, если вы просто должны проверить одну вещь, это п.
И так ты вроде умножения вместе.
Так что это, как вы получили, что окончательный проверить п сюда с бревна п
здесь.
И если умножить им, что это н н войти.
>> И так в лучшем случае и худшие Корпус и ожидается, все п п войти.
Это также, как другого рода.
Это как выбор рода в том смысле, что
Не имеет значения, что ваш Список, это просто будет
чтобы сделать то же самое каждый раз.
ХОРОШО.
Итак, как вы, ребята, можете видеть, даже если растения, которые мы пошли through-- п
квадрат, это не очень эффективно.
И даже в этом п п журнала не самым эффективным.
Если вы, ребята, интересно, есть механизмы сортировки
которые являются настолько эффективно, что они почти практически плоским в режиме исполнения.
>> У вас есть некоторые журнал N.
У вас есть некоторые журнал журнала N.
Мы не касаемся их в этом классе сейчас.
Но если вы, ребята, интересно, не стесняйтесь Google, что
наиболее эффективные механизмы сортировки.
Я не знаю, есть некоторые действительно смешные,
like-- есть некоторые действительно смешные, которые люди делают.
И вы удивляетесь, как они когда-нибудь думали об этом.
Так Google, если у вас есть запасной Время, на то, что некоторые забавные способы
что people-- а также эффективные ways-- люди
смогли реализовать всевозможные.
ХОРОШО.
И вот только маленький удобный график.
Я знаю все о тебе, до этого викторине 0, будет в вашей комнате, вероятно, пытается
запомнить это.
Так что приятно там для вас, ребята.
Только не забывайте, логику, made-- Поэтому эти цифры были происходит.
Если вы всегда теряется, просто убедитесь, уверен, что вы знаете, что сорта.
И вы можете запустить через их в своем уме
чтобы выяснить, почему те, ответы ответы на эти вопросы.
>> Все в порядке.
Итак, мы собираемся, чтобы переместить на, наконец, поиска.
Потому что, как тех из вас, кто читал PSET,
поиск также является частью Проблема этой неделе задает.
Вам будет предложено осуществить два типа поисков.
Одним из них является линейный поиск и один двоичный поиск.
>> Таким образом, линейный поиск довольно легко.
Вы просто хотите, чтобы поиск элемента из списка, чтобы увидеть, если вы его получите.
Вы просто должны перебора.
И если он равен то, вы можете просто вернуть его, верно?
Но тот, что мы наиболее заинтересованы в разговоре о
это бинарный поиск, право, которое является разделяй и властвуй механизм, который
Дэвид демонстрировал в лекции.
>> Помните пример телефонной книги что он продолжает воспитывать,
тот, который он вроде боролись немного на прошедший год,
где вы разделите задачу на половине, в два раза, в два раза, снова и снова,
пока вы не найдете то, что вы ищете?
И вы получили время выполнения, что хорошо.
И вы можете видеть, это значительно более эффективным
чем любой другой тип поиска.
>> Таким образом, путь, который мы бы идти о реализации двоичного поиска
есть, если у нас было множество, Индекс 0 до 6, семь элементов,
мы можем смотреть в середине, right-- извините, если наш вопрос first--
если мы хотим, чтобы задать вопрос о, не массив содержит элемент 7,
Очевидно, будучи людей, и имеющий такой маленький массив, это просто для нас
чтобы сказать да.
Но путь к реализации двоичный Поиск будет выглядеть в середине.
>> Мы знаем, что индекс 3 средний, потому что мы
знаю, что есть семь элементов.
Что 7 делится на 2?
Вы можете отрубить что дополнительный 1.
Вы получили 3 в середине.
Так массив из 3 равно 7?
Это не правильно?
Но мы можем сделать пару чеков.
Это массив из 3 меньше, чем 7 или это массив из 3 больше, чем 7?
>> И мы знаем, что это меньше, чем 7.
Итак, мы знаем, что, ну, она должна не может быть в левой половине.
Мы знаем, что это должно быть в правой половине, верно?
Таким образом, мы можем просто отрубить половину массива.
Мы даже не должны смотреть на него больше.
Потому что мы знаем, что половина нашего problem--
мы знаем, что ответ находится в правая половина нашей задачи.
Таким образом, мы просто посмотрите на это сейчас.
>> Так что теперь мы смотрим на Середина то, что осталось.
Этот показатель 5.
Мы делаем то же самое еще раз проверку и мы видим, что это меньше.
Таким образом, мы смотрим в левой части, что.
И тогда мы видим, что чек.
Является ли значение массива в Индекс 4 равна 7?
Это.
Таким образом, мы можем вернуться так, потому что мы нашли значение в нашем списке.
Ли путь я прошел что смысл всем?
ХОРОШО.
Я дам вам, ребята, может быть, как, три, четыре минуты, чтобы выяснить,
как псевдокод это.
>> Итак, представьте, я попросил вас написать Функция называется поиск (), что вернулся
значение, логическое значение, что это правда или false-- как,
верно, если вы нашли значение, ложь, если вы не сделали.
И тогда вы были прошел в стоимости вы
искали в ценности, которые это array-- о, я определенно поставить
что в неправильном месте.
ХОРОШО.
В любом случае, что должно быть был справа значений.
А потом Int N это число элементов в этом массиве.
Как бы вы идти о попытке в псевдокоде эту проблему в?
Я дам вам, ребята, как три минуты, чтобы сделать это.
Нет, я думаю, что есть only-- да, есть одна прямо здесь.
АУДИТОРИЯ: Могу ли я?
ANDI Пэн: Да, у меня есть ты.
Это работает?
Ладно, круто.
>> ХОРОШО.
Все правильные парни, мы собирается обуздать его.
ХОРОШО.
Так предположим, что у нас есть эта прекрасная немного массив с п значений в нем.
Я не рисовать линии.
Но как бы мы идти о пытаюсь написать это?
Кто-нибудь хочет дать мне первую линию?
Если вы хотите, чтобы дать мне Первая строка этого псевдокода.
>> АУДИТОРИЯ: [неразборчиво]
АУДИТОРИЯ: Вы хотели для перебора through--
АУДИТОРИЯ: Просто еще один цикл?
АУДИТОРИЯ: --Для.
>> ANDI Пэн: Так что это одно немного сложнее.
Подумайте about-- вы хотите держать работает этот цикл
снова и снова, пока, когда?
>> АУДИТОРИЯ: До [неразборчиво] значение равно этому значению.
ANDI Пэн: Точно.
Таким образом, вы можете на самом деле просто write-- мы можем даже упростить его больше.
Мы можем просто сделать то время как цикл, верно?
Таким образом, вы можете просто loop-- мы знаем, что это какое-то время.
Но сейчас, я собираюсь сказать "петлю" - через что?
Цикл until-- что наш заканчивая состояние?
Я думаю, что я слышал.
Я слышал, кто-то сказать.
>> Аудитория: Значения равна середину.
ANDI Пэн: Скажи это еще раз.
АУДИТОРИЯ: Или, до Значение вы ищете
Для равна среднего значения.
>> ANDI Пэн: Что делать, если это не там?
Что делать, если значение вы ищете для на самом деле не в этом массиве?
АУДИТОРИЯ: Вы возвращаетесь 1.
>> ANDI Пэн: Но то, что мы хотим, чтобы цикл до если у нас есть состояние?
Да.
>> АУДИТОРИЯ: пока есть только одно значение?
ANDI Пэн: Вы можете цикл until-- так что вы знаете, что вы
будет иметь максимальное значение, не так ли?
И вы знаете, что вы собираетесь иметь значение мин, верно?
Потому что также, это то, что Я забыл сказать, прежде чем,
что что-то, что это критически бинарного поиска
является то, что ваш массив уже отсортированы.
Потому что нет никакого способа делать это, если они просто случайные значения.
Вы не знаете, если один это больше, чем другие, верно?
>> Таким образом, вы знаете, что ваш Макс и Ваши минут здесь, верно?
Если вы собираетесь быть регулировки Ваш макс в ваших минут и mid--
давайте предположим, ваш Значение среднего правильно here--
Вы собираетесь в основном цикл до тех пор, минимальная не
примерно то же самое, как ваш макс, прямо или если ваш максимум не то же самое, как ваш мин.
Правильно?
Потому что, когда это произойдет, вы знаете, что Вы в конечном итоге попал в такое же значение.
Так вы не хотите, чтобы петли, пока ваш мин меньше или равно, целью которых упс,
не менее или равно, иначе around-- Макс.
>> Разве что смысл?
Я взял несколько попыток, чтобы получить это право.
Но цикл, пока ваш максимального значения по сути почти нет
чем или равно вашей минимум, верно?
Вот когда вы знаете, что вы сошлись.
АУДИТОРИЯ: Когда ваша максимальная значение меньше, чем минимум?
ANDI Пэн: Если вы держите регулируя его, что
это то, что мы собираемся чтобы делать в этом.
Имеет ли это смысл?
Минимальная и максимальная просто целые числа, мы, вероятно,
собирается хотите создать, чтобы держать трек, где мы ищем.
Поскольку массив существует независимо от того, что мы делаем.
Мол, мы на самом деле не физически отрубание массива, верно?
Мы просто регулируя где мы ищем.
Имеет ли это смысл?
>> АУДИТОРИЯ: Да.
>> ANDI Пэн: ОК.
Так что, если это условие нашей петли, то, что мы хотим внутри этой петли?
Что мы собираемся быть желание сделать?
Так что сейчас, у нас есть макс и мин, право,
вероятно, создана где-то здесь.
Мы собираемся, вероятно, хотите найти середину, верно?
Как мы собираемся, чтобы быть возможность найти середину?
Что mathematical--
АУДИТОРИЯ: Макс плюс мин разделены на 2.
ANDI Пэн: Точно.
Имеет ли это смысл?
И вы, ребята, понять, почему мы не просто use--, почему мы сделали это
а не делать просто п делится на 2?
Это потому, что п является значение что собирается остаться то же самое.
Правильно?
Но, как мы скорректируем нашу минимум и Максимальные значения, они собираются изменить.
И в результате, наш средний собирается менять слишком.
Так вот почему мы хотим сделать это прямо здесь.
ХОРОШО.
>> А потом, в настоящее время, что мы нашли our-- да.
>> АУДИТОРИЯ: Просто быстро question-- когда вы говорите, мин и макс,
мы предполагая, что это уже отсортированы?
>> ANDI Пэн: Да, это на самом деле предпосылкой для бинарного поиска,
что вы должны знать, что это сортируется.
Именно поэтому-то, вы пишете в вашем Проблема установить до вашего бинарного поиска.
ХОРОШО.
Так что теперь мы знаем, где наша середина является то, что вы хотите сделать здесь?
>> АУДИТОРИЯ: Мы хотим, чтобы сравнить что к другому.
ANDI Пэн: Точно.
Таким образом, вы будете сравнивать с середины до значения, не так ли?
И что это говорит нам, когда мы сравниваем?
Что мы хотим делать дальше?
>> АУДИТОРИЯ: Если значение больше чем середине, мы хотим, чтобы отрезать его.
ANDI Пэн: Точно.
Таким образом, если значение больше чем середине, мы
захочет изменить эти Минимальное и исчерпан, верно?
Что мы хотим изменить?
Так что, если мы знаем, что где-то значение здесь, что вы у нас изменить?
Мы хотим изменить нашу Минимальный быть в середине, не так ли?
А потом еще, если он находится в этом половина, что мы хотим изменить?
>> АУДИТОРИЯ: Ваша максимальная.
ANDI Пэн: Да.
А потом вы просто держать цикл, верно?
Потому что сейчас, после одной итерации через, у вас есть макс здесь.
И тогда вы можете пересчитать середине.
И тогда вы можете сравнить.
И вы собираетесь продолжать не до минут и Maxes
существенно сошлись.
И вот, когда вы знаете, что Вы попали в конец.
И либо вы нашли его или вы не в этой точке.
>> Имеет ли это смысл для всех?
ХОРОШО.
Это очень важно, потому что вы будете иметь
чтобы написать это в коде сегодня.
Но вы, ребята, есть очень хороший чувство, что вы должны делать,
и это хорошо.
ХОРОШО.
Итак, мы получили около семи минуты осталось раздел.
Таким образом, мы будем говорить о это PSET, что мы будем делать.
Таким образом, PSET разделен на две половины.
Первая половина включает реализации находку
в котором Вы пишете, линейный поиск, А бинарный поиск, и алгоритм сортировки.
>> Таким образом, это является первым раз в PSET где
мы будем давать вам, ребята, что называется Код распределения, который является код
что мы предварительно написано, но просто оставили несколько кусков от
для Вас, чтобы закончить запись.
Таким образом, вы, ребята, когда вы смотрите на это Код, вы могли бы получить действительно страшно.
Если вы просто хотите, Ах, я не знаю, что делает,
Я не знаете, как, кажется, что так сложно, ах, расслабиться.
Это нормально.
Читайте спецификацию.
Спецификация будет объяснить вам точно что все эти программы делают.
>> Например, generate.c программа что придет с вашего PSET.
Вы на самом деле не имеют к ней прикоснуться, но Вы должны понимать, что он делает.
И generate.c, все это делает, либо генерации случайных чисел
или вы можете дать ему семя, как у условный номер, который он принимает,
и генерирует больше число.
Таким образом, есть определенный способ, чтобы осуществить generate.c, в котором
вы можете просто сделать кучу цифр для вас, чтобы проверить свои другие методы на.
>> Так что, если вы хотите, чтобы для Например, проверить свои находки,
Вы хотели бы, чтобы запустить generate.c, генерировать кучу цифр,
а затем запустить функцию помощников.
Ваша функция помощники где вы на самом деле физически написания кода.
И думаю, помощников в виде файла библиотеки Вы пишете, что находка звонит.
И так в течение helpers.c, вы будете сделать поиска и сортировки.
>> И тогда вы будете по существу просто положить их все вместе.
Спецификация скажет вам, как положить, что в командной строке.
И вы сможете проверить, является ли не ваша сортировки и поиска работают.
Круто.
Кто-нибудь уже началась, и встречающиеся проблемы или вопросы
они имеют сейчас с этим?
ХОРОШО.
>> АУДИТОРИЯ: Подождите.
У меня есть вопрос.
>> ANDI Пэн: Да.
>> АУДИТОРИЯ: Так что я начал делать линейный поиск в helpers.c
и это не было действительно работает.
Но потом я узнал, мы просто должны удалить его и сделать бинарный поиск.
Так не все ли равно, если он не работает?
>> ANDI Пэн: Короткий ответ: нет.
Но так как мы не--
АУДИТОРИЯ: Но никто не на самом деле проверки.
ANDI Пэн: Мы никогда не увидите, что.
Но вы, вероятно, хотите, чтобы что ваш поиск работы.
Потому что, если ваш линейный поиск не работает,
то скорее всего, ваш бинарный Поиск не будет работать, как хорошо.
Потому что у вас есть подобное Логика в них обоих.
И нет, это не имеет значения.
Таким образом, единственными вы включите в являются своего рода и бинарный поиск.
Да.
>> А также, много детей были пытаясь собрать helpers.c.
Вы на самом деле не допускаются чтобы сделать это, потому что helpers.c
не имеет основную функцию.
И поэтому вы должны только быть на самом деле компиляции
генерировать и найти, потому что найти звонки helpers.c и функции в ней.
Так что делает отладку боль в заднице.
Но это то, что мы должны делать.
АУДИТОРИЯ: Вы просто сделать все, верно?
ANDI Пэн: вы можете просто сделать все как хорошо, да.
ХОРОШО.
Так вот оно что в плане того, что PSET просит, чтобы вы все делаете.
Если у вас есть какие-либо вопросы, пожалуйста, свободным спросить мне после раздела.
Я буду здесь, как, 20 минут.
>> И да, Pset-х действительно не так уж плохо.
Вы, ребята, должно быть в порядке.
Они, просто следуйте рекомендациям.
Вид есть чувство, по логике, то, что должно происходить, и вы будете в порядке.
Не слишком страшно.
Там очень много кода уже написано.
Не слишком страшно, если вы не понять, что все это значит.
Если это много, это совершенно нормально.
И пришли к офисной часов.
Мы поможем вам взглянуть.
>> АУДИТОРИЯ: с дополнительными Функции, мы смотрим те до?
>> ANDI Пэн: Да, те в коде.
В игре 15, половина из это уже написана для вас.
Так что те функции уже в коде.
Ага.
Все в порядке.
Ну, удачи.
Это отвратительно день.
Так надеюсь, вы, ребята, не чувствовать себя слишком плохо о пребывании внутри и кодирования.