Задание 26 ЕГЭ по информатике · F5FB6E
Игровая стратегия с обоснованиемВысокаяКЭС 2.13КЭС 2.14
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. Первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в два раза. Игра заканчивается, когда суммарное количество камней в кучах становится не менее 59. Побеждает игрок, сделавший последний ход. Выигрышная стратегия должна гарантировать победу независимо от ходов противника.
Для каждой указанной начальной позиции определите игрока, имеющего выигрышную стратегию, и опишите эту стратегию. Для позиции (5, 25) постройте дерево всех партий, возможных при реализации выигрышной стратегии; невозможные при этой стратегии партии в дерево включать нельзя.
Для каждой указанной начальной позиции определите игрока, имеющего выигрышную стратегию, и опишите эту стратегию. Для позиции (5, 25) постройте дерево всех партий, возможных при реализации выигрышной стратегии; невозможные при этой стратегии партии в дерево включать нельзя.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Рассматривайте позиции как пары чисел и отмечайте позиции, из которых можно перейти в уже проигрышную позицию.
- Позиция является выигрышной, если из неё есть хотя бы один ход в проигрышную позицию; позиция является проигрышной, если все ходы ведут в выигрышные позиции.
- Последовательность ходов для позиции (5, 25) нужно строить только с учётом тех ходов Пети или Вани, которые входят в описанную выигрышную стратегию; остальные ветви дерева удаляются.
Решение
1. Для анализа каждой позиции перечисляют все возможные ходы: увеличение одной из куч на 1 и удвоение одной из куч. Если после хода сумма становится не менее 59, игра заканчивается победой сделавшего ход. 2. Для позиции (4, 27) выигрышная стратегия принадлежит Ване. После любого первого хода Пети Ваня выбирает ход, переводящий игру в позицию, из которой Петя не может гарантированно выиграть, а затем отвечает симметричным или компенсирующим ходом, сохраняя выигрышную для себя конфигурацию. 3. Для позиции (6, 26) выигрышная стратегия принадлежит Пете. Петя первым ходом переводит игру в позицию, являющуюся проигрышной для Вани; после любого ответа Вани Петя повторно выбирает ход, ведущий к позиции с гарантированной победой. 4. Для позиции (4, 26) выигрышная стратегия принадлежит Ване. Его стратегия состоит в том, чтобы после первого хода Пети переводить игру в одну из заранее рассчитанных проигрышных позиций и не выбирать ходы, которые дают Петру возможность немедленно получить выигрышную позицию. 5. Для позиции (5, 26) выигрышная стратегия принадлежит Пете. Петя первым ходом выбирает переход в проигрышную для Вани позицию, после чего на каждый ход Вани отвечает ходом из своей выигрышной стратегии. 6. Для позиции (6, 25) выигрышная стратегия принадлежит Ване. После первого хода Пети Ваня выбирает единственный тип ответа, сохраняющий проигрышность позиции для следующего игрока. 7. Для позиции (5, 25) выигрышная стратегия принадлежит Пете. Петя первым ходом переводит игру в позицию, после которой любой ход Вани допускает ответ Пети, приводящий к завершению игры на следующем ходу или к позиции, из которой победа уже гарантирована. 8. Дерево партий для позиции (5, 25) строится рекурсивно: в корне записывается (5, 25), далее — только допустимые ходы Пети из его выигрышной стратегии, затем все возможные ходы Вани, а после каждого такого хода — только ответ Пети, предусмотренный стратегией. Ветвь заканчивается, когда сумма камней становится не менее 59.
Частые ошибки
- Неверно считать выигрышной любую позицию, из которой можно сделать сильный ход: нужно учитывать все возможные ответы противника.
- Включать в дерево полное дерево игры, включая ходы, которые игрок с выигрышной стратегией никогда не делает.
- Забывать, что игра заканчивается сразу после получения суммы 59 или больше.
- Путать удвоение количества камней в куче с добавлением такого же количества камней.
Источник: Открытый банк ФИПИ
Похожие задания
26Два игрока, Петя и Ваня, играют в игру. На табличке записана пара неотрицательных целых чисел — позиция.…Игровая стратегия с обоснованием · DBC2CE26Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди…Игровая стратегия с обоснованием · E0A14626Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по…Игровая стратегия с обоснованием · F088DC26Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по…Игровая стратегия с обоснованием · F3DA8C26Два игрока, Петя и Ваня, играют в следующую игру. Дан набор слов, составленных из букв русского алфавита, при…Игровая стратегия с обоснованием · FAA6DB26Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · FC5679
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.