План открытого урока в 11 классе по теме “Алгоритм Евклида нахождения НОД в геометрических задачах”

Зубков Олег Владимирович, учитель информатики МАОУ Лицей ИГУ города Иркутска



План открытого урока в 11 классе
по теме “Алгоритм Евклида нахождения НОД в геометрических задачах”

Тема: Алгоритм Евклида нахождения НОД в геометрических задачах.
ЭОР: “Школа программиста” (acmp.ru), “Timus Online Judge” (acm.timus.ru)
Технология: интерактивный метод обучения
УМК: Поляков К. Ю. . Еремин Е. А. Информатика. Углублённый уровень: учебник для 10 класса : в 2 ч. Ч.1., БИНОМ. “Лаборатория знаний”, 2013.
Тип урока: урок комплексного применения знаний
Образовательная цель: создать условия для формирования навыков применения алгоритма Евклида для решения олимпиадных задач.
Деятельностная цель: закрепить навыки быстрого и безошибочного программирования алгоритма Евклида на языке С++.
Форма организации: коллективное, групповое - в малых группах, индивидуальное учебное занятие.

Задачи:
Предметные: ознакомление с олимпиадными задачами, решаемыми при помощи нахождения НОД двух чисел;
Личностные: формирование познавательного интереса к изучаемому предмету;
Межпредметные: формирование навыков решения задач из одной области при помощи методов из смежной области знаний на примере разделов “Теория чисел” и “Геометрия”;
Деятельностные задачи:
предметные: построение и отладка программ для реализации комбинированного алгоритма;
личностные: воспитание внимательности, аккуратности и настойчивости при достижении поставленной цели;
метапредметные: развитие методов получения новых знаний: анализ, синтез, рассуждения по аналогии.




Ход урока
Деятельность
Применяемые технологии, приёмы, средства организации урока
Интерактивная доска

Учитель
Ученики



Организационный момент, актуализация знаний - время 5 мин.

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

Приветствуют учителя, занимают рабочие места, запускают среду программирования CodeBlocks и авторизуются на ЭОР “Школа программиста”. Параллельно вспоминают и озвучивают алгоритм Евклида

Формирование ответственного отношения к учению,
создание условия для возникновения у ученика внутренней потребности включения в учебный процесс.

Найти наибольший общий делитель чисел:

12 и 18;

1000 и 128;

714 и 221;

Повторение и применение уже известной краткой реализации алгоритма Евклида - 5 минут

На экране уже известная ученикам рекурсивная реализация алгоритма Евклида. Проговаривает алгоритм, особо отмечая условие завершения и выхода из рекурсии.
Создают шаблон программы, самостоятельно или, сверяясь с интерактивной доской, пишут функцию NOD и проверяют свои ответы на примеры из первого раздела урока.
Включение в учебную деятельность на личностно значимом уровне, повторение и закрепление на практике путем проверки устных вычислений при помощи самостоятельно написанной программы.
int NOD (int a, int b){
if (b ==0) return a;
else return NOD(b, a%b);
}


Закрепление алгоритма Евклида при помощи автоматической проверяющей системы - 5 минут

Анализирует задачу №148 “НОД”, отмечает, что алгоритм ее решения уже фактически реализован, помогает исправить ошибки.
Производят окончательную отладку уже работающей программы и сдают ее на проверку в автоматической системе acmp.ru. При получении сообщения об ошибке, пытаются найти и исправить недостаток самостоятельно.
Доведение условно работающей программы до состояния прохождения формальной и независимой от ученика и учителя проверки, воспитание внимательности и аккуратности при написании фрагмента программы уже известного алгоритма.
Задача №148 “НОД” с acmp.ru
Условие задачи
Даны два натуральных числа A и B. Требуется найти их наибольший общий делитель (НОД).
Входные данные
Во входном потоке два натуральных числа A и B через пробел (A, B
· 109).
Выходные данные
В выходной поток выведите НОД чисел А и В.
Пример
Входные данные Выходные данные
12 42 6


Осмысление основной учебной задачи - 6 минут

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

