Пришло время для кое-чего интересного! Обратите внимание, 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.
Итак, вот что нам нужно сделать:
- Реализовать
search. Эта функция должна возвращатьtrue, если значение найдено в «стогу» иfalse, если его там нет. - Реализовать
sort, функцию, сортирующую массив значений.
Изначально поиск реализован как линейный. Но вы можете сделать лучше. Алгоритм линейного поиска выполняется за время О(n). Ваша задача — написать алгоритм бинарного поиска. Время его исполнения — O(log n). Однако его проблема в том, что ему на вход нужно подавать отсортированные данные, иначе он не будет работать. Вы помните пример с разорванной книгой, и, вероятно, знаете, почему так.
Если вы прошлись бинарным поиском по элементам, и их больше не осталось (то есть в этом «стоге» нашей «иголки» попросту нет), нужно, чтобы функция вернула false.
Бинарный поиск можно реализовать итеративно или рекурсивно (о рекурсии Дэвид Малан рассказал в восьмой лекции).