План урока на тему:

Бинарное дерево и выигрышные стратегии в дискретных играх

Информатика10 класс65 разделов
Бинарное дерево и выигрышные стратегии в дискретных играх

Информатика · 10 класс · Практикум · 45 мин

Бинарное дерево и выигрышные стратегии в дискретных играх

Цели и задачи

  • Цель: за 45 минут научиться строить дерево перебора вариантов для игры двух игроков с полной информацией, представлять стратегию в табличной форме и определять выигрышную стратегию одного из игроков.
  • Сформировать умение выделять позиции игры, возможные ходы и конечные результаты, используя модель бинарного дерева.
  • Научиться анализировать дерево от конечных позиций к начальной и обосновывать выигрышность стратегии первого или второго игрока.
  • Развивать навыки алгоритмического, логического и критического мышления при решении практических игровых задач.
  • Воспитывать ответственность за точность построения модели, готовность проверять решение и аргументировать собственный выбор.

Планируемые результаты

Личностные

  • Проявляют интерес к алгоритмическому моделированию игровых ситуаций и связывают изучаемый материал с задачами программирования и исследования операций.
  • Осознают ценность последовательного анализа и проверки гипотез при решении нестандартной задачи.
  • Формируют ответственное отношение к самостоятельному выбору стратегии и аргументации результата.
  • Развивают готовность воспринимать ошибку в дереве игры как источник для уточнения модели.

Метапредметные

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

Предметные

  • Знать понятия «позиция игры», «ход», «конечная позиция», «дерево перебора вариантов», «выигрышная стратегия».
  • Уметь строить дерево игры для двух игроков с полной информацией при двух возможных ходах из позиции.
  • Уметь описывать стратегию в табличной форме с указанием позиции, хода и результата.
  • Уметь определять выигрышные и проигрышные позиции анализом дерева от листьев к корню.
  • Уметь обосновывать вывод о стратегии первого или второго игрока.

Универсальные учебные действия (УУД)

Личностные УУД

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

Регулятивные УУД

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

Познавательные УУД

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

Коммуникативные УУД

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

Подготовка учителя к уроку

  • Подготовить презентацию или интерактивную доску с обозначениями: вершина — позиция, ребро — ход, лист — конечный результат.
  • Распечатать по одной карточке на пару с правилами игры: из числа 1 можно прибавить 1 или умножить на 2; выигрывает игрок, первым получивший число 10.
  • Распечатать по одной карточке на пару с усложнённой игрой: из числа можно прибавить 1 или 2; выигрывает игрок, первым получивший число 8.
  • Подготовить индивидуальные листы самопроверки с критериями полноты дерева, правильности классификации позиций и обоснования стратегии.
  • Вывести на доску шаблон таблицы: «Позиция», «Ход игрока», «Ответ соперника», «Результат».
  • Подготовить маркеры двух цветов или цифровые инструменты для обозначения выигрышных и проигрышных позиций.
  • Распечатать по одному листу с заданием повышенного уровня на каждого ученика.
  • Подготовить таймер и, при наличии оборудования, открыть редактор схем или электронную таблицу для построения дерева.
  • Разложить карточки по парам до начала урока; предусмотреть чистые листы для построения деревьев.

Ход урока

Этап 1. Организационный момент и мотивация (3 мин)

Цель этапа: включить учащихся в практическую работу и показать, что стратегия требует анализа всех ответов соперника.
Время
Действие учителя
Действие учеников
1 мин
Учитель приветствует класс: "Здравствуйте, ребята. Сегодня мы будем не пересказывать определения, а исследовать игровые позиции и доказывать, кто может гарантировать себе победу. На доске вы видите две возможные операции: прибавить 1 и умножить число на 2. Как вы думаете, достаточно ли выбрать один удачный ход, чтобы выиграть игру?"
Фиксируют тему в тетради, выдвигают предположения: "Нет, нужно учитывать ответ соперника" и "Нужно проверять несколько ходов вперёд".
2 мин
Учитель показывает короткую цепочку позиций 1 → 2 → 4 → 8 и говорит: "Эта цепочка показывает только один вариант развития игры. Но у соперника тоже есть выбор. Приём сегодняшней работы — дерево перебора вариантов. Наша задача — построить не одну линию, а все допустимые ветви и найти ход, который остаётся успешным при любом ответе соперника."
Сравнивают линейную цепочку и дерево, формулируют практическую цель: "Построить все варианты и определить гарантированный выигрыш".
Завершение этапа: учитель подводит итог: "Мы увидели, что один удачный вариант ещё не является стратегией. Теперь проверим, какие знания нужны, чтобы построить полное дерево игры."

