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Файловая система
  • Устройство компьютера
  • ПО компьютера

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

Время выполнения-30 мин, уровень сложности-высокий

Два игрока играют в следующую игру. На координатной плоскости стоит фишка. В начале игры фишка находится в точке с координатами (–2,–1). Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3,y), (x,y+4), (x+2,y+2). Игра заканчивается, как только расстояние от фишки до начала координат превысит число 9. Выигрывает игрок, который сделал последний ход. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Решение:

Чтобы кто-то из игроков выйграл,он должен попасть в такую координату, где х2+у2>92, т.е. х2+у2>81.

Изобразим ход игры в виде дерева решений. После первых 2-х ходов оно будет выглядеть так:

задача C3 ЕГЭ по информатике 2010 второй ход

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

Когда 1-й игрок совершает 3-й ход, он выигрывает, когда попадает в координату: -2,11, т.к. сумма квадратов х и у в этих случаях больше 81. На рисунке выйгрышные позиции 1-го игрока выделены сплошной рамкой:

задача C3 ЕГЭ по информатике 2010 третий ход

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

задача C3 ЕГЭ по информатике 2010 запретные позиции второго игрока

Рассматривая дальнейшие ходы не будем ветвить позиции, которые идут из позиции -2,7.Когда 2-й игрок совершает 4-й ход, он выигрывает, когда попадает в координаты: 10,-1, 9,1, 1,11, 3,9, 2,11, 4,9, 6,7, т.к. сумма квадратов х и у в этих случаях больше 81. На рисунке выйгрышные позиции 2-го игрока на 4-м ходу выделены сплошной рамкой:

задача C3 ЕГЭ по информатике 2010 четвертый ход

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

задача C3 ЕГЭ по информатике 2010 запретные позиции первого игрока

Будем ветвить только позиции, идущие из позиций 4,3 и 5,3:

задача C3 ЕГЭ по информатике 2010 пятый ход

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

Теперь необходимо найти выйгрышные ходы игрока на 3-м ходу (пойдем с конца дерева решений в начало). Это позиции 4,3 и 5,3 3-го хода. На рисунке выше они выделены пунктирной рамкой. Как бы не пошел 2-й игрок на 2-м ходу, у 1-го игрока есть выйгрышные ходы 4,3 и 5,3.

Необходимо определить выйгрышный ход 1-го игрока на 1-м ходу. Если он пойдет в позицию -1,1, то как бы не пошел на следующий ход 2-й игрок, у 1-го есть возможность попасть в выйгрышную позицию 4,3 или 5,3. Если 1-й игрок пойдет в позицию -2,3 или 0,1, 2-й игрок может пойти в позицию 0,5 на 3-м ходу, и тогда 1-й игрок не сможет сделать выйгрышный ход. На рисунке розовым выделен ход 2-го игрока в позицию 0,5, из которого нет выйгрышных ходов 4,3 и 5,3 для 1-го игрока:

задача C3 ЕГЭ по информатике 2010 ход второго игрока

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


1 ход2ход3 ход4 ход5 ход
Старт1-й игрок
(выйгрышный ход)
2-й игрок
(все ходы)
1-й игрок
(выйгрышный ход)
2-й игрок
(все ходы)
1-й игрок
(выйгрышный ход)
-2,-1 1,-1 4,-1 4,3 7,3 10,3, 7,7, 9,5
4,7 7,7, 4,11, 6,9
6,5 9,5, 6,9, 8,7
1,3 4,3 те же ходы, что описаны выше
3,1 5,3 8,3 11,3, 8,7, 10,6
5,7 8,7, 5,11, 7,9
7,5 10,5, 7,9, 9,7

Выигрывает 1-й игрок. Его 1-й ход- поставить фишку в точку с координатами (-1,1).

Перейти к С3-2012.

Перейти к С3-2011.

Перейти к С3-2009.

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

 

Rambler's Top100

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