• ,

Гарвард CS50: задания третьей недели (лекции 7 и 8), часть 1

Лекции Гарвардского курса по основам программирования CS50
Дополнительные материалы: асимптотическая нотация, алгоритмы сортировки и поиска
Часть вторая. «Пятнашки» на Си

Подготовка


Прежде, чем браться за задачи, посмотрите лекции 7-8, прочитайте и вникните в «Дополнительные материалы третьей недели». Они посвящены алгоритмам поиска (линейному и бинарному), сортировки (много их!), а также работе дебаггера (умение работать с дебаггером для отладки программ — чрезвычайно важный навык!).

Если с лекциями и теорией все пошло, как надо, вы без труда ответите на проверочные вопросы:

  • Почему бинарный поиск требует отсортированного массива?
  • Почему оценка сортировки пузырьком равна O (n2)?
  • Почему оценка сортировки вставками — это Ω (n)?
  • Как работает сортировка выбором? Опишите в трех предложениях (или меньше).
  • Каков верхний предел (наихудший случай) времени работы сортировки слиянием?
  • Дебаггер GDB позволяет отладить программу. А если сформулировать конкретнее, что именно он позволяет делать?

Цели


  • Научиться работать с проектами, которые содержат несколько файлов
  • Научиться читать чужой исходный код
  • Усвоить различные алгоритмы и рекурсивные функции

Большинство из этих целей формально оценить практически нереально. Поэтому, с точки зрения формальной проверки задач, здесь мало что покажется вам сложным. Тем не менее, напоминаем: научиться программированию можно только постоянно практикуясь! Поэтому призываем вас не просто решить задания, но также потратить дополнительные время и усилия и реализовать все те алгоритмы, которые были рассмотрены на этой неделе. Вперед!

Начинаем

Напомним, для решения практических задач на первой и второй неделе, вы писали программы с нуля и создали собственные каталоги pset1 и pset2 с помощью команды mkdir. Для практического задания третьей недели, нужно загрузить дистрибутив (или «дистро», мы так его называем), написанный нами, и добавить туда собственные строки кода. Сначала вчитайтесь в наш код и постарайтесь его понять. Важнейший навык этой недели — научиться читать чужой код.

Итак, залогиньтесь на cs50.io и выполните команду

update50

в терминальном окне, чтобы убедиться в актуальности версии рабочего пространства. Если вы случайно закрыли терминальное окно и не можете его найти, зайдите в меню View и убедитесь, что напротив пункта Console стоит галочка (поставьте её, если это не так). Кликните на(+), внутри зеленого круга на рамке терминального окна, выберите New Terminal.



После этого выполните команду

cd ~/workspace

и убедитесь, что вы находитесь внутри директории workspace (это ваш каталог). После этого выполните команду:

wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip

чтобы загрузить ZIP-архив задачника в ваше рабочее пространство (wget — команда linux для загрузки). Если всё ок, в строке вы увидите такую фразу:

'pset3.zip' saved

Убедитесь, что вы действительно скачали pset3.zip выполнив команду:

ls

а затем запустите

unzip pset3.zip

чтобы разархивировать файл. Если теперь вы еще раз запустите команду ls, вы также увидите директорию pset3. Перейдите в неё, выполнив команду

cd pset3

а затем снова запросите просмотр содержимого директории:

ls

вы увидите, что в этой директории есть две поддиректории:

fifteen  find

Уже интригует!

Поиск

Давайте теперь нырнем в одну из этих поддиректорий. Для этого выполним команду:

cd ~/workspace/pset3/find

Если вы выведете содержимое этой папки на экран (вы уже, наверное, помните, как это делать), вот что вы должны увидеть:

helpers.c  helpers.h  Makefile  find.c  generate.c

Ух ты, файлов хватает. Но не беспокойтесь, сейчас мы с ними разберёмся.
В файле generate.c размещён код программы, которая использует «генератор псевдослучайных чисел» (генерация посредством функции drand48) чтобы сгенерировать большое количество случайных (по правде говоря, псевдослучайных, компьютеры не могут работать с чистой случайностью!) чисел, и разместить их по одному в строке. Скомпилируйте программу:

