Методическая разработка Практического занятия по теме «Массивы» ОП.05 «Основы программирования»

Министерство образования Саратовской области

Государственное автономное профессиональное образовательное учреждение Саратовской области

«Поволжский колледж технологий и менеджмента»

Методическая разработка

Практическое занятие по теме «Массивы»

дисциплины ОП.05 «Основы программирования»

Разработал: преподаватель Кузнецова Т.П. _______________

2016г.

Рецензенты:

1. ________________/_______________/

2. ________________/_______________/

Практическое занятие

Дисциплины: Основы программирования

Тема: Тема 2.3. Массивы

Наименование работы: Сортировка массивов

Цель работы: Приобретение практических навыков при составлении программ, включающих обработку массивов. Отладка программ на ПК

Приобретаемые умение и навыки: формирование умений и навыков применения знаний языка Pascal при решении конкретных задач

Техника безопасности: правила техники безопасности при работе на персональном компьютере

Литература:

• Семакин И.Г., Шестаков А.П. Основы алгоритмизации и программирования. – М: ОИЦ «Академия». 2013. - 304 с.

• Семакин И.Г., Шестаков А.П. Основы алгоритмизации и программирования. Практикум. – М: ОИЦ «Академия». 2013. - 144 с.

Время работы: 2 часа

Средства обучения: Компьютерные столы и персональные компьютеры, компьютер преподавателя, мультимедийный проектор, экран

Краткое пояснение: Часто необходимо внутри одного цикла проводить ещѐ

один цикл вычислений или включать условные операторы или операторы выбора для организации разветвления алгоритма. Такие программы относятся уже к программам усложненной структуры.

Вопросы для самопроверки:

1. Опишите алгоритм нахождения минимального элемента массива.

2. Опишите алгоритм нахождения максимального элемента массива.

3. Опишите алгоритм реверса массива.

4. Опишите алгоритм циклического сдвига элементов массива влево на 1

элемент.

5. Опишите алгоритм циклического сдвига элементов массива вправо на 1

элемент.

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

7. Перечислите, известные вам, методы сортировки?

Методы сортировки

Метод парных перестановок (пузырьковый метод)

Смысл этого метода заключается в сравнивании соседних элементов и, если

нужно, их перестановке. Причѐм за один просмотр всех пар сортировка не достигает нужного результата. Приходится просматривать все пары элементов n-1раз.

Сортировка выбором

Сортировка основана на определении наибольшего (наименьшего) элемен-

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

Метод вставки

Массив разделяется на две части: отсортированную и не отсортированные

элементы из не отсортированной части поочередно выбираются и вставляют-

ся в отсортированную часть так, чтобы не нарушить в ней упорядоченность

элементов. В начале работы алгоритма в качестве отсортированной части

массива принимают только первый элемент, а в качестве не отсортированной

- все остальные элементы. Таким образом, алгоритм будет состоять из (n-1)-го прохода (n - размерность массива), каждый из которых будет включать четыре действия:

• взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;

• поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

• сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;

• вставка взятого элемента в найденную i-ю позицию.

Метод сортировки Шелла

Сначала сравниваются и сортируются между собой значения, отстоящие

один от другого на некотором расстоянии d1=n/2, di=di-1/2, …, dk=1.

Рекомендации по отладке программы:

1. Введите основной код программы в редакторе кода.

2. Запустите программу на выполнение.

3. Если обнаружены синтаксические ошибки, то устраните их и запустите

программу на выполнение еще раз.

4. Если больше ошибок не обнаружено и программа готова к вводу исходных данных, введите необходимые исходные данные.

5. Если нет больше никаких ошибок в ходе выполнения программы, в окне вывода должны появиться выходные данные. Проверьте правильность работы программы на контрольных примерах. Обычно количество контрольных примеров зависит от количества веток-разветвлений

вашей программы.

6. Если результат вывода программы не соответствует расчетным данным

контрольного примера, следовательно, ошибки имеются в самом алгоритме. Проверьте логику алгоритма, исправьте программу и начните с пункта 2.

Дополнительное задание

1. Вставьте в программе дополнительную проверку, чтобы посмотреть,

за сколько проходов будут отсортированы ваши наборы данных.

2. Проведите сравнительный анализ для различных наборов данных и

внесите эти данные в таблицу.

Таблица1 - Число проходов для разных методов сортировок

3. Напишите программы сортировки одномерного массива :

• методом вставки

• методом Шелла.