Урок информатики по теме "Определение выигрышной стратегии игры"

Цель урока: сформировать навык решения задач типа СЗ из заданий ЕГЭ с помощью дерева игры.

1. Освоить понятия: стратегия игры, полное дерево игры, неполное дерево игры.
2. Овладеть методом построения дерева игры.
3. Приводить доказательство того, что стратегия игры - правильная.

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

1. Развивать умения и навыки анализа и построения дерева игры.
2. Способствовать интеграции знаний учащихся, полученных при изучении информатики, математики.

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

1. Развить внимательность и аккуратность.
2. Оценивать результаты своей деятельности.
3. Активировать творческие способности учащихся.
4. Эффективно использовать разные информационные ресурсы.

1. Метод построения полного дерева игры.
2. Метод построения неполного дерева игры.

Ученик должен уметь:

1. Строить полное и неполное дерево игры.
2. Приводить доказательство того, что приведенная стратегия игры – правильная.
3. Уметь определять выигрывающего игрока.

Методы обучения: частично-поисковый, объяснительно-иллюстративный, репродуктивный.

1. Организационный момент.
2. Целеполагание и мотивация.
3. Объяснение нового материала.
4. Осознание и осмысление учебного материала.
5. Первичное закрепление.
6. Подведение итогов урока.
7. Домашнее задание.

• коллективная;
• индивидуальная.

Программное обеспечение ПК: операционная система Windows XP, PowerPoint 2003.

Средства обучения: мультимедийный проектор, компьютер, MS PowerPoint 2003; презентация “Определение выигрышной стратегии игры” (Презентация 1), презентация “Определение выигрышной стратегии игры” (Презентация 2), раздаточный материал с заданиями (Приложение 1), раздаточный материал для записи полного дерева игры (Приложение 2), раздаточный материал для записи неполного дерева игры (Приложение 3). презентация “Домашнее задание” (Приложение 4).

Технологическая карта урока

Ход урока

2. Целеполагание и мотивация. (3 мин.).

При объяснении нового материала используется (Презентация 1). Учитель предлагает решить задачу: Пример 1. “Камешки”. <Слайд 1>, <Слайд 2>, <Слайд 3>.

Для краткой записи условия задачи учащимся предлагаются следующие три слайда. <Слайд 4>, <Слайд 5>, <Слайд 6>.

Рассмотрим решение задачи на представленных далее слайдах. <Слайд 7>, <Слайд 8>, <Слайд 9>.

4. Осознание и осмысление учебного материала. (10 мин.).

Дальнейшее решение задачи рассматривается вместе с учащимися, они предлагают свои варианты решения. <Слайд 10>, <Слайд 11>, <Слайд 12>, <Слайд 13>, <Слайд 14>, <Слайд 15>, <Слайд 16>, <Слайд 17>, <Слайд 18>, <Слайд 19>, <Слайд 20>, <Слайд 21>.

Учитель предлагает решить следующую задачу: Пример 2. “Фишки” с последующей проверкой всех этапов решения. При решении задачи используется (Презентация 2). <Слайд 1>, <Слайд2>.

Для краткой записи условия задачи учащимся предлагаются следующие три слайда. <Слайд 3>, <Слайд 4>, <Слайд 5>.

Существует несколько способов выполнения этого задания. Мы рассмотрим только один способ – метод построения полного дерева игры и определения по нему выигрывающего игрока. Этот метод самый кропотливый и трудоемкий.

Построение полного дерева игры – это рассмотрение для каждой позиции игры всех возможных ходов. Затем для получившихся позиций – снова рассмотрение всех возможных ходов. И так до тех пор, пока по всем получившимся “направлениям” мы не достигнем конца игры (в рассмотренном примере – расстояние от точки (0, 0) до текущей позиции фишки больше 12 единиц).

Обычно дерево рисуют сверху вниз или слева направо.

Данное решение выглядит очень трудоемким, потому что для каждой позиции игры нужно указать три возможных варианта следующего хода (в других задачах – четыре варианта). То есть, рассматривая каждый следующий ход, размер нашего дерева игры увеличится в три раза.

Выигрыш редко достигается раньше четвертого хода. А это значит, что в дереве на 4-м ходу рассматриваются 3⁴=81 вариант игры, правда, часто многие из них повторяются.

Более короткие методы решения задачи мы рассмотрим позже. Важно, чтобы вы, прежде всего, понимали, как построить дерево игры и какие выводы нужно из него сделать. А уже потом думать об убыстрении решения.