make generate

Теперь запустите её, выполнив команду:

./generate

Программа выдаст вам следующее сообщение:

Usage: generate n [s]

Это значит, что программа ожидает один или два аргумента командной строки. Использование первого, n, обязательно; это число означает, сколько псевдослучайных чисел вы хотите создать. Параметр s не является обязательным, на что указывают квадратные скобки. Число s можно назвать «семенами» для генератора псевдослучайных чисел. Под «семенами» подразумеваем входные данные в генератор псевдослучайных чисел, которые влияют на его вывод.

Например, если вы используете drand48, сначала вызвав srand48 (еще одна функция, цель которой заключается в „посеве“ drand48) с аргументом, скажем, 1, а затем вызовете drand48 три раза, drand48 может вернуть 2728, потом 29785, потом 54710.

Tсли вы вместо предыдущего, используя drand48, сначала вызовете srand48 с аргументом, скажем, 2, а затем снова используете drand48 три раза, drand48 может вернуть 59797, потом 10425, потом 37569. Но если вы повторно «посеете» drand48, вызывая srand48 снова с аргументом 1, в результате следующих трех вызовов drand48 вы снова получите 2728, потом 29785, потом 54710!

Видите, все происходит совсем не случайно.
Запустите программу еще раз, на этот раз, скажем, n = 10, как показано ниже; вы увидите список из 10 псевдослучайных чисел.

./generate 10

Давайте запустим программу в третий раз с тем же значением n; вы должны увидеть другой список из 10 цифр. Теперь попробуйте запустить программу с двумя параметрами. Давайте возьмем s = 0, как показано ниже.

./generate 10 0

Теперь запустите ту же команду еще раз:

./generate 10 0

Можно даже не спорить: вы снова увидели ту же самую «случайную» последовательность из десяти цифр. Вот что произойдет, если вы не будете менять «семена» генератора псевдослучайных чисел.

Теперь посмотрим на саму программу generate.c (помните, как?).
Комментарии в начале этого файла объясняют общую функциональность программы. А вот сам код мы, похоже, забыли прокомментировать. Внимательно вчитайтесь в код, и читайте его до тех пор, пока не уловите смысл каждой строки. После этого прокомментируйте этот код вместо нас, заменяя каждый TODO фразой, описывающей цель или функциональность соответствующей строки или строк кода. (примечание: unsigned int — это «беззнаковый» int, то есть он не может быть отрицательным). Чтобы получить более подробную информацию о rand или srand, выполните:

man drand48

или

man srand48

После того, как в generate.c откомментируете всё, что можно, перекомпилируйте программу, чтобы убедиться, что вы ничего не сломали:

make generate

Если generate больше не компилится, чините, что сломали:)!

Напомним: команда make автоматизирует компиляцию кода, поэтому вам не придется выполнять команду clang вручную подставляя кучу переключателей. Но на самом деле make просто упрощает нам ввод, а на деле за ним спрятан тот же clang с нужными нам параметрами. Однако когда ваши программы станут больше по размеру, make не сможет больше выяснить из контекста, как компилировать код. В таком случае вам придется указать make, как нужно скомпилировать программы, особенно если они связаны с использованием различных исходных файлов (например, .c). Для решения этой проблемы мы будем использовать файлы конфигурации (Makefiles), которые точно указывают make, что нужно делать.

Как команда make узнала, как нам следует компилировать generate? На самом деле команда использовала конфигурационный файл, который мы уже написали. Этот файл называется Makefile и он лежит в той же директории, что и generate.c. Makefile — некий список правил, указывающих, как создать файл generate из generate.c. В файле вы найдете, в частности соответствующие строки:

generate: generate.c
    clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c

Первая строка говорит make, что „цель“ под названием generate должна быть создана путем вызова команды из второй строки. Более того, первая строка указывает make, что generate зависит от generate.c, смысл которого в том, что make будет только пересобирать generate в ходе последующих запусков, если этот файл был изменен. Неплохой трюк для экономии времени, не так ли? На самом деле, выполните команду ниже снова, если вы не меняли generate.c.

