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

1. Что такое сортировка?

2. В чем заключается метод быстрой сортировки?

3. В чем заключается метод сортировки Шелла?

Задания и инструкция по выполнению практической работы

1. Из папки «Рабочие файлы» откройте файлы с именем P13_1.pas, P13_2.pas. В этих файлах содержится заголовок программ, комментарии по выполнению, описание переменных, оператор начала и конца программы, операторы ввода и вывода данных. Вам следует из этой "болванки" составить программы, позволяющие продемонстрировать сортировку разными методами.

2. Решите задачу «Хитрой» сортировки. Из массива путем однократного просмотра выбирается последовательность элементов, расположенных в порядке возрастания, переносится в выходной массив и заменяется во входном на —1. Затем оставшиеся элементы включаются в полученную упорядоченную последовательность методом погружения», когда очередной элемент путем ряда обменов «погружается» до требуемой позиции в уже упорядоченную часть массива.

Порядок выполнения отчета по практической работе

После завершения работы студенты должны представить в отчете оформление задачи 2. В котором следует:

• указать постановку задачи;

• дать описание исходных, результирующих и промежуточных данных;

• показать словесный алгоритм и блок-схему;

• оформить задачу по варианту, указав номер варианта;

• отчет выполняется на листе формата А4 в печатном виде.

Образец отчета по практической работе

Образец отчета к данной практической работе имеет тот же вид, что в практической работе № 1.

Практическая работа № 14 «Методы поиска»

Учебная цель:

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

Учебные задачи:

1. Научиться навыкам и приемам использования массивов, доступа к их элементам и преобразований массивов;

2. Сформировать знания о работе и алгоритмах методов поиска элементов массива.

3. Закрепить практические навыки работы с системой программирования.

Образовательные результаты, заявленные во ФГОС третьего поколения:

Студент должен

уметь:

• формализовать поставленную задачу;

• применять полученные знания к различным предметным областям;

• составлять и оформлять программы на языках программирования;

• тестировать и отлаживать программы.

знать:

• процесс создания программ;

• общие принципы построения и использования языков программирования, их классификацию;

• современные интегрированные среды разработки программ;

• стандарты языков программирования.

Задачи практической работы:

1. Повторить теоретический материал по теме практической работы.

2. Ответить на вопросы для закрепления теоретического материала.

3. Выполнить задания по написанию программ поиска элементов одномерного массива.

4. Оформить отчет.

Обеспеченность занятия и средства обеспечения такая же как в практической работе №5.

Краткие теоретические и учебно-методические материалы по теме практической работы

Поиск - процесс нахождения в заданном множестве объекта, обладающего свойствами или качествами задаваемого априори эталона (или шаблона).

Линейный поиск. Пусть требуется найти элемент X в массиве А. Предполагается, что никакой дополнительной информации ни об этом номере, ни о самом массиве нет. Будем последовательно просматривать элементы массива и сравнивать значения элемента массива А с X.

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

Исходный массив делится пополам и для сравнения выбирается средний элемент. Если он совпадает с искомым, то поиск заканчивается. Если же средний элемент меньше искомого, то все элементы левее его также будут меньше искомого. Следовательно, их можно исключить из дальнейшего поиска, оставив только правую часть массива. Аналогично, если средний элемент больше искомого, то отбрасывается правая часть, а остается левая.

На втором этапе выполняются аналогичные действия над оставшейся половиной массива. В результате после второго этапа остается ¼ часть массива. И так далее, пока или элемент будет найден, или длина зоны поиска станет равной нулю. В последнем случае искомый элемент найден не будет.

Линейный поиск не представляет значительную ценность, и может быть использован только в небольших массивах размером до 100 элементов. Использование линейного поиска в больших массивах ведет к резкому замедлению работы программы.

Двоичный поиск показывает высокую скорость. Достоинство: стабильность работы на любых наборах ключей и независимость времени поиска от наличия или отсутствия ключа в таблице. Недостаток: необходимость сортировки данных по ключам.