План открытого урока в 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 ≤ 10⁹).

Выходные данные

В выходной поток выведите НОД чисел А и В.

Пример

Входные данные Выходные данные

12 42 6

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

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

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

НОД(|A_x-B_x|, |A_y-B_y|)+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). Каждая из координат не превышает по абсолютной величине значения 10⁹.

Выходные данные

Выходной поток должен содержать одно число - количество точек на заданном отрезке, имеющих целочисленные координаты.

Пример

Входные данные Выходные данные

0 0 -2 -2 3

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

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

Совместно разрабатывают алгоритм решения задачи №358 "Забор в парке", пишут и сдают на проверку решающую ее программу либо пытаются отладить и успешно сдать программу по задаче №319 "Точки отрезка".

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

Задача №358 "Забор в парке"

с acmp.ru

Условие задачи

В парке деревья образуют квадратную решетку с шагом один метр. Часть парка было решено оградить забором, который представляет собой треугольник с заданными координатами вершин. Деревья, которые в точности попадают на вершины или стороны треугольника, придется срубить. Требуется написать программу, которая найдет количество таких деревьев.

Входные данные

Входной поток содержит шесть целых чисел - координаты вершин треугольника. Все числа по абсолютной величине не превышают 10⁹ и разделены пробелами.

Выходные данные

Выходной поток должен содержать одно число - количество деревьев.

Пример

Входные данные Выходные данные

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. - Режим доступа: acmp.ru/

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

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

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

Литература

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

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

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