Этап 2. Актуализация понятий и правил (5 мин)

Цель этапа: актуализировать понятия вершины, ветви, конечной позиции и правила чтения дерева.
Время
Действие учителя
Действие учеников
2 мин
Учитель выводит на экран схему с вершиной 3 и двумя стрелками к позициям 4 и 6: "Посмотрите на схему. Что обозначает число в вершине? Что обозначает стрелка? Почему из одной позиции появляются две следующие?"
Отвечают: "Число обозначает текущую позицию игры", "Стрелка обозначает разрешённый ход", "Две ветви соответствуют двум операциям".
3 мин
Учитель проводит приём "Подумай — обсуди в паре — поделись": "За 30 секунд определите, что должно быть записано в листе дерева. Затем обсудите ответ в паре и подготовьте одну точную формулировку. Не называйте листом любую вершину: конечная позиция определяется условием победы или невозможностью продолжения."
Сначала формулируют ответ индивидуально, затем обсуждают в паре и сообщают: "В листе должна быть позиция, на которой игра заканчивается; в ней фиксируется победитель или результат".
Завершение этапа: учитель подводит итог: "Мы вспомнили, что дерево состоит из позиций и ходов, а листы отражают завершение игры. Теперь сформулируем проблему, которую решим на практикуме."

Этап 3. Постановка проблемы и планирование практикума (4 мин)

Цель этапа: определить алгоритм поиска выигрышной стратегии и критерии правильного решения.
Время
Действие учителя
Действие учеников
2 мин
Учитель записывает на доске задачу: "Игра начинается с числа 1. За ход разрешается прибавить 1 или умножить число на 2. Побеждает тот, кто первым получает 10. Можно ли заранее доказать, что первый игрок выиграет?" Затем спрашивает: "Какие действия нужно выполнить, чтобы ответ был доказательством, а не догадкой?"
Предлагают план: "Выписать все ходы, построить дерево, отметить конечные позиции, анализировать дерево снизу вверх и записать стратегию в таблицу".
2 мин
Учитель фиксирует на доске алгоритм: "Первое — выписываем правила. Второе — строим все допустимые ветви до 10. Третье — отмечаем позиции, из которых игрок может привести игру к победе. Четвёртое — проверяем все ответы соперника. Пятое — оформляем стратегию таблицей."
Записывают алгоритм практической работы и задают уточняющие вопросы о повторяющихся позициях и остановке игры.

Посмотрите план целиком

Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.

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

Этап 4. Практикум 1. Построение дерева перебора вариантов (10 мин)