make generate

Вам сообщат, что generate уже обновлен до текущей версии.

Замечание: отступление в начале второй строки не является последовательностью пробелов, это, скорее, знак табуляции. К сожалению, make требует, чтобы командам предшествовали знаки табуляции, так что будьте осторожны, чтобы не изменить их на пробелы, иначе вы столкнетесь с непонятными ошибками! Флаг -Werror говорит команде clang считать предупреждения (плохо) ошибками (еще хуже), так что вы будете вынуждены (в хорошем, обучающем смысле!) исправить их.

Теперь посмотрим на файл find.c. Обратите внимание, эта программа ожидает один аргумент командной строки: „иглу“, которую нужно найти в «стоге сена» значений. После этого, просмотрите код и скомпилируйте программу, выполнив команду ниже.

make find

make практически вывел для нас следующее:

clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm

Обратите внимание! Только что вы скомпиллировали приложение, состоящее е из одного, а из двух файлов: helpers.c и find.c. Каким образом об этом узнала make? Чтобы понять это, снова откройте файл Makefile, чтобы понять, что там на самом деле творится. Соответствующие строки ниже.

find: find.c helpers.c helpers.h
clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm

Под зависимостью (после двоеточия) можно понимать то, что все изменения в файлы find.c, helpers.c, или helpers.h вынудят make пересобирать find следующий раз, когда она будет вызвана для этих целей.
Теперь запустите эту программу, выполнив, например, следующее:

./find 13

После этого вам поступит предложение предоставить некий стог (то есть целые числа), и подавать их по одной соломинке за раз. Как только вы устанете от ввода чисел, нажмите комбинацию клавиш Ctrl-D. Эта комбинация пошлет программе символ конца файла (EOF, end-of-file). Символ вынудит функцию GetInt из библиотеки CS50 вернуть константу INT_MAX, а она, в свою очередь в find.c заставит find прекратить набирать «стог».
Теперь программа будет искать иглу в том стоге сена, что вы предоставили, и в конечном счете она сообщит, была ли она найдена. Говоря кратко, программа выполняет поиск некоторого значения в массиве. По крайней мере, она должна, но загвоздка в том, что пока что она ничего не найдет! Но тут на помощь приходите вы! О важности вашей роли поговорим чуть позднее.

На самом деле процесс предоставления стога можно автоматизировать хотя бы по „слиянию“ вывода generate в find в качестве входных данных. Например, команда ниже передает 1000 псевдослучайных чисел в find, которая затем ищет среди этих значений 42.

./generate 1000 | ./find 42

Обратите внимание: когда generate передает исходные данные в find, вы не видите числа generate, но вы увидите работу find.

В качестве альтернативы, вы можете „перенаправить“ вывод generate в файл с помощью такой команды:

./generate 1000 > numbers.txt

Содержимое этого файла можно перенаправить на вход find с помощью команды:

./find 42 < numbers.txt

Давайте еще разок посмотрим на код в Makefile и обратим внимание на следующую строку:

all: find generate

Это означает, что вы можете собрать generate и find, выполнив следующую команду:

make all

Более того, команда под этой строкой эквивалентна команде над ней, поскольку make строит первую запись в Makefile по умолчанию.

make

Если бы вы только могли свести все эти практические задания к одной команде! Но — увы!
Наконец, обратите внимание на эти последние строки в Makefile:

clean:
    rm -f *.o a.out core find generate

Эта запись позволяет вам удалить все файлы, которые заканчиваются на .o или называются core (это мы поясним чуть позднее!), а также запустить программы find или generate просто выполнив строку:

make clean

Если захотите экспериментировать, то вот с чем будьте осторожны: не добавляйте, скажем, *.c в эту последнюю строку Makefile! (почему?) Все строки, которые начинаются со знака # — это просто комментарии.

Задание 1: Search


