Цели урока:
- Образовательная: формирование у учащихся навыков составления алгоритмов сортировки массива методом прямого выбора и методом отбора; повторение алгоритмов ввода массива с клавиатуры и с помощью оператора случайных чисел; повторение строковых переменных.
- Развивающая: Развитие алгоритмического мышления; умения применять полученные знания при решении задач различной направленности.
- Воспитательная: привитие учащимся навыков самостоятельности в работе; воспитание чувства коллективизма, ответственности.
Тип урока: комбинированный урок.
Вид урока: урок-практикум.
Методы обучения: наглядный, объяснительно-иллюстративный, практический, частично-поисковый.
Формы обучения: коллективная, групповая.
Технология: личностно-ориентированная.
Оборудование:
- компьютеры,
- проектор,
- программное обеспечение – презентация по теме “Методы сортировки массивов”, Windows XP, Qbasic.
Ход урока
I. Сообщение темы и постановка целей урока.
II. Актуализация опорных знаний учащихся.
Устный опрос:
Один учащийся отвечает устно, другой записывает на доске.
- Как описать числовой массив в программе?
- Как описать массив строковых переменных в программе?
- Как определить первый символ в строковой переменной?
- Как осуществить ввод массива с клавиатуры?
- Как осуществить ввод массива с помощью оператора случайных чисел?
- Как установить графический режим в QBasic? Каковы при этом будут размеры и координаты экрана?
- С помощью какой команды рисуется закрашенный прямоугольник?
III. Ознакомление с новым материалом.
Ознакомление с новым материалом ведется с использованием презентации и проектора.
Слайд 1: Сортировка
Сортировка – один из наиболее распространенных процессов обработки данных.
Сортировкой числового массива называют расположение его элементов в возрастающем или убывающем по величине порядке. Сортировка символьного массива заключается в расположении элементов, например, по алфавиту или по длине строк. Сортировка массивов включена в качестве стандартной операции во многие системы прикладного обеспечения (MS Word, MS Excel и др).
Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием.
Существует достаточно много методов (алгоритмов) сортировки массивов. Мы рассмотрим два из них: метод прямого выбора и метод обмена (метод “пузырька”)
Слайды 1-2: Метод прямого выбора.
Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:
- Просматривая массив с первого элемента, найти минимальный и поменять его местами с первым элементом.
- Просматривая массив со второго элемента, найти минимальный и поменять его местами со вторым элементом.
- И, так далее, до последнего элемента.
Пример работы алгоритма:
| Исходный массив: | 8, 3, 6, 1, 4 (последовательно меняются местами 8 и 3, 3 и 1) |
| После первого шага: | 1, 3, 8, 6, 4 (последовательно меняются местами 8 и 6, 6 и 3) |
| После второго шага: | 1, 3, 6, 8, 4 (меняются местами 6 и 4) |
| После третьего шага: | 1, 3, 4, 8, 6 (меняются местами 8 и 6) |
| После четвертого шага: | 1, 3, 4, 6, 8 |
Алгоритм использует вложенные циклы. Внешний цикл (счетчик шагов) последовательно выбирает номер элемента массива, куда следует записывать найденный в неупорядоченной части массива минимальный элемент. Внутренний цикл перебирает номера неупорядоченных элементов при поиске минимального элемента. Для внешнего цикла достаточно шагов на один меньше, чем элементов в массиве.
Слайды 3-4: Метод обмена.
В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут), поэтому этот метод иногда называют методом “пузырька”. Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.
Пример работы алгоритма:
| Исходный массив: | 8, 3, 6, 1, 4 (последовательно меняются местами 8 и 3, 6 и 1, 6 и 4) |
| После первого шага: | 3, 8, 1, 4, 6 (последовательно меняются местами 8 и 1, 8 и 4, 8 и 6) |
| После второго шага: | 3, 1, 4, 6, 8 (последовательно меняются местами 3 и 1) |
| После третьего шага: | 1, 3, 4, 6, 8 |
| После четвертого шага: | 1, 3, 4, 6, 8 |
| После пятого шага: | 1, 3, 4, 6, 8 |
IV. Закрепление нового материала.
Слайд 5: Задача
Составить программу сортировки массива по возрастанию методом обмена. Массив задать случайными числами.
Фрагмент программы, реализующий сортировку массива по возрастанию методом прямого выбора.
For i=1 To n-1
For j=i+1 To n
If a(i)>a(j) Then Swap a(i), a(j)
Next j
Next i
Для проверки решений учащимся демонстрируется заранее приготовленная программа.
Вопрос: Что нужно изменить в программе, чтобы выполнялась сортировка массива по убыванию?
V. Самостоятельная работа учащихся за компьютером.
Учащиеся разбиваются на разноуровневые группы по два человека. Учащимся предлагаются задания трех уровней сложности.
Уровень 1.
Задача 1. Составить программу сортировки числового массива по возрастанию методом отбора. Массив задать случайными числами.
Уровень 2.
Задача 2. Составить программу сортировки списка фамилий учеников по алфавиту методом отбора. Фамилии учеников вводить с клавиатуры.
Уровень 3.
Задача 3. Составить программу сортировки массива по возрастанию методом отбора.
Массив представить в виде прямоугольников разной высоты. Массив значений высот прямоугольников задать с помощью функции RND.
VI .Проверка работ учащихся.
Для проверки решений учащимся демонстрируются заранее приготовленные программы.
VII. Подведение итогов урока.
Подводятся итоги урока, выставляются оценки.
VIII. Домашнее задание.
Даются пояснения к выполнению домашнего задания.
Уровень 1.
Задача 4. На соревнованиях по прыжкам в длину получен массив b(n). Определить три лучших результата. Массив сформировать с помощью функции RND.
Уровень 2.
Задача 5. Составить программу, которая выполняет перестановку букв в исходном слове по алфавиту.
Уровень 3.
Задача 6 . Составить программу, которая в исходном предложении меняет местами слова так, чтобы они были расположены по алфавиту (рассматриваются первые буквы слов). В конце исходного предложения стоит точка.
Приложение 1. Решение задач самостоятельной работы
Задача 1.
REM Сортировка массива методом "пузырька"
CLS
RANDOMIZE TIMER
INPUT "введите размерность массива: "; n
DIM a(n) AS INTEGER
' Заполнение массива
PRINT "Исходный массив:"
FOR i = 1 TO n
a(i) = INT(RND * 50 – 25)
PRINT a(i);
NEXT i
' Сортировка
FOR i = 1 TO n
FOR j = 1 TO n – 1
IF a(j) > a(j + 1) THEN SWAP a(j), a(j + 1)
NEXT j
NEXT i
' Вывод массива
PRINT "Упорядоченный массив:"
FOR i = 1 TO n
PRINT a(i);
NEXT i
END
Задача 2.
REM Сортировка методом "пузырька"
CLS
INPUT "Введите количество фамилий в списке: "; n
DIM a(n) AS STRING
' Ввод фамилий
PRINT "Введите фамилии"
FOR i = 1 TO n
PRINT i; ". ";
INPUT a(i)
NEXT i
' Сортировка
FOR i = 1 TO n
FOR j = 1 TO n – 1
IF MID$(a(j), 1, 1) > MID$(a(j + 1), 1, 1) THEN SWAP a(j), a(j + 1)
NEXT j
NEXT i
' Вывод упорядоченного списка
PRINT "Упорядоченный список: "
FOR i = 1 TO n
PRINT a(i)
NEXT i
END
Задача 3.
REM Сортировка методом "пузырька"
SCREEN 9
RANDOMIZE TIMER
INPUT "Введите размерность массива: "; n
DIM a(n) AS INTEGER
' Исходный массив
x = 5
y = 150
PRINT "Исходный массив: "
FOR i = 1 TO n
a(i) = INT(RND * 100)
LINE (x + 20 * i, y)-(x + 20 * i + 10, y – a(i)), 2, BF
NEXT i
' Сортировка
FOR i = 1 TO n
FOR j = i + 1 TO n
IF a(i) > a(j) THEN SWAP a(i), a(j)
NEXT j
NEXT i
' Вывод упорядоченного массива
y = 300
LOCATE 13, 1: PRINT "Упорядоченный массив: "
FOR i = 1 TO n
LINE (x + 20 * i, y)-(x + 20 * i + 10, y – a(i)), 2, BF
NEXT i
END
Приложение 2. Решение задач домашней работы.
Примечание: Презентацию урока можно получить у автора.