В поисках алгоритма. Конспект урока по теме «Сортировка массивов» 9 класс

СМОЛЕНСКОЕ ОБЛАСТНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
«ШКОЛА-ИНТЕРНАТ СРЕДНЕГО (ПОЛНОГО) ОБЩЕГО ОБРАЗОВАНИЯ
С УГЛУБЛЕННЫМ ИЗУЧЕНИЕМ ОТДЕЛЬНЫХ ПРЕДМЕТОВ
ИМЕНИ КИРИЛЛА И МЕФОДИЯ»

Конспект урока информатики и ИКТ

«В поисках алгоритма»

(по теме «Сортировка массивов»)
в 9 классе
физико-математического профиля

подготовила

учитель информатики и ИКТ

Сенчилова Ольга Константиновна

г. Смоленск

2013

Раздел программы: Программное управление работой компьютера.

Тип урока: нетрадиционный урок – урок-путешествие; урок изучения и первичного закрепления новых знаний.

Цель урока: формирование навыков программирования сортировки одномерного массива.

Задачи урока.

Обучающие:

1. учащиеся повторяют и закрепляют основные понятия, связанные с одномерными массивами;

2. изучают алгоритмы сортировки методом обмена и методом выбора;

3. учатся составлять код программы сортировки одномерного массива на языке Паскаль;

4. формируют умение анализировать сложность алгоритма.

Развивающие:

1. у учащихся развивается умение обобщать полученные знания и последовательно их применять в процессе выполнения задания;

2. развивается абстрактное и логическое мышление;

3. формируется умение анализировать, строить аналогии, выделять главное.

Воспитательные:

1. у учащихся формируется коммуникационная культура, умение работать в паре;

2. воспитывается самостоятельность в применении полученных знаний;

3. воспитываются аккуратность, внимательность, вежливость и дисциплинированность.

Оборудование:

• компьютер учителя с проектором и экраном;

• презентация «В поисках алгоритма»;

• компьютеры со средой программирования PascalАВС;

• файлы с заготовками программ;

• карточки с заданиями к практической части урока;

• секундомер.

План урока.

1. Организационный момент. Мотивация (проблемная задача). (1 мин)

2. Обсуждение цели и задач урока. (2 мин.)

3. Актуализация опорных знаний. (2 мин.)

4. Изучение нового материала.

1. Знакомство с алгоритмами сортировки. (8 мин.)

2. Первичная проверка понимания нового материала. (5 мин.)

3. Физкультминутка (1 мин.)

4. Разработка программ сортировки массива. «Вычислительный центр» (12 мин.)

5. Анализ сложности алгоритмов сортировки. «Испытательный стенд» (3 мин.)

6. Решение проблемной задачи (1 мин.)

5. Подведение итогов урока. Рефлексия. Домашнее задание (5 мин.)

Ход урока.

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

<Приветствие>

Предлагаю сегодня отменить обычный урок. Дело в том, что наш класс попросил о помощи ваш, можно сказать, коллега – программист Костя Байтов. Смотрите, какое письмо пришло мне сегодня по электронной почте. <Зачитывается письмо> (Слайд 1)

Ну что, ребята, согласны вы отправиться в офис программиста Кости Байтова и помочь ему решить задачу? (Да) Поскольку для решения любой задачи нужно сначала придумать алгоритм, то тема нашего сегодняшнего урока будет звучать так: «В поисках алгоритма» (Слайд 2).

Готовы к путешествию? Тогда в путь!

2. Обсуждение цели и задач урока.

Итак, мы в офисе. Нас встречает Костя. (Слайд 3).

(Костя: «Здравствуйте, братцы! Очень рад, что вы пришли на помощь. Задачу помните?».)

<Учащиеся вспоминают условие задачи: выстроить по убыванию баллы, полученные в результате анонимного тестирования.>

(Костя: «В компьютере сохранен фрагмент программы, который я успел написать. Вы тут осваивайтесь, а я побегу, очень много работы».)

(Слайд 4)

Посмотрите, какие части в программе готовы? (Задание элементов массива, вывод его на экран)

Какая задача стоит перед нами? В чем ее суть? (Упорядочить элементы массива по убыванию)