Коллективно или разбившись на подгруппы, анализируют приведенные примеры и ответы к ним, пытаются применить уже известную тему урока и формулируют гипотезу о том, что число целых точек на отрезке есть
НОД(|Ax-Bx|, |Ay-By|)+1.
Проверяют эту гипотезу на своих примерах.
Метод постановки и решения учебной задачи: подводящий к теме - диалог, коллективное обсуждение или обсуждение в группах.

Задача: даны две произвольные точки A и B плоскости с целыми координатами.
Требуется узнать, сколько точек с целыми координатами попадает на отрезок АB.


1: A(1,7), B(7,4)
2: A(2,1), B(6,1)
3: A(10,7), B(10,4)
4: A(9,1), B(12,2)

И еще:

5: A(16, 11), B(1,1)



Написание и отладка программы, окончательная проверка гипотезы - время 9 мин.

Формулирует основную задачу урока, предлагает самостоятельно написать и сдать на проверку в систему программу для ее решения, при необходимости помогает исправить ошибки и отладить неработающие варианты программ.


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


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

Задача №319 “Точки на отрезке”
с acmp.ru
Условие задачи
Концы отрезка на плоскости имеют целочисленные координаты. Написать программу, которая вычислит, сколько всего точек с целочисленными координатами принадлежат этому отрезку.
Входные данные
Входной поток содержит четыре числа – координаты концов отрезка (x1, y1) и (x2, y2). Каждая из координат не превышает по абсолютной величине значения 109.
Выходные данные
Выходной поток должен содержать одно число – количество точек на заданном отрезке, имеющих целочисленные координаты.
Пример
Входные данные Выходные данные
0 0 -2 -2 3







Решение дополнительной задачи или продолжение решения основной задачи - время 8 мин.

Предлагает ученикам, получившим вердикт Accepted по предыдущей задаче объединиться в группу решающих дополнительную задачу №358 “Забор в парке”. Убедившись, что данная задача понята и группа приступила к ее решению и написанию программы, продолжает помогать группе учеников, программы которых по предыдущей задаче еще не прошли окончательную проверку в системе.
Совместно разрабатывают алгоритм решения задачи №358 “Забор в парке”, пишут и сдают на проверку решающую ее программу либо пытаются отладить и успешно сдать программу по задаче №319 “Точки отрезка”.
Метод работы в малых группах, обусловленый разной скоростью восприятия материала и написания программ обучающимися.




Задача №358 “Забор в парке”
с acmp.ru
Условие задачи
В парке деревья образуют квадратную решетку с шагом один метр. Часть парка было решено оградить забором, который представляет собой треугольник с заданными координатами вершин. Деревья, которые в точности попадают на вершины или стороны треугольника, придется срубить. Требуется написать программу, которая найдет количество таких деревьев.
Входные данные
Входной поток содержит шесть целых чисел – координаты вершин треугольника. Все числа по абсолютной величине не превышают 109 и разделены пробелами.
Выходные данные
Выходной поток должен содержать одно число – количество деревьев.
Пример
Входные данные Выходные данные
0 0 2 0 0 2 6

Домашнее задание, инструктаж по его выполнению – время 2 мин.

Предлагает домашнее задание каждой группе в отдельности:
решившим все задачи урока -дополнительную задачу №1259 “Как стать звездой” с ресурса acm.timus.ru, остальным - дорешать и успешно сдать на проверку в системе acmp.ru те задачи урока, по которым программа не получила полный балл.
Самостоятельно выбирают объем
домашнего задания; задают уточняющие вопросы.

Объективно оценивать свои результаты и соответственно им выбирать домашнее задание.
Способность организовать собственную деятельность.



Задачи для тренировки: © acm.timus.ru, 2000-2015

