Урок информатики в 10 классе СОРТИРОВКА МАССИВА МЕТОДОМ ОБМЕНА
Муниципальное автономное общеобразовательное учреждение
средняя общеобразовательная школа № 8 г. Белебея
муниципального района Белебеевский район
Республики Башкортостан
Урок информатики в 10 классе
СОРТИРОВКА МАССИВА МЕТОДОМ ОБМЕНА
115824017145000
Тагнер Анастасия Леонидовна,
учитель математики и информатики,
высшая квалификационная категория
Урок информатики в 10 классе
Тема: СОРТИРОВКА МАССИВА МЕТОДОМ ОБМЕНА
Тип урока: комбинированный
Цели урока:
Образовательная:
повторить ключевые знания по теме «Одномерные массивы»; познакомить с сортировкой массива методом обмена; реализовать этот метод с помощью языка программирования; формирование компетентностей интеграции, оценки, поиска и создания информации.
Развивающая:
развивать алгоритмическое мышление, умение применять полученные знания при решении задач различной направленности.
Воспитательная:
воспитывать информационную культуру учащихся, самостоятельность, внимательность.
Задачи урока:
Рассмотреть подробно сортировку массива методом прямого выбора.
Составить программу, выполняющую сортировку массива, реализующую этот метод.
Оборудование:
ПК, интерактивная доска, проектор, программное обеспечение – Windows 7, School Pascal.
Дидактическое обеспечение урока:
видеоматериалы (Ролик 1, Ролик 2, Сортировка методом обмена, задание для самостоятельной работы (Приложение 1), алгоритм сортировки (Приложение 2), листинг основной программы (Приложение 3).
Основные понятия:
алгоритм сортировки методом обмена;
улучшенный алгоритм «пузырьковой» сортировки;
программа на Паскале сортировки методом «пузырька».
Предполагаемый результат урока:
приобретение знаний, умений и навыков по реализации изученного метода сортировки.
Продукт урока:
решение задач на упорядочивание элементов одномерного массива.
План урока
Организационный момент
Актуализация опорных знаний
Сообщение темы и постановка целей урока
Объяснение нового материала
Закрепление изученного материала
Подведение итогов урока
Этапы урока Деятельность учителя Деятельность учащихся
Организационный момент Приветствие обучающихся. Проверка готовности к уроку.
Здравствуйте, ребята! Я рада видеть вас на уроке информатики! Приветствие учителя.
Актуализация опорных знаний И начнем мы урок с просмотра видеоролика. Ученики просматривают видеофрагмент «Ролик 1».
Вы, наверное, удивлены, каким образом связаны фигурное катание и информатика? Посмотрите внимательно на данный кадр? Что напоминают вам оценки судей за каждое выступление? Числовой массив, состоящий из 5 элементов.
Дайте определение массива. Массив – это структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип.
Какую задачу решил программист, обработав полученные оценки? Нахождение среднего арифметического элементов каждого из двух массивов и суммирование полученных результатов.
Программу для решения данной задачи написал программист, который знает 5 основных действий с массивом. Перечислите их. Ввод массива.
Вывод массива
Поиск в массиве
Обработка массива
Сортировка массива
Проверим ваши знания, выполнив самостоятельную работу. Обучающиеся выполняют на местах проверочную работу по карточкам (см. Приложение 1)
Знания какого школьного предмета помогли вам без особых усилий выполнить 7-е задание? Предмета «Математика»
Сообщение темы и постановка целей урока Сегодня мы рассмотрим одно из наиболее важных действий над массивами - сортировку. Какие задачи необходимо решить в течение урока? - Изучить понятие сортировка;
- Познакомиться с методами сортировки;
- Составить программу на языке Pascal, реализующую сортировку одномерного массива.
Объяснение нового материала - Сортировкой называется распределение элементов массива в соответствии с определенными правилами.
Например, сортировка файла, содержащего фамилии, в алфавитном порядке.
-Как можно отсортировать массив?
-Вы когда-нибудь задумывались почему, например, слова в словаре расположены по алфавиту? Обучающиеся записывают определение в тетрадь.
По возрастанию или убыванию.
Сортировка главным образом нужна, для того чтобы ускорить поиск.
Методы сортировки:
- Существует множество различных способов сортировки, которые значительно отличаются друг от друга по скорости работы.
- «Быстрые» способы сортировки могут дать колоссальный выигрыш на больших массивах, содержащих тысячи элементов, однако для небольших массивов можно использовать самые простые способы сортировки. Например, сортировку обменом. По необходимости учитель может остановить показ, обращая внимание учеников на основные понятия и особенности реализации алгоритма сортировки. Ученики просматривают видеофрагмент «Сортировка методом обмена».
Этот метод также называют методом «пузырька». Название это происходит от образной интерпретации, при которой в процессе выполнения сортировки более «легкие» элементы (элементы с заданным свойством) мало-помалу всплывают на «поверхность». Учащиеся знакомятся с алгоритмом сортировки (см. Приложение 2)
Составим алгоритм таким образом, чтобы он заканчивал свою работу в случае, когда на очередном проходе не произошло ни одного обмена (это означает, что массив уже отсортирован и дальнейшие проходы не нужны).
- Для экономии времени возьмем заготовку основной программы из материалов прошлого урока.
Учитель на доске начинает писать программу. Ученики работают в листингах
Разберем внутренний цикл перестановки, удобнее использовать цикл с параметром, параметром, которого будет i, принимающее значение количества пар элементов.
- Как вы думаете, сколько будет пар в массиве размерности 6, 10, n?
- Тем самым в цикле будем сравнивать a[i] элемент и последующий a[i+1]. 5, 9, n-1.
Какое условие нужно записать в ветвлении для сравнения? a[i] > a[i + 1]
Если a[i] больше, то его меняем местами с a[i+1]. Для перестановки нам так же понадобится вспомогательная переменная P. Как запишется наша перестановка? p:= a[i];
a[i]:= a[i + 1];
a[i + 1]:= p;
Во вложенном цикле For должны подсчитать количество перестановок.
Как вы думаете, как можно подсчитать количество k? k:=k+1;
Итак, мы получили внутренний цикл перестановок.
For i:= 1 To n-1 Do
If a[i] > a[i + 1] Then
Begin
p:= a[i];
a[i]:= a[i + 1];
a[i + 1]:= p;
k:=k + 1;
End;
Во внешнем цикле repeat, отвечающем за проходы по массиву пропишем условие завершения цикла until k=0, где k – количество перестановок.
При каждом новом проходе мы должны этот счетчик обнулять. Учащиеся дополняю программу в листинге.
Если же при каком-нибудь очередном проходе цикла repeat, k останется равно нулю, то цикл завершится. В итоге наша запись в Паскале примет такой вид:
Repeat
k:=0;
For i:= 1 To n-1 Do
If a[i] > a[i + 1] Then
Begin
p:= a[i];
a[i]:= a[i + 1];
a[i + 1]:= p;
k:=k + 1;
End
Until k=0; Закрепление изученного материала Реализуем данный алгоритм за компьютерами. Учащиеся работают за компьютерами.
Подведение итогов урока - Сегодня мы научились реализовывать один из алгоритмов сортировки, чтобы в дальнейшем в случае необходимости не тратить время на его отладку, т.к. часто сортировка используется как первый шаг в алгоритме решения более сложной задачи. Вернемся к фигурному катанию. Просмотр видеоролика «Ролик 2»
По итогам все выступлений составляется итоговая таблица. И вновь не без участия компьютера. Какую задачу решил компьютер? Упорядочил полученные итоговые суммы всех выступлений по убыванию.
Постановка домашнего задания Ваша задача дома, составить программу сортировки массива методом обмена по убыванию, используя два цикла с параметром.
- Есть ли у вас вопросы по данной теме? Какие ситуации вам нужно прояснить? Список учебной и дополнительной литературы
Андреева Е.В. Программирование – это так просто, программирование – это так сложно. Современный учебник программирования. – М.: МЦНМО, 2009.
Златопольский Д.М. Программирование: типовые задачи, алгоритмы, методы. Москва, БИНОМ. Лаборатория знаний,2007.
Окулов С.М. Основы программирования. Москва, БИНОМ. Лаборатория знаний, 2010.
Приложение 1
Самостоятельная работа
вариант
Необходимо ответить на вопросы, связанные с массивом Х.
Х 1 2 3 4 5 6 7 8 9
-6 5 -3 5 9 7 3
имя массива _________________________________________________
номера четных элементов массива ______________________________
x[3]:=x[1]+x[8].
х[7]=sqrt(x[6]).
имена нечетных элементов _____________________________________
сумма нечетных элементов массива _____________________________
Расположите элементы массива в порядке убывания.
P 1 2 3 4 5 6 7 8 9
Самостоятельная работа
вариант
Необходимо ответить на вопросы, связанные с массивом Р:
P 1 2 3 4 5 6 7 8 9
-4 9 -3 4 4 2 6
имя массива _________________________________________________
номера нечетных элементов массива _____________________________
p[3]:=p[4]+p[9].
p[7]=sqrt(p[5]).
имена четных элементов _____________________________________
сумма четных элементов массива _______________________________
Расположите элементы массива в порядке возрастания.
P 1 2 3 4 5 6 7 8 9
Приложение 2
Алгоритм «пузырьковой» сортировки
Массив просматривается от первого элемента до последнего. Если очередной элемент больше предыдущего, то они меняются местами. В результате на последнем месте массива оказывается наибольший элемент.
Массив просматривается от первого элемента до предпоследнего. Если очередной элемент больше предыдущего, то они меняются местами. В результате на предпоследнем месте массива оказывается второй по величине элемент.
Далее повторяются аналогичные действия – просмотр массива от первого элемента, обмен элементов, если предыдущий элемент больше следующего, с каждым разом поиск всё дальше не доходит до конца массива. Чем больше элемент массива, тем ближе к концу массива он окажется.
Приложение 3
program sort;
uses crt;
const n=10;
var a: array [1..n] of integer;
i,k,p: integer;
BEGIN
clrscr;
randomize;
{Заполнение массива случайными двузначными числами}
for i:=1 to n do
a[i]:=10+random(90);
{Вывод массива на экран}
for i:=1 to n do
write (a[i]:4);
writeln;
{Сортировка массива в порядке возрастания}
repeat k:=0;
for i:=1 to n-1 do
if a[i]>a[i+1] then
begin p:=a[i];
a[i]:=a[i+1];
a[i+1]:=p;
k:=k+1;
end until k=0;
{Вывод на экран отсортированного массива}
writeln('Массив в порядке возрастания');
for i:=1 to n do
write(a[i]:4);
readln;
END.
Программа сортировки одномерного массива методом обмена
program sort;
uses crt;
const n=10;
var a: array [1..n] of integer;
i,k,p: integer;
BEGIN
clrscr;
randomize;
{Заполнение массива случайными двузначными числами}
for i:=1 to n do
a[i]:=10+random(90);
{Вывод массива на экран}
for i:=1 to n do
write (a[i]:4);
writeln;
{Сортировка массива в порядке возрастания}
{Вывод на экран отсортированного массива}
writeln('Массив в порядке возрастания');
for i:=1 to n do
write(a[i]:4);
readln;
END.