Практическая работа № 16 "Сортировка массивов методом «вставки»"

Информатика 9 класс

Дата - ________________

Урок № 30

Практическая работа № 16 "Сортировка массивов методом «вставки»"

Цели урока:

Образовательная: формирование у учащихся навыков составления алгоритмов сортировки массива методом обмена; ввода массива с клавиатуры, с помощью генератора случайных чисел и с помощью объявления значений массива в разделе описания констант; повторение строковых переменных.

Развивающая: развитие алгоритмического мышления; умения применять полученные знания при решении задач различной направленности.

Воспитательная: привитие учащимся навыков самостоятельности в работе.

Тип урока: комбинированный урок.

Методы обучения: наглядный, объяснительно-иллюстративный, практический, частично-поисковый.

Оборудование: компьютеры, программное обеспечение – Windows, среда программирования PascalABС для написания программы на языке Паскаль.

Ход урока

1. Организационный момент.

Сообщение темы и постановка целей урока.

1. Актуализация опорных знаний и умений учащихся.

Устный опрос:
Как описать числовой массив в программе?

Как описать массив строковых переменных в программе?

Как задаётся массив в разделе описания констант?

Как осуществить ввод массива с клавиатуры?

Как осуществить ввод массива с помощью генератора случайных чисел?

1. Ознакомление с пройденным материалом.

Рассмотрим процесс упорядочивания элементов массива по возрастанию в игровой форме.

Один учащийся заполняет таблицу следующего вида на доске.

Пять учащихся выстраиваются в линию, им раздаются карточки с цифрами: 5, 2, 4, 6, 1, 3 (они будут представлять собой элементы массива). По ходу объяснения учащиеся демонстрируют, как происходит перестановка элементов в массиве, и каждый просмотр фиксируется на доске. В результате, заполненная таблица должна выглядеть следующим образом.

В рабочие тетради учащиеся зарисовывают полученную таблицу и записывают описание метода «вставки».

При методе «вставки» сравнивается 1-ый элемент со 2-ым. Если 1-ый окажется больше 2-го, то их поменяем местами. Те же действия выполним для 2-го и 3-го, 3-го и 4-го,…, (n-1)-го и n-го элементов. В результате этих действий самый большой элемент станет на последнее (n-е) место.

Физкультминутка.

1. Закрепление повторного материала.

Работа с карточками.

Учащимся раздаются карточки, которые они должны заполнить.

1 вариант

Выполнить сортировку массива методом пузырька.

2 вариант

Выполнить сортировку массива методом пузырька

3 вариант

Выполнить сортировку массива методом пузырька

4 вариант

Выполнить сортировку массива методом пузырька

ОТВЕТЫ

1 вариант

2 вариант

3 вариант

4 вариант

Задача

Составить программу сортировки массива из N элементов по возрастанию методом вставки. Массив задать случайными числами из диапазона [0-25], N взять равным 10. Вывести на экран исходный и отсортированный массивы.

Примерный код программы.

program InsertionSort;

var a: array [1..1000] of integer;

n, t, i, j: integer;

begin

readln(n);

for i := 1 to n do {цикл, вводим элементы, заодно и сортируем}

begin

read(a[i]); {вводим}

t := a[i]; {запоминаем в буфере}

j := i - 1; {первая позиция для вставки}

while (j = 1) and (a[j] t) do {пока есть куда вставить и условие для вставки выполняется}

begin

a[j + 1] := a[j]; {перемещаем очередной элемент}

j := j - 1 {сдвигаем позицию для вставки}

end;

a[j + 1] := t {вставляем}

end;

for i := 1 to n do write(a[i], ' ') {печатаем результат}

end.

Вопрос: Что нужно изменить в программе, чтобы выполнялась сортировка массива по убыванию?

Самостоятельная работа учащихся за компьютером. Учащимся предлагаются задания трех уровней сложности.

Уровень 1.

На соревнованиях по прыжкам в длину получен массив b(n). Определить три лучших результата. Массив сформировать с помощью генератора случайных чисел.

Уровень 2.

Заданы два массива одинаковой размерности (строковый и числовой). Элементы строкового массива представляют собой фамилии учащихся (задаётся в разделе описания констант), а числовой массив представляет собой баллы полученные на ЕГЭ (генератор случайных чисел – диапазон [1-100]). Между элементами 2-х массивов однозначное соответствие: фамилии 1-го элемента из строкового массива соответствуют баллы 1-го элемента числового и т.д. Вывести исходные массивы в виде: Фамилия – баллы, а затем массивы отсортированные по убыванию полученных баллов.

Уровень 3.

Решить задачу (Уровень 2), оптимизировав её таким образом, что если после очередного прохода по числовому массиву ни разу не произошла перестановка элементов, это значит, что массив уже отсортирован и можно завершать выполнение программы.

1. Проверка работ учащихся. Подведение итогов урока, выставление оценок.

2. Домашнее задание.

Повторить материал по конспекту и алгоритмы сортировки данных стр.126-129 учебник Семакин И.Г. 9 класс.