Методическая информация
Тип урока: комбинированный – изучение нового материала, закрепление, выполнение практической работы.
Цели и задачи:
- Образовательные
Время реализации урока: 2х45 мин
Предполагаемый результат урока: приобретение знаний, умений и навыков по реализации изученных методов сортировок.
Продукт урока: решение задач на упорядочивание элементов одномерного массива.
Оборудование: ПК, интерактивная доска, проектор.
Дидактическое обеспечение урока: видеоматериалы (Приложение 1, Приложение 2, флеш-ролики (Приложение 3, Приложение 4, Приложение 5), задание для практической работы.
Основные понятия:
- алгоритм сортировки методом выбора;
- алгоритм сортировки методом «пузырька»;
- улучшенный алгоритм «пузырьковой» сортировки;
- программа на Паскале сортировки методом выбора;
- программа на Паскале сортировки методом «пузырька».
Особенности изложения содержания урока:
Это один из заключительных уроков изучения темы «Программирование» в 9 классе. Учащиеся изучили алгоритмы заполнения одномерного массива, поиска числа в массиве; научились составлять программу на Паскале по данному алгоритму. Знания, умения и навыки, приобретенные на этом уроке, понадобятся в дальнейшем при изучении модуля «Программирование» в 11 классе.
Урок проводится на основании знаний, полученных по модулю «Программное управление работой компьютера» (Глава 6) и материала для углубленного изучения курса п.6.3 [1].
Ход урока
1. Организационный момент
Приветствие и проверка готовности учащихся к уроку.
2. Мотивация учащихся
На предыдущих занятиях мы с вами изучили основные алгоритмические конструкции, научились писать достаточно сложные программы.
Сегодня на уроке научимся упорядочивать элементы числовых массивов.
Зачем нужна сортировка? С отсортированными данными работать легче, чем с произвольно расположенными:
- когда элементы отсортированы, их проще найти;
- на отсортированных данных легче определить, имеются ли пропущенные элементы;
- проще удостовериться, что все элементы были проверены;
- легче найти общие элементы двух множеств.
Сортировка является мощным средством ускорения работы практически любого алгоритма, в котором нужно часто обращаться к определенным элементам данных. Если хотите стать хорошими программистами, то обязательно должны знать различные методы сортировки[3].
Далее урок ведется с использованием приложенного видеоматериала, учитель рассказывает, по необходимости останавливает показ, обращая внимание учеников на основные понятия (приведенные выше), ученики самостоятельно составляют конспект.
3. Изучение алгоритмов сортировки
3.1. Сортировка выбором
Задача сортировки массива – это перестановка элементов массива так, чтобы они были упорядочены по возрастанию, убыванию или другой аналогичной характеристике.
3.1.1. Алгоритм сортировки прямым выбором по убыванию
Далее просматриваем видеоматериал (Приложение 1). По необходимости учитель может остановить показ, обращая внимание учеников на основные понятия и особенности реализации алгоритма сортировки.
Рассмотрим алгоритм сортировки выбором. Суть ее в случае упорядочивания по убыванию заключается в следующем. Будем просматривать массив слева направо. Найдем максимальный элемент в массиве и поменяем его с первым элементом. Затем найдем максимальный элемент среди оставшихся элементов и поменяем его со вторым элементом. На N-1 шаге мы закончим упорядочивание нашего массива, состоящего из N элементов [2].
3.1.2. Алгоритм сортировки прямым выбором по возрастанию
Используя флеш-ролик (Приложение 3), выполним алгоритм сортировки выбором. Ученик у доски выполняет упорядочивание элементов массива по возрастанию, используя алгоритм сортировки прямым выбором.
Далее сформулируем особенности программирования сортировки выбором. Структура алгоритма должна представлять собой два вложенных цикла. Внешний цикл – проходы по массиву, внутренний цикл – поиск необходимого элемента и обмен элементов массива.
3.2. Сортировка обменом или «пузырьковая» сортировка
«Пузырьковая» сортировка традиционно считается более простой в реализации [2].
3.2.1. Алгоритм сортировки обменом или «пузырьковая» сортировка по возрастанию
Просматриваем видеоматериал (Приложение 2). По необходимости учитель может остановить показ, обращая внимание учеников на основные понятия и особенности реализации алгоритма сортировки обменом или «пузырьковой» сортировки.
Суть упорядочивания по возрастанию заключается в следующем. Просматриваем слева направо все пары соседних элементов. Если при этом рассматриваемый элемент массива больше следующего, то элементы меняем местами. В результате такого просмотра массива максимальный элемент окажется на крайнем справа (своём) месте. Будем просматривать массив снова, исключив из рассмотрения правый элемент. На своем месте теперь окажется уже второй по величине элемент. В последнем просмотре будут участвовать только первый и второй элементы. Общее число просмотров массива из N элементов при этом равно N-1 [2].
3.2.2. «Пузырьковая» сортировка по убыванию
Используя флеш-ролик (Приложение 4), выполним алгоритм сортировки обменом. Ученик у доски выполняет упорядочивание элементов массива по убыванию, используя алгоритм сортировки обменом.
Далее формулируем особенности программирования сортировки обменом. Структура алгоритма должна представлять собой два вложенных цикла. Внешний цикл – проходы по массиву, внутренний цикл – сравнение пар элементов и обмен, если это необходимо.
3.2.3. Усовершенствованная «пузырьковая» сортировка
При просмотре видеоматериала (Приложение 2) обращаем внимание учеников на то, что «пузырьковую» сортировку можно усовершенствовать.
Используя флеш-ролик (Приложение 5), выполним алгоритм «пузырьковой» сортировки. Сформулируем, как надо изменить алгоритм, чтобы он заканчивал свою работу в случае, когда на очередном проходе не произошло ни одного обмена (это означает, что массив уже отсортирован и дальнейшие проходы не нужны) [2].
4. Рефлексия деятельности на уроке
Рассмотрели наиболее простые алгоритмы сортировки:
- сортировка выбором;
- сортировка обменом или «пузырьковая» сортировка;
- усовершенствованная «пузырьковая» сортировка.
Теперь необходимо научиться реализовывать один из алгоритмов сортировки, чтобы в дальнейшем в случае необходимости не тратить время на его отладку, т.к. часто сортировка используется как первый шаг в алгоритме решения более сложной задачи [2].
5. Практическая работа
Используя один из изученных алгоритмов сортировки, составить программы на Паскале.
1. Выполнить сортировку только четных элементов массива (нечетные элементы остаются на своих местах)
Примерный вариант решения задачи:
2. Выполнить сортировку элементов, записанных на нечетных местах [4].
Примерный вариант решения задачи:
Для помощи в составлении и отладке программ ученик может самостоятельно за своим рабочим местом просмотреть видеоматериалы и флеш-приложения еще раз.
6. Домашнее задание
Придумать пример задачи из реальной жизни, для решения которой необходимо использовать сортировку.
7. Итоги урока
Выделить тех учеников, кто выполнил все задания, особенно подчеркнуть то, что у всех есть возможность дома доработать программы; при выходе из кабинета попросить ребят оставить на партах одну из трех заготовленных ранее карточек: красная – урок был трудным, у меня мало что получилось; желтая – урок был в целом понятен, но дома мне предстоит потрудиться, чтобы доделать работу; зеленая – урок был понятным и интересным, я почти все сделал в классе.
Список учебной и дополнительной литературы
- Семакин И.Г.