Дерево игры обычно строят-рисуют сверху вниз или слева направо. Мы будем изображать его слева направо. В дереве в результате будет около 81 позиции на 4-м уровне. Если изображать дерево сверху вниз, ширины страницы при этом не хватит. А вот в высоту 81 строчка вполне поместится.

Рассмотрим все возможные варианты хода первого игрока (их три) и все варианты ответного хода второго игрока для каждой позиции первого игрока (их девять). <Слайд 6>.

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

Хотя, конечно, правильнее было бы подумать об этом до построения дерева игры.

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

Мы будем для каждой позиции дерева вычислять расстояние до точки (0, 0) по теореме Пифагора (квадрат расстояния). <Слайд 7>.

Допишем к нашему дереву для каждой позиции квадрат расстояния до точки (0, 0):

5. Первичное закрепление. (15 мин.). <Слайд 8>

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

Рассматривать следующие варианты ходов вы будете самостоятельно. Для этого вам необходимо Приложение 1 к данному уроку, которое находится на ваших столах. Первый ход второго игрока у вас уже проставлен, у некоторых он будет совпадать, вам необходимо продолжить ветвь дерева игры, указать все варианты хода (вторые ходы) первого игрока, а затем ответные ходы второго игрока.

Вы указываете и выигрышные и проигрышные ходы обоих игроков и рядом с ходом нужно указать квадрат расстояния до точки (0, 0) и указываете, кто в вашем задании выигрывает первый или второй игрок.

На выполнения задания учащимся дается 5 минут. Затем учащиеся в порядке очереди относительно позиции первого хода второго игрока в представленной выше таблице на слайде 7 выходят к доске (если были совпавшие варианты у двух учащихся, то оба выходят к доске) и озвучивают остальным учащимся, не поворачиваясь к доске, получившиеся у них в таблице варианты ходов и результаты игры.

В это же время на доске остальные учащиеся видят слайд с результатами по таблице каждого выступающего ученика (выступающих учеников) и могут сравнить их с озвученными результатами. Учитель отмечает совпадения на доске маркером “+” и если есть ошибки у выступающих после их доклада предлагает им исправить их в соответствии с результатами на слайде.

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

Остальным учащимся предлагается после озвученных каждым докладчиком результатов и сверенных с представленными результатами на слайде занести эти результаты в Приложение №2.

Заполненное учащимися Приложение №2 после выступления каждого из докладчиков будет являться полным деревом игры. Данное Приложение №2 и Приложения №3 сдается в конце урока учителю.

Итак, результаты первого (первых) докладчика (докладчиков). <Слайд 9>.

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

После этого слайда возвращаемся к таблице указанной на слайде 7 и в соответствии с оговоренными выше условиями закрашиваем рассматриваемую ячейку желтым или зеленым цветом.

Итак, мы будем закрашивать все полученные результаты. Всего получим девять закрашенных ячеек желтого и зеленого цвета. <Слайд 10>.

В Презентации2.ppt используются гиперссылки в виде прямоугольников с надписью выигрыш зеленого и желтого цвета.

Результаты второго (вторых) докладчика (докладчиков). <Слайд 16>, <Слайд 16>, <Слайд 11>.

Результаты третьего (третьих) докладчика (докладчиков). <Слайд 17>, <Слайд 17>, <Слайд 12>.

Результаты четвертого (четвертых) докладчика (докладчиков). <Слайд 18>, <Слайд 18>, <Слайд13>.

Результаты пятого (пятых) докладчика (докладчиков). <Слайд 19>, <Слайд 19>, <Слайд 14>.

Результаты шестого (шестых) докладчика (докладчиков). <Слайд 20>, <Слайд 15>.

Мы получили дерево игры, но пока что еще не получили ответа ни на один вопрос, который у нас спрашивают - кто выигрывает, как он при этом должен ходить и почему это так. Ответы на эти вопросы мы получим из анализа дерева игры.

Позиции, выделенные желтым цветом в таблице - выигрыш первого игрока; позиции, выделенные зеленым цветом в таблице - выигрыш второго игрока; То есть, если игрок в нее перейдет, то он сразу выиграет.

Значит, предыдущая позиция (из которой игрок ходил) является для него выигрышной (из этой позиции игрок может пойти так, чтобы выиграть).

Из полученной таблицы мы можем сделать вывод, что выигрывает второй игрок, при любом варианте хода первого игрока. (Предложить этот вывод сделать ученикам).

Показать учащимся, как правильно оформить ответ. <Слайд 21>, <Слайд 22>.

Учащиеся заполняют Приложения №3, которое является неполным деревом игры и сдают учителю вместе с Приложением №2. <Слайд 23>, <Слайд 24>.

7. Домашнее задание. (2 мин.). (Приложение 4). <Слайд 1>).