Цель этапа: построить полное дерево игры с начальной позицией 1 и научиться не пропускать варианты.
Время
Действие учителя
Действие учеников
3 мин
Учитель раздаёт карточки и говорит: "Работаем в парах. Запишите в корне число 1. От него проведите две ветви: результат операции +1 и результат операции ×2. Для каждой новой позиции снова выпишите все разрешённые ходы, но остановитесь, когда получится 10. Один участник строит дерево, второй проверяет каждую вершину по правилам."
В парах записывают корень 1, строят первые ветви 2 и 2, замечают совпадение позиций и обсуждают, как обозначить одинаковые состояния.
4 мин
Учитель уточняет: "Если одна и та же позиция достигается разными путями, не удаляйте её смысл. Подпишите путь или изобразите отдельную ветвь, чтобы видеть, чей ход наступил. Проверяйте каждую вершину вопросом: какие операции ещё допустимы и не превышают ли они целевое число?" Учитель консультирует пары и отмечает типичные ошибки.
Достраивают ветви: из 2 получают 3 и 4, из 3 — 4 и 6, из 4 — 5 и 8, из 5 — 6 и 10, из 6 — 7 и 10, из 8 — 9 и 10, из 9 — 10 и 18; ветви, пересекающие 10, завершают по условию игры.
3 мин
Учитель предлагает взаимопроверку: "Обменяйтесь схемой с соседней парой. Проверьте три пункта: есть ли оба хода из каждой незавершённой позиции, остановлены ли позиции с 10, подписаны ли конечные результаты. Одну найденную неточность сформулируйте как вопрос, а не как готовый ответ."
Проверяют чужое дерево по трём критериям, задают вопросы: "Почему из этой позиции отсутствует ветвь умножения?" или "Почему здесь игра продолжается после получения 10?"

Запись в тетрадях

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

Этап 5. Практикум 2. Анализ дерева и описание стратегии (9 мин)

Цель этапа: научиться классифицировать позиции и переводить найденную стратегию в таблицу.
Время
Действие учителя
Действие учеников
3 мин
Учитель объясняет через эвристическую беседу: "Рассмотрим позицию непосредственно перед победой. Если из неё можно сделать ход в 10, она выгодна игроку, который ходит. А позиция, из которой любой ход отдаёт сопернику возможность победить, является проигрышной. Как будем двигаться по дереву?"
Отвечают: "От листьев к корню"; отмечают конечные позиции и определяют, кто сделал последний ход.
3 мин
Учитель предлагает заполнить таблицу на доске: "Позиция — выигрышный ход — ответ соперника — результат. Запишите не только первый ход. Если вы утверждаете, что стратегия выигрышная, покажите, что произойдёт после каждого ответа соперника."
Заполняют таблицу для найденной стратегии, например: «5 — +5 до 10 — игра заканчивается» и «6 — +4 до 10 — игра заканчивается», затем обсуждают, какие позиции могут быть выгодны игроку, делающему ход.
3 мин
Учитель задаёт вопрос: "Можно ли назвать стратегией последовательность 1 → 2 → 4 → 8?" После ответов уточняет: "Нет, если она не учитывает альтернативный ход соперника. Стратегия должна задавать действие в каждой позиции, которая может возникнуть при ответах соперника."
Обосновывают: "Одна цепочка не учитывает все ответы"; формулируют критерий выигрышной стратегии: «при любом ходе соперника остаётся ход, ведущий к победе».

Эталон решения

Для каждой позиции выписываются разрешённые переходы: $x \to x+1$ и $x \to 2x$. Позиция с числом 10 является конечной. Позиция считается выигрышной для игрока, если существует хотя бы один ход в проигрышную для соперника позицию. Позиция считается проигрышной, если все допустимые ходы ведут в выигрышные позиции соперника. Итог стратегии записывается таблицей: для каждой возможной позиции указывается ход, сохраняющий возможность победы при любом ответе соперника.
Завершение этапа: учитель подводит итог: "Мы научились читать дерево снизу вверх и описывать стратегию не одной стрелкой, а таблицей ответов. Теперь каждый проверит себя на новой игре без пошаговой подсказки."

Этап 6. Самостоятельная практическая работа с самопроверкой (10 мин)

