Создайте программу, которая будет искать число среди определенного количества других чисел.
$ ./generate 1000 | ./find 42
Didn't find needle in haystack.
(Иголка в стоге сена не была найдена)
$ wget https://github.com/cs50/problems/archive/find.zip
$ unzip find.zip
$ rm find.zip
$ mv problems-find find
$ cd find
$ ls
Makefile find.c generate.c helpers.c helpers.h
В файле generate.c реализована программа, использующая “генератор псевдослучайных чисел” (с помощью функции drand48) для генерации целой кучи случайных чисел (на самом деле псевдослучайные, т.к. компьютер не может создавать по-настоящему случайные числа) по одному на строку, каждая из которых в пределах [0, LIMIT), где LIMIT (лимит, предел) является константой (заданное и не изменяющееся число), заданной внутри файла. Т.е. каждое число больше или равно 0 и меньше чем LIMIT.
Скомпилируйте программу, выполнив код ниже.
make generate
Теперь запустите ее следующим образом.
./generate
Вас должны уведомить о правильном использовании программы, как показано ниже.
Usage: generate n [s]
Данная строка говорит нам о том, что эта программа ожидает один или два аргумента командной строки. Первый аргумент n - обязательно должен присутствовать; он указывает сколько псевдослучайных чисел должно быть сгенерировано. Второй аргумент s не обязательно указывать (поэтому он был помещен в квадратные скобки); если же его предоставили, он будет обозначать число, которое будет использовано генератором псевдослучайных чисел в качестве “зернышка” (то, которое сеют для получения урожая). Зернышко используется на входе генератора псевдослучайных чисел, влияя на его выходные данные. К примеру, если вы посеете зернышко в drand48, сперва использовав srand48 (еще одна функция, предназначенная для “сеяния” зернышка в drand48), используя к примеру аргумент 0 и затем вызовите три раза функцию drand48 - drand48 может вернуть 0.170828, потом 0.749902 и 0.096372. Но если вы посеете зернышко в drand48, сперва вызвав функцию srand48 с использованием аргумента 1, и затем вызовите три раза функцию drand48 - drand48 может теперь уже вернуть 0.041630, потом 0.454492 и 0.834817. Но если вы повторно посеете зернышко в drand48, вызвав функцию srand48, использовав аргумент 0, следующий раз вызвав три раза функцию drand48 - вы опять получите 0.170828, потом 0.749902 и 0.096372! Видите, не так уж это и случайно.
Повторно запустите эту программу, но на этот раз со значением, к примеру 10 для n, как указано ниже. Должен появится список из 10 псевдослучайных чисел.
./generate 10
Запустите программу в третий раз, используя тоже самое значение n, и вы увидите список с другим набором значений. Теперь попробуйте запустить программу, дав значение s (т.е. 0), как показано ниже.
./generate 10 0
Опять запустите ту же самую команду:
./generate 10 0
Спорим, вы опять увидели ту же самую последовательность чисел? О да, вот что происходит если вы не используете разные зернышки для псевдослучайного генератора чисел.
Теперь разберем сам файл generate.c. (Помните как?) Комментарии, находящиеся в верхней части данного файла, объясняют общие возможности программы. Но похоже мы забыли дать комментарии к самому коду. Тщательно прочитайте код, пока вы не будете понимать каждую его строчку, а потом добавьте комментарии к нашему коду, заменяя каждый TODO (ЗАДАЧА или что делать) фразой, описывающей смысл или функциональность соответствующих строк кода. (Знайте, что unsigned int это обычный int, который не может быть отрицательным). Не забывайте, что вы всегда можете найти в интернете документацию на drand48 и srand48, которая поможет вам лучше понимать их функционал.
Закончив комментировать код generate.c, перекомпилируйте программу, дабы быть уверенным, что вы ничего не сломали, выполнив команду.
make generate
Если generate более не компилируется, сделайте паузу и посмотрите, где вы могли допустить ошибку.
Теперь вспомните, что make автоматизирует компиляцию вашего кода, чтобы вам не пришлось вручную прописывать clang вместе с его многими аргументами. Заметьте, как make прописала и запустила за вас приличного размера команду, которая является выходными данными. Но, с увеличением размера вашей программы, make больше не сможет сама по себе компилировать ваш код. Вам придется начать говорить make, как компилировать вашу программу, в частности когда дело касается нескольких исходных файлов (т.е. .c). И теперь мы будем полагаться на “Makefiles” - файлы конфигурации, которые говорят make, какие именно шаги нужно применять.
Как make узнал, каким образом компилировать программу “generate” в данном случае? На самом деле он использовал конфигурационный файл, который мы ранее создали. Давайте откроем файл Makefile, который находится в той же папке что и generate.c. Этот Makefile в своей основе представляет список правил, который мы написали для вас, говорящий “make”, как создавать программу “generate” из файла generate.c. Соответствующие строки указываются ниже.
generate: generate.c
clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c
Первая строка говорит make, что “цель”, имеющая название generate, должна быть создана вызовом команды второй строки. Знайте, что пропуск в начале второй строки - это не последовательность пробелов, а единожды нажатая кнопка “tab”. К сожалению, для make является принципиальным, чтобы команды начинались с “tab”, поэтому будьте осторожнее и смотрите, не изменяйте их на пробелы, в противном случае вы столкнетесь со странными ошибками! Флаг или аргумент -Werror говорит clang‘у воспринимать предупреждения (плохо), как будто бы они были ошибками (намного хуже), чтобы заставить вас (в хорошем, поучительном смысле!) исправить их.
Теперь посмотрите на find.c. Заметьте, что эта программа ожидает один аргумент командной строки: “иголку”, которая будет искаться в “стоге” значений. Как только закончите работать с кодом, можете компилировать программу, выполнив команду, написанную ниже.
make find
Заметьте, посмотрев на вывод команды, что make на самом деле выполнила следующее.
clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm
Еще вы скомпилировали программу, включающую в себя не один, а два .c файла: 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
Вам будет предложено предоставить немного сена (т.е. немного integer’ов), по одной “соломинке”. Как только вам надоест предоставлять integer’ы, нажмите на клавиатуре ctrl + d, чтобы отправить программе символ EOF (end-of-file или конец файла). Данный символ вынудит функцию библиотеки CS50 get_int вернуть 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! (Почему?)
Заметьте, что в find.c main вызывает search - функцию, объявленную в helpers.h. К сожалению, мы забыли полностью реализовать эту функцию в helpers.c! Загляните в helpers.c и вы увидите, что search всегда возвращает false (ложь), вне зависимости от того, есть ли значение в значениях. Для надежности мы могли бы поместить содержимое helpers.h и helpers.c в саму find.c. Но иногда лучше распределять программы в несколько файлов, тем более если некоторые функции являются “полезными функциями”, которые в будущем могут пригодиться другим программам - как, к примеру, те, что в библиотеке CS50.
Также заметьте в соответствии с helpers.h, что прототип search выглядит вот так:
bool search(int value, int values[], int n);
А прототип sort так:
void sort(int values[], int n);
Обе функции принимают массив values в виде одного из своих аргументов, также и integer n - размер данного массива. Это потому, что, передавая функции массива, вы должны передавать его размер отдельно; вы не можете вывести размер массива из самого массива.
Закончите реализацию программы find, продолжив написание программ search и sort в helpers.c.
searchВаш код должен сразу же вернуть false (ложь), если n будет не положительным.
Ваш код должен вернуть true (истину), если значение окажется в значениях, и - false (ложь), если значения не будет в значениях.
Время работы вашего кода должно быть в границах O(log n).
Вам нельзя изменять объявление функции. Прототип должен оставаться тем же:
bool search(int value, int values[], int n);
sortВаша программа должна сортировать числа массива, переданные ей, начиная от меньшего и заканчивая наибольшим.
Время выполнения вашего кода должно быть в O(n2), где n - размер массива.
Вам нельзя менять объявление функции. Прототип должен оставаться тем же:
void sort(int values[], int n);
Ваша программа должна проделывать тоже самое, что показано в примере ниже.
$ ./find 42
50
43
^d
Didn't find needle in haystack.
$ ./find 42
50
42
^d
Found needle in haystack!
Когда будете готовы проверить правильность вашей программы, попробуйте запустить команду указанную ниже.
./generate 1000 50 | ./find 127
Так как один из номеров, выведенных generate, когда в нее было посеено зернышко 50, оказался 127, ваш код должен будет найти эту “иголку”! Для разнообразия попробуйте запустить команду, приведенную ниже.
./generate 1000 50 | ./find 128
Так как 128 нет среди выведенных программой generate чисел, при использовании в качестве зернышка 50, ваш код не должен находить эту иголку. Лучше всего провести еще несколько тестов, запуская generate с разными зернышками, и смотреть на выходные данные, упаковывая их в программе find, в поисках “иголки”, которая, вы знаете, точно будет среди “сена”.
Заметьте, что main в find.c записан таким образом, что find возвращает 0, если иголка найдена, и 1 в противном случае. Вы можете проверить так называемый “код выхода”, который возвращает main, завершая свою работу
echo $?
после того, как запустим кое-какую команду. Предположим вы правильно имплементируете функцию search. Если вы пропишите
./generate 1000 50 | ./find 127
echo $?
то вы увидите 0, потому что 127 есть среди 1,000, выведенных программой generate чисел - эти числа были сгенерированы благодаря зернышку 50. В данном случае функция search должна вернуть true (истину), а функция main должна вернуть 0. Но если вы пропишите
./generate 1000 50 | ./find 128
echo $?
то вы увидите 1, так как 128 нет среди 1,000, выведенных программой generate чисел - эти числа были сгенерированы благодаря зернышку 50 и в данном случае функция search должна вернуть false (ложь), а функция main должна вернуть 1. Улавливаете логику?
check50 cs50/2017/x/find/less
Вас потребуют ввести логин (GitHub username) и пароль (GitHub password) от вашей учетной записи на Github’е, которую вы можете завести, пройдя по данной ссылке https://github.com/join.
Зайдите на сайт cs50.me, используя всё ту же учетную запись GitHub’а и нажмите на зеленую кнопку authorize submit50 (Это действие производится только один раз).
Перед тем как вы имплементируете search в границу времени O(log n), вам лучше написать временный код в O(n) границе, также как и в линейном поиске, потому что так легче реализовать правильный поиск. Таким образом, вы можете перейти к sort, зная, что search точно будет работать, как надо. И как только sort начнет выполняться должным образом, вы сможете вернуться и повторно имплементировать search в O(log n) времени, как с бинарным поиском. Не забудьте это сделать!
Вы можете реализовать код search итеративным подходом (используя цикл) или рекурсивно (где функция будет вызывать саму себя). Если вы выберите последний способ, то знайте, что вам нельзя будет менять нашу имплементацию кода search, но вы можете создать новую, рекурсивную функцию, которую будет вызывать сама search.
Для функции sort вы, скорее всего, захотите имплементировать пузырьковую сортировку, сортировку выбором или сортировку вставками! Просто помните, что нет единого правильного способа реализации любого из этих алгоритмов. Существует огромное количество вариаций. Более того, вы можете улучшать их как пожелаете, до тех пор, пока ваша реализация остается в O(n2). Хоть вы и не можете менять наш код функции sort, вы можете спокойно реализовать свою собственную функцию (функции) в helpers.c, которую (которые) затем сама sort может вызвать.
Мы оставляем вам работу по определению лучшего способа проверки вашей имплементации функций search и sort. Но не забывайте, что у вас есть верный друг eprintf, который поможет вам в вашем дебаггинге! И не забывайте, что вы можете генерировать одинаковую последовательность псевдослучайных чисел опять, опять и опять, указывая зернышко программы generate.