Пришло время для кое-чего интересного! Обратите внимание, find.c вызывает search, функцию, объявленную в helpers.h. К сожалению, мы забыли реализовать эту функцию полностью в helpers.c! (Надо отметить, что мы могли бы поместить содержимое helpers.h и helpers.c в один find.c. Но иногда лучше разделять программы на несколько файлов. Особенно если некоторые функции, точнее функции-утилиты, могут оказаться полезными и для других программ. Как, например, функции из библиотеки CS50.

Взгляните на helpers.c и вы увидите, что search всегда возвращает значение false, независимо от того, занесено ли данное значение value в values. Перепишите search таким образом, чтобы она использовала линейный поиск, возвращая true, если value входит в values и false, если value не входит в values. Позаботьтесь о том, чтобы вернуть false сразу, если n не является положительным.
Когда вы будете готовы к проверке правильности, попробуйте вызвать следующую команду:

./generate 1000 50 | ./find 127

Поскольку одно из чисел, выведенных с помощью generate, когда «засеивали» 50, равно 127, ваш код должен найти „иголку“! Для контраста попробуйте выполнить и такую команду:

./generate 1000 50 | ./find 128

Поскольку 128 не входит во множество чисел, выведенных функцией generate, когда «засеивали» 50, ваш код не должен найти «иглу». Проведите и другие тесты, запуская generate с каким-то семенем, анализируя выходные данные, и ища «иголку», которая должна быть в «стогу».

Обратите внимание, что main в find.c написана таким образом, что find возвращает 0, если «игла» найдена, иначе — возвращает 1. Вы можете проверить так называемый „выходной код“, который main возвращает при выполнении

echo $?

После запуска некоторых других команд. Например, если ваша реализация search — правильна, если вы запустите

./generate 1000 50 | ./find 127
echo $?

Вы увидите 0, пока 127 есть среди тех 1000 чисел, выведенных с помощью generate с семенем 50, поэтому написанный вами поиск search должен возвратить true. В этом случае main (написанный нами) должен вернуть 0 (то есть завершить работу). Если же вы зададите следующие входные данные

./generate 1000 50 | ./find 128
echo $?

Вы увидите 1, поскольку 128 не находится среди тех 1000 чисел, которые были выведены с помощью generate с семенем 50. В этом случае search (написанный вами) вернет false, и main (написанный нами) вернет 1 (и с тем закончит работу). Сечёте логику?

Когда всё будет готово для проверки с помощью check50, выполните такую команду:

check50 2015.fall.pset3.find helpers.c

Кстати, не стоит привыкать тестировать код с помощью check50 перед собственным тестированием. Всё-таки check50 не в реальности не существует, поэтому запуск кода с вашими собственными входными выборками, сравнение фактического вывода к ожидаемым выходных данных, — лучшая привычка, которую можно обрести на этом этапе. Правда-правда, не приобретайте вредную зависимость!

Если вам интересно поиграть с реализацией find, выполненной ассистентами cs50, выполните такую команду:

~cs50/pset3/find

Сортировка


Линейный поиск — это не то, что по-настоящему впечатляет, но с первых лекций (а в седьмой мы снова повторили этот трюк!) вы помните, что найти иглу в стоге сена можно гораздо быстрее. Только сперва нужно отсортировать наш стог сена.

Обратите внимание: find.c вызывает sort, функцию, объявленную в helpers.h. К сожалению, мы «забыли» реализовать эту функцию в полной мере в helpers.c! Загляните в helpers.c, и вы увидите, что происходит мгновенное возвращение sort, хотя функция main из find действительно передает ей фактический массив.
Теперь вспомните синтаксис объявления массива. Вы не только указываете тип элементов этого массива, но также задаете его размер в квадратных скобках. Так мы делаем для haystack в find.c:

int haystack [MAX];

Но при прохождении массива вы только указываете его имя. И мы это делаем точно так же, когда проходим haystack, чтобы выполнить sort в find.c:

sort (haystack, size);

(Догадайтесь, почему мы передаем размер этого массива отдельно?)
Когда мы объявляем функцию, которая принимает в качестве аргумента одномерный массив, не нужно указывать размер массива. Точно так же мы этого не делали, когда объявляли sort в helpers.h (и helpers.c):

void sort (int values [] int n);

Реализуйте sort, так чтобы функция действительно отсортировывала массив чисел от меньших к большим. Нужно, чтобы время ее работы было равно O (n2), где n — размер массива. Скорее всего, вы захотите реализовать метод пузырьковой сортировки, сортировка выбором, или вставкой, поскольку мы изучили их на третьей неделе. Тем не менее, важно отметить: „правильного“ способа реализации не существует для этих алгоритмов. Есть огромное количество вариаций. На самом деле, вы всегда можете улучшить их, если считаете нужным, до тех пор, пока ваша реализация сойдется к O (n2). Тем не менее, эксперименты оставьте для тела функции, а с целью упрощения проверки, не меняйте нашу декларацию sort. Она должна выглядеть так:

void sort (int values [] int n);

Поскольку функция возвращает значение типа void, она не должна возвращать отсортированный массив. Вместо этого, она должна „деструктивно“ сортировать фактический массив, по которому она «пробегает», перемещая его элементы. На четвертой неделе мы будем обсуждать, что массивы передаются не по значению, а по ссылке. То есть, sort не получит копии массива, а сам исходный массив.

Хотя вы не можете изменить нашу декларацию sort, вы всегда можете определить свою собственную функцию в helpers.c, которые затем можно будет вызвать из sort.

Выберите сами, как лучше протестировать реализацию вашей sort. Не стоит забывать, что printf и GDB вам помогут! И не забывайте, что вы можете создать ту же последовательность псевдослучайных чисел снова и снова, явно указывая значения семян для generate.

Бинарный поиск, советы


Первое, что необходимо понимать о функции find — у нас уже есть написанный код (дистрибутив). Мы просто заполняем некие пробелы в уже существующем коде.

Программа find.c запрашивает ввод чисел (то есть, заполнить «стог»), а потом ищет в нем «иголку» по запросу пользователя, используя для этого sort и search — функции, определенные в helpers.c. Таким образом, find уже написана, нам нужно написать helpers.

Итак, вот что нам нужно сделать:

  1. Реализовать search. Эта функция должна возвращать true, если значение найдено в «стогу» и false, если его там нет.
  2. Реализовать sort, функцию, сортирующую массив значений.

Изначально поиск реализован как линейный. Но вы можете сделать лучше. Алгоритм линейного поиска выполняется за время О(n). Ваша задача — написать алгоритм бинарного поиска. Время его исполнения — O(log n). Однако его проблема в том, что ему на вход нужно подавать отсортированные данные, иначе он не будет работать. Вы помните пример с разорванной книгой, и, вероятно, знаете, почему так.

Если вы прошлись бинарным поиском по элементам и их больше не осталось (то есть в этом «стоге» нашей «иголки» попросту нет), нужно, чтобы функция вернула false.

Бинарный поиск можно реализовать итеративно или рекурсивно (о рекурсии Дэвид Малан рассказал в восьмой лекции).

4 комментария

NikSue
«Теперь посмотрим на саму программу generate.c (помните, как?).» здесь всё-таки не понятно как открыть файл посмотреть на программу и меня архив не разархивирован. Файл find.c тоже не вижу.
NikSue
уже разобрался сам))), не всё выполнил как положено.
marcell
После того, как мы реализовали бинарный поиск, утилита check50 уже не тестирует программу? То есть тестирует, но сообщает, что она работает неверно, ведь она проверяет лишь сам поиск, а он не работает без сортировки входящих данных. Или я что-то не так понимаю?
sibkedr
тестирует. У меня работает верно. Без сортированного массива бинарный поиск не будет работать, но они как раз и дают для проверки отсортированный массив. Вот что у меня выдало, когда я реализовал бинарный поиск (впрочем, тоже самое что и при линейном)
:) helpers.c exists
:) helpers.c compiles
:) finds 42 in {42,43,44}
:) finds 42 in {41,42,43}
:) finds 42 in {40,41,42}
:) finds 42 in {41,42,43,44}
:) finds 42 in {40,41,42,43}
:) finds 42 in {39,40,41,42}
:) doesn't find 42 in {39,40,41}
:) doesn't find 42 in {39,40,41,43}
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.