Цель этапа: самостоятельно построить дерево и определить выигрышную стратегию в изменённой игре.
Время
Действие учителя
Действие учеников
6 мин
Учитель раздаёт индивидуальное задание: "Игра начинается с числа 1. За ход можно прибавить 1 или 2. Побеждает игрок, который первым получает 8. Постройте дерево всех вариантов, отметьте выигрышные и проигрышные позиции и определите, есть ли выигрышная стратегия у первого игрока. Оформите минимум четыре строки таблицы стратегии."
Индивидуально строят дерево: из каждой позиции выписывают переходы +1 и +2, останавливаются на 8, анализируют позиции от конечных к начальной, оформляют стратегию в таблице.
2 мин
Учитель предлагает самопроверку по чек-листу: "Поставьте плюс, если дерево полное; если конечные позиции выделены; если каждый вывод подтверждён всеми ответами соперника; если таблица содержит конкретные ходы. Если одного плюса нет, исправьте работу."
Проверяют четыре пункта, исправляют пропущенные ветви или неверную классификацию.
2 мин
Учитель организует короткое сравнение: "Поднимите карточку зелёного цвета, если выигрышная стратегия есть у первого игрока, жёлтого — если вывод не завершён. Две пары объяснят решение, называя ключевую позицию, а не только итог."
Показывают результат, сравнивают решения, объясняют: "Нужно попасть в такую позицию, после которой на каждый ход соперника есть ответ, ведущий к 8".

Эталон решения

Для игры с ходами $+1$ и $+2$ и целью 8 анализ начинают с позиций 7, 6 и 5. Из 7 любой разрешённый ход приводит к завершению или превышению цели в зависимости от принятого правила, поэтому в условии следует явно считать ход, превышающий 8, недопустимым. При таком соглашении из 7 доступен ход $+1$ в 8; из 6 доступны 7 и 8; из 5 доступны 6 и 7. Окончательный вывод делается только после построения полного дерева и проверки того, кто получает ход в каждой позиции.
Завершение этапа: учитель подводит итог: "Самостоятельная работа показала, что главное затруднение возникает не в рисовании стрелок, а в точном учёте правил и порядка ходов. Завершим урок проверкой выводов и личной рефлексией."

Этап 7. Рефлексия и подведение итогов (4 мин)

Цель этапа: зафиксировать освоенный алгоритм, выявить затруднения и определить направление дальнейшей работы.
Время
Действие учителя
Действие учеников
2 мин
Учитель проводит приём "Билет на выход": "На листе ответьте на три вопроса: что обозначает вершина дерева; как распознать выигрышную позицию; почему одной цепочки ходов недостаточно для доказательства стратегии?"
Письменно отвечают: "Вершина — позиция", "выигрышная позиция имеет ход к проигрышной для соперника", "цепочка не учитывает все ответы".
2 мин
Учитель обращается к классу: "Оцените свою работу: зелёный — могу построить дерево и доказать стратегию; жёлтый — строю дерево, но путаюсь в классификации; красный — нужна совместная тренировка. Запишите одно действие, которое поможет перейти на следующий уровень."
Выбирают цвет самооценки, записывают индивидуальный шаг: «проверять все ветви», «анализировать дерево от листьев», «оформлять таблицу стратегии».
Завершение этапа: учитель подводит итог: "Сегодня вы построили дерево перебора вариантов, научились анализировать его от конечных позиций и описывать выигрышную стратегию таблицей. Важно помнить: стратегия гарантирует результат только тогда, когда учитывает любой ответ соперника."

Критерии оценивания практической работы

  • «5» — построено полное дерево для обеих практических игр, не пропущены допустимые ходы, корректно выделены конечные и выигрышные позиции, таблица стратегии содержит конкретные ответы на ходы соперника, вывод аргументирован.
  • «4» — дерево и общий вывод верны, но допущена одна неточность в оформлении ветви или таблицы; ошибка исправляется при самопроверке.
  • «3» — построена основная часть дерева, определены отдельные выигрышные позиции, однако пропущены несколько ветвей или недостаточно обоснована стратегия.
  • Ниже «3» — дерево существенно неполно, правила игры применены непоследовательно, выигрышная стратегия не подтверждена анализом ответов соперника.

Рефлексия

Вопрос для ученика
Цель вопроса
Что обозначают вершины, рёбра и листья дерева игры?
Проверка понимания базовой модели и терминов.
Как вы доказывали, что стратегия является выигрышной?
Выявление понимания необходимости учитывать все ответы соперника.
На каком этапе возникло затруднение: построение дерева, классификация позиций или таблица стратегии?
Диагностика конкретной точки затруднения.
Какое правило самопроверки вы будете использовать в следующей задаче?
Формирование навыка осознанного контроля решения.