Как называется упорядочение элементов по возрастанию или убыванию? (Сортировка)

То есть наша цель – научиться программировать сортировку массива. Что мы должны сделать для достижения цели? <Учащиеся помогают формулировать задачи урока. Цель и задачи записываются и остаются на доске>.

1. Узнать метод (методы) сортировки массива.

2. Научиться программировать сортировку массива.

3. Испытать (проверить) получившуюся программу.

3. Актуализация знаний учащихся.

Нам предстоит работать с массивом. Проверим, готовы ли мы к такой работе. Запустим на Костином компьютере тест. Вы будете записывать ответы на доске, а я – вносить их в компьютер.

(Слайды 5-7)<Учитель вызывает учащихся для записи требуемых фрагментов программного кода. Записи остаются на доске.>

Задания (актуализация опорных знаний).

1. Как обменять значения двух переменных a и b с помощью третьей переменной c?

Ответ: c:=a;

a:=b;

b:=c;

2. Какую алгоритмическую структуру используют для обработки массивов? (цикл)

3. Массив задан следующим образом:

Const N=10;

Var m : array[1..N] of integer;

Найти значение максимального элемента и поместить его в переменную max.

Ответ: max:=m[1];

for i:=2 to N do

if m[i]>max then max:=m[i];

(Слайд 8) Тест пройден. Мы готовы к работе!

4. Изучение нового материала.

а) Знакомство с алгоритмами сортировки.

(Слайд 9; верхний ? – переход к слайду 10, нижний ? – переход к слайду 11)

Давайте пройдем в конференц-зал, сядем поудобнее и устроим «мозговой штурм». Есть ли у вас идеи, как осуществить сортировку массива?

<Обсуждаются идеи, выдвинутые учащимися. Если в ходе обсуждения учащимися был сформулирован алгоритм сортировки методом выбора или методом обмена, учитель подтверждает их догадку, открывая слайд с соответствующим алгоритмом и называя его. В случае затруднений (если один или оба алгоритма не были озвучены) учитель предлагает: обратиться к справочной литературе и узнать о простых методах сортировки, а затем открывает соответствующие слайды.>

Метод обмена (Слайд 10)

Алгоритм состоит из повторяющихся проходов по массиву.

За каждый проход поочередно сравниваем каждые два соседних элемента и, если они расположены не по убыванию, меняем их местами.

После первого прохода на последнем (N-ом) месте в массиве будет стоять наименьший элемент.

Второй проход обменов выполняется до N-1-го элемента (т.к. N-ый – уже на своем месте), третий – до N-2-го, и так далее.

Всего потребуется N-1 проход.

Другое название метода – метод пузырька. В результате прохода минимальное значение «всплывает» в конец массива, как воздушный пузырек всплывает на поверхность, подталкиваемый архимедовой силой.

Метод выбора (Слайд 11)

Максимальный элемент и первый меняются местами. Первый элемент занял свое место.

В неотсортированной части массива снова выбирается максимальный элемент; он меняется местами с первым из неотсортированных элементов массива.

Повторяем, пока в неотсортированной части не останется один элемент.

Всего потребуется N-1 поиск максимального элемента.

б) Первичная проверка понимания нового материала.

Давайте выполним эти алгоритмы, чтобы лучше понять их работу.

(Слайд 12)

<Имитационная игра «Сортировка массива».

В классе выбрать 5 учеников разного роста. Построить их в ряд. Пригласить еще одного ученика, который будет выполнять алгоритм сортировки методом обмена для того, чтобы расположить детей в этом ряду по росту. (Поочередно сравниваем рост стоящих рядом учеников, и меняем их местами, если это необходимо). (Слайд 13) Игра повторяется для сортировки методом выбора.>

(Слайд 14)

Конечно, методы сортировки массивов не исчерпываются методом обмена и методом выбора. Есть множество более сложных алгоритмов, разработанных для эффективной сортировки больших массивов. Но мы с вами только начали изучать программирование, поэтому пока остановимся на этих двух методах.

