Подготовка к практическому заданию и вопросы для самопроверки

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

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

Цели

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

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

Начинаем

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

Итак, зайдите в терминал «Виртуальной лаборатории» или залогиньтесь на cs50.io и выполните команду 

update50

чтобы убедиться в актуальности версии рабочего пространства.

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

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 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. 

Если вы вместо предыдущего, используя 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).

Как команда 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! (почему?) Все строки, которые начинаются со знака # — это просто комментарии.