План открытого урока в 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 МБ

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

1.     Фиксируем некоторый угол α (0 < α < π)

2.     Первое звено ломаной (0, 0) – (1, 0).

3.     Второе звено ломаной получается из первого путем его поворота на угол α против часовой стрелки относительно точки (1, 0).

4.     (i + 2)-е звено ломаной получается из (i + 1)-го звена путем его поворота на угол α против часовой стрелки относительно свободного конца (противоположного тому, которое соединено с i-м звеном) (i + 1)-го звена.

5.     Алгоритм заканчивает работу сразу, как только ломаная замкнулась.

Определение. Количество вершин звезды — количество звеньев построенной ломаной.

Исходные данные

Единственное целое число 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-й шестерни в данном механизме в виде несократимой дроби. Числитель и знаменатель должны быть разделены знаком ‘/’. Скорость может быть как положительной, тогда считается, что шестерня крутится против хода часовой стрелки, так и отрицательной, тогда считается, что шестерня крутится по ходу часовой стрелки. Если скорость отрицательна, то знак минус должен быть перед числителем. Если скорость равна нулю, то числитель должен быть равен нулю, а знаменатель — единице. Гарантируется, что и числитель, и знаменатель скорости любой шестерёнки не превосходит по абсолютному значению 10⁶.

Пример

исходные данные	результат
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. – Режим доступа: http://acmp.ru/

2. Архив задач по программированию с автоматической проверяющей системой “ Timus Online Judge” [Электронный ресурс] // Сайт студентов и выпускников Уральского Федерального университета. – 2015. – Режим доступа: http://acm.timus.ru/

3. Портал Codeforces  [Электронный ресурс] // Сайт Михаила Мирзаянова: платформа для создания, проведения и обсуждения соревнований по программированию. – 2015. – Режим доступа: http://codeforces.ru/

4. Информационный ресурс по программированию e-maxx [Электронный ресурс]  // Сайт Максима Иванова: методические и информационные материалы для подготовки к олимпиадам по программированию. – 2015. – Режим доступа: http://e-maxx.ru/

Литература

1. Кирюхин В.М. Методика проведения и подготовки к участию в олимпиадах по информатике. Всероссийская олимпиада школьников. – М.: БИНОМ. Лаборатория знаний, 2012. – 280 с. 

2. Меньшиков Ф.В. Олимпиадные задачи по программированию. – СПб.: Питер, 2006. – 315 с.

3. Бьерн Страуструп - Программирование. Принципы и практика использования C++. –М.: Вильямс, 2011. - 1248 с.