Прежде, чем перейти к решению Костиной задачи, предлагаю сначала составить программы на основе этих алгоритмов и испытать их. Нам потребуется несколько компьютеров, поэтому давайте пройдем в вычислительный центр, а чтобы лучше подготовиться к работе, по дороге проведем физкультминутку.

в) Физкультминутка. (Слайд 15)

г) Разработка программ сортировки массивов.

Мы в вычислительном центре. (Слайд 16) Предлагаю поработать в парах. Пары за нечетными компьютерами составляют программу сортировки массива обменом, пары за четными компьютерами – методом выбора. В помощь вам я успела приготовить карточки с блок-схемами соответствующих алгоритмов и заготовки программ.

<Файлы для работы: 9А_obmen.pas, 9A_vybor.pas – в общей папке на компьютерах.

Карточки «Алгоритмы сортировки массивов».

Листы с заданием «Разработка программ сортировки» дублируют набранный в файлах текст заготовок программ.

Первые результаты демонстрируются по сети на большом экране для обсуждения, возможной доработки и записи в тетрадь. Образцы программ открываются по ссылкам (Слайд 17,18).>

д) Анализ сложности алгоритмов сортировки.

Какой же из двух вариантов программного кода мы предложим Косте?

Оценивая программы, в первую очередь обращают внимание на скорость их работы и требуемые для них ресурсы. Давайте оценим скорость работы наших программ. (Слайд 19)

<В тексте программ исправить строку Const N=10; на Const N=10000; одновременно запустить программы с разными методами сортировки и с помощью секундомера засечь время их выполнения.>

(Слайд 20) Сортировка методом выбора выполняется быстрее. Как вы думаете, почему? (Сортировка выбором работает быстрее, т.к. в алгоритме меньше операций перестановки элементов массива). <Для аргументации можно открыть по ссылке тексты программ (Слайд 21).>

е) Решение проблемной задачи.

Вернемся в офис Кости Байтова (Слайд 22) и допишем его программу. Вставим в нее фрагмент программы сортировки методом выбора (Слайд 23). <Можно открыть файл test_rez_itog.pas в среде PascalABC> Проверим работу программы (Слайд 24). <или запуск программы в среде PascalABC>

7. Подведение итогов урока. Рефлексия

(Слайд 25) (Появляется Костя.
— О, программа уже готова! Спасибо, выручили! И сами в роли программистов побывали.

— Вижу, вы учились использовать два метода сортировки. Метод выбора из них более эффективный. Но и сортировка обменом вам пригодится.

— Метод обмена более прост для записи, а главное – он лежит в основе некоторых более совершенных алгоритмов сортировки.)

Пора прощаться в Костей Байтовым и возвращаться в наш класс.

(Слайд 26)

Ребята, вы хорошо потрудились сегодня и многое узнали. Давайте поделимся впечатлениями о путешествии. Прошу вас высказаться одним предложением, выбирая начало фразы из списка на экране:

Сегодня я узнал…

Было интересно…	Было трудно…
Я выполнял задания…	Я понял, что…	Теперь я могу…
Я почувствовал, что…	Я приобрел…	Я научился…
У меня получилось …	Я смог…	Я попробую…
Меня удивило…	Урок дал мне для жизни…	Мне захотелось…

Удалось нам достичь цели урока – научиться программировать сортировку массива? (Да)

Домашнее задание. (Слайд 16)

Задача:

Уровень В: Дан массив из N элементов. Вывести три самых маленьких элемента массива.

Уровень С: Дан массив из N элементов. Определить количество различных элементов в массиве.

По желанию: Если вас заинтересовала проблема сортировки, то вы можете прочитать о других ее методах, например, в Википедии (ru.wikipedia.org).

<Выставление отметок>

Спасибо за урок!

Список литературы.

1. Семакин И.Г. Информатика и ИКТ : учебник для 9 класса / И.Г. Семакин, Л.А. Залогова, С.В. Русаков, Л.В. Шестакова. – М.: БИНОМ. Лаборатория знаний, 2010.

2. Босова Л.Л. Информатика и ИКТ : учебник для 9 класса : в 2ч. Ч. 1 / Л.Л. Босова, А.Ю. Босова. – М.: БИНОМ. Лаборатория знаний, 2012.