1259. Как стать звездой
Ограничение времени: 1.0 секундыОграничение памяти: 64 МБ
Определение. Звездой называется замкнутая ломаная, построенная за конечное число шагов по следующему алгоритму:
Фиксируем некоторый угол
· (0 <
· <
·)
Первое звено ломаной (0, 0) – (1, 0).
Второе звено ломаной получается из первого путем его поворота на угол
· против часовой стрелки относительно точки (1, 0).
(i + 2)-е звено ломаной получается из (i + 1)-го звена путем его поворота на угол
· против часовой стрелки относительно свободного конца (противоположного тому, которое соединено с i-м звеном) (i + 1)-го звена.
Алгоритм заканчивает работу сразу, как только ломаная замкнулась.
Определение. Количество вершин звезды количество звеньев построенной ломаной.
Исходные данные
Единственное целое число N (3
· N 
· 100000).
Результат
Выведите количество различных звёзд с N вершинами.
Примеры
исходные данные
результат

5
2

9
3


1291. Шестерёнки
Ограничение времени: 1.0 секундыОграничение памяти: 64 МБ
Каждая шестерня на схеме обозначается окружностью с вписанным в ней числом  количеством зубьев шестерни. Шестерни соединяются самым обычным образом: зубья одной шестерёнки заходят в пазы между зубьями другой так, что вращение одной из них передаётся другой. Известно, что система шестерёнок не содержит циклы. Необходимо проверить, что скорость и направление вращения каждой шестерни соответствуют требованиям.
Исходные данные
В первой строке содержится число N (1
· N 
· 1000)  количество шестерёнок в системе. В следующих N строках содержится информация о шестерёнках и их соединении между собой. i-я строка содержит следующие числа через пробел: количество зубьев i-й шестерёнки (целое число от 1 до 1000) и список номеров шестерёнок, с которыми она соединена, заканчивающийся нулём.
Последняя строка входа содержит два числа: номер шестерни, соединённой с кинетическим генератором, и скорость, с которой она вертится против хода часовой стрелки (целое число от 1 до 1000).
Результат
Выведите N строк. i-я строка должна содержать скорость вращения i-й шестерни в данном механизме в виде несократимой дроби. Числитель и знаменатель должны быть разделены знаком /’. Скорость может быть как положительной, тогда считается, что шестерня крутится против хода часовой стрелки, так и отрицательной, тогда считается, что шестерня крутится по ходу часовой стрелки. Если скорость отрицательна, то знак минус должен быть перед числителем. Если скорость равна нулю, то числитель должен быть равен нулю, а знаменатель  единице. Гарантируется, что и числитель, и знаменатель скорости любой шестерёнки не превосходит по абсолютному значению 106.
Пример
исходные данные
результат

4
10 2 3 0
20 1 0
40 1 4 0
100 3 0
1 6
6/1
-3/1
-3/2
3/5




Медиаресурсы
1. Образовательный Интернет-ресурс олимпиадного программирования для школьников “Школа программиста” [Электронный ресурс] // Сайт Красноярского краевого Дворца пионеров и школьников. – 2015. – Режим доступа: [ Cкачайте файл, чтобы посмотреть ссылку ]
2. Архив задач по программированию с автоматической проверяющей системой “ Timus Online Judge” [Электронный ресурс] // Сайт студентов и выпускников Уральского Федерального университета. – 2015. – Режим доступа: http://acm.timus.ru/
3. Портал Codeforces [Электронный ресурс] // Сайт Михаила Мирзаянова: платформа для создания, проведения и обсуждения соревнований по программированию. – 2015. – Режим доступа: [ Cкачайте файл, чтобы посмотреть ссылку ]
4. Информационный ресурс по программированию e-maxx [Электронный ресурс] // Сайт Максима Иванова: методические и информационные материалы для подготовки к олимпиадам по программированию. – 2015. – Режим доступа: [ Cкачайте файл, чтобы посмотреть ссылку ]


Литература
1. Кирюхин В.М. Методика проведения и подготовки к участию в олимпиадах по информатике. Всероссийская олимпиада школьников. – М.: БИНОМ. Лаборатория знаний, 2012. – 280 с.
2. Меньшиков Ф.В. Олимпиадные задачи по программированию. – СПб.: Питер, 2006. – 315 с.
3. Бьерн Страуструп - Программирование. Принципы и практика использования C++. –М.: Вильямс, 2011. - 1248 с.


Заголовок 1Заголовок 2Заголовок 315