infoegehelp.ru

Успешно сдать ЕГЭ по информатике
  • Главная
  • Контакты
  • Карта сайта
  • Помощь сайту
Важно
  • Демо варианты ЕГЭ
  • Учим числа: 2 в степени
  • Биты, байты, килобайты
Решение задач
  • Задачи вне основных разделов информатики
Разделы информатики
  • 2011-12-18-14-33-54Системы счисления
  • 2011-12-18-16-45-20Алгебра логики
  • 2011-12-18-16-55-26Программирование
  • 2011-12-18-16-53-40Кодирование информации
  • 2011-12-18-16-56-19Компьютерные сети и Интернет
  • -excelЭлектронные таблицы (Excel)
  • 2011-12-18-16-57-50Базы данных
  • 2011-12-18-16-58-50Графы
  • 2011-12-18-17-00-15Файловая система
  • Устройство компьютера
  • ПО компьютера

Разбор задачи C4 (демо ЕГЭ 2004)

Два игрока играют в следующую игру. Перед ними лежат три кучки камней, в первой из которых 2, во второй – 3, в третьей – 4 камня.  У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет по два камня в каждую из куч. Выигрывает игрок, после хода которого либо в одной из куч становится не менее 15 камней, либо общее число камней во всех трех кучах становится не менее 25. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение:

Введем обозначения:

х - количество камней в первой куче,

у - количество камней во второй куче,

z - количество камней в третьей куче.

Позиция игрока: (х, у, z).

Варианты хода игроков: (х*2,у,z), (х,у*2,z), (х,у,z*2), (х+2,у+2,z+2).

Игрок выйграет, когда

  • число камней в одной из куч ≥15 (x≥15 или y≥15, или z≥15)
  • число камней в 3-х кучах станет ≥25 (х+у+z≥25).
Изобразим ход игры в виде дерева решений. Необходимо ветвить дерево до того момента, когда все варианты последнего хода станут выйгрышными.

После первого хода дерево будет выглядеть так:

Задача С4 ЕГЭ по информатике 2004 первый ход

На дереве изображены все возможные варианты ходов.

После первых 2-х ходов дерево будет выглядеть так:

Задача С4 ЕГЭ по информатике 2004 второй ход

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

Когда 2-й игрок совершает 2-й ход, он выигрывает, когда попадает в позицию: (2,3,16), т.к. z в этом случае больше 15. На рисунке выйгрышная позиция 2-го игрока выделены сплошной рамкой.

Смотрим предыдущий ход. Чтобы 2-й игрок не выйграл, 1-й игрок на 1-м ходе не должен идти в позицию (2,3,8). Он может идти в остальные позиции. Запретная позиция для 1-го игрока перечеркнута красным:

Задача С4 ЕГЭ по информатике 2004 запретная позиция 1-го игрока

Рассматривая дальнейшие ходы не будем ветвить позиции, которые идут из позиции (2,3,8). После 3-х ходов дерево будет выглядеть так:

Задача С4 ЕГЭ по информатике 2004 третий ход

Для того чтобы в одной из куч стало ≥15 камней (выйгрышный ход), необходимо чтобы на предыдущем ходу в данной куче было ≥8 камней (8*2=16). Поэтому прежде чем рассчитывать все варианты хода, необходимо просмотреть все x,y,z и на наличие числа ≥8. Если такое число будет найдено, то следующий ход будет получен удвоением найденного x,y или z. Если же не будет найдено, то будут рассмотрены все возможные ходы. Например, чтобы выиграть 1-й игрок из позиции (8,3,4) обязательно пойдет в (16,3,4), а не в (8,6,4), например.

Когда 1-й игрок совершает 3-й ход, он выигрывает, когда попадает в позиции: (16,3,4), (4,3,16), (2,24,4), (2,6,16), (4,16,6), (16,5,6), (4,20,5), (4,5,24), (6,7,16), т.к. х, у или z в этих случаях ≥15. На рисунке выйгрышные позиции 1-го игрока на 3-м ходу выделены сплошной рамкой.

Смотрим предыдущий ход. Чтобы 1-й игрок не выйграл, 2-й игрок на 2-м ходе не должен идти в позиции (8,3,4), (4,3,8), (2,12,4), (2,6,8), (4,8,6), (8,5,6), (4,10,6), (4,5,12), (6,7,8). Он может идти в остальные позиции. Запретные позиции для 2-го игрока перечеркнуты красным:

Задача С4 ЕГЭ по информатике 2004 запретные позиции 2-го игрока

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

Рассмотрим ситуацию, когда 1-й игрок пойдет в одну из позиций: (4,3,4) или (2,6,4).

Рассматривая дальнейшие ходы не будем ветвить позиции, которые идут из позиций (8,3,4), (4,3,8), (2,12,4), (2,6,8), (4,8,6), (8,5,6), (4,10,6), (4,5,12), (6,7,8). После 4-х ходов дерево будет выглядеть так:

Задача С4 ЕГЭ по информатике 2004 четвертый ход

Из рисунка видно, что любой ход 2-ого игрока на 4-м ходу был бы выйгрышным при ошибочном 1-м ходе 1-го игрока.

Представим решение также в виде таблицы (выйгрышные ходы выделены розовым):


1 ход2 ход3 ход
Старт1-й игрок
(выйгрышный ход)
2-й игрок
(все ходы)
1-й игрок
(выйгрышный ход
(один из вариантов))
2,3,4
4,5,6
8,5,6
16,5,6
4,10,6
4,20,6
4,5,12
4,5,24
6,7,8
6,7,16

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

Перейти к другим задачам.

 

Rambler's Top100

© Латыпова В, 2012-2015. Все права защищены.
Копирование материалов сайта только с разрешения администрации сайта