Завершающее слово учителя

"Сегодня мы рассмотрели игру как алгоритмическую модель: позиция стала вершиной, ход — ребром, а результат — листом дерева. Мы убедились, что выигрышная стратегия должна учитывать любой ответ соперника, а не только удобную последовательность ходов. Типичная ошибка — пропустить ветвь или продолжить игру после достижения конечного числа. На следующем уроке мы усложним модели: рассмотрим игры с несколькими параметрами и обсудим, как описывать перебор вариантов с помощью алгоритма."

Домашнее задание

Уровень
Что задать
Зачем
Базовый (обязательный)
Решить две игры на построение дерева: из числа 1 разрешены ходы +1 и +2, цель — 7; из числа 2 разрешены ходы +1 и умножение на 2, цель — 12. Для каждой игры построить дерево и указать, у какого игрока есть выигрышная стратегия.
Закрепляет построение полного дерева и определение конечных позиций; при проверке смотреть на полноту ветвей и соблюдение правил.
Средний (повышающий)
Для одной из игр базового уровня оформить стратегию в таблице минимум с пятью строками: позиция, возможный ход, ответ соперника и последующий результат.
Формирует умение описывать стратегию формально; при проверке смотреть, учитывает ли таблица все существенные ответы соперника.
Продвинутый (дополнительный)
Придумать собственную игру двух игроков с двумя разрешёнными ходами и конечной целью, построить дерево первых уровней, исследовать выигрышные позиции и кратко обосновать выбор правил.
Развивает проектное и исследовательское мышление; при проверке смотреть на непротиворечивость правил, полноту модели и доказательность вывода.
Контрольные вопросы перед выходом: «Что такое позиция игры?», «Почему дерево нужно анализировать от конечных позиций?», «Чем выигрышный ход отличается от случайно удачного хода?», «Что обязательно должно быть указано в таблице стратегии?»

Создайте уникальный план урока по своей теме

  • Любая тема, любой уровень
  • Структура по ФГОС
  • 100% уникальный план урока
  • Цели, ход урока, рефлексия
  • Экспорт в PDF и Word
  • Готово за 1 минуту

Другие темы по информатике для 10 класса

Представление целых и вещественных чисел в памяти компьютераЛогический квест «Логические основы компьютера»Блоки питанияБинарное дерево и выигрышные стратегии в дискретных играхТроичная уравновешенная система счисленияОсновные устройства компьютераСистемы, компоненты систем и их взаимодействиеТекстовый процессор. Редактирование и форматирование; Проверка орфографии и грамматики. Средства поиска и автозамены; Использование стилей. Структурированные документы. Сноски, оглавление; ОблачныеСоздание таблиц в текстовом редактореФайловая система компьютераПринципы работы компьютера. Персональный компьютер; Виды программного обеспечения и их назначение; Выбор конфигурации компьютера в зависимости от решаемых задачДвоичная, восьмеричная и шестнадцатеричная системы и переводы между ними; Арифметические операции в позиционных системах счисления

Чем удобны планы уроков Нейрум

  • Готовый план, не набросокЦели, ход урока, планируемые результаты, рефлексия — всё по структуре ФГОС, открыли и пошли вести.
  • План урока или техкартаОдин материал — два формата экспорта в PDF. Скачали то, что нужно завучу.
  • Свой план урока за минутуНе нашли нужный? ИИ-конструктор напишет план урока по вашей теме, классу и типу урока.

Вопросы и ответы

Как скачать план урока «Бинарное дерево. Дискретные игры двух игроков с полной информацией. Построение дерева перебора вариантов, описание стратегии игры в табличной форме. Выигрышные стратегии»?

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

Соответствует ли план урока ФГОС?

Да, структура урока — цели, ход урока, планируемые результаты — построена по ФГОС для 10 класса (информатике).

Можно ли изменить план под свой класс?

Да. После регистрации план урока открывается в конструкторе: этапы и содержание можно отредактировать или перегенерировать.