Задание 19. Анализ алгоритма логической игры: ЕГЭ по информатике

Задание 19 ЕГЭ по информатике проверяет умение анализировать алгоритм логической игры с двумя кучами камней. Нужно найти минимальное значение S, при котором Ваня (второй игрок) выигрывает своим первым ходом, то есть после любого хода Пети Ваня может сделать ход, приводящий к сумме камней ≥ 133.…

Что нужно знать

Игра: две кучи, начальные значения (17, S), 1 ≤ S ≤ 115.
Ходы: добавить 4 камня в одну из куч ИЛИ удвоить количество камней в одной из куч.
Игра завершается, когда суммарное количество камней в двух кучах становится ≥ 133.
Победитель — тот, кто сделал последний ход (первым получил сумму ≥ 133).
Петя ходит первым, Ваня — вторым.
Ваня выиграл своим первым ходом — это значит, что после хода Пети Ваня может сделать ход, приводящий к сумме ≥ 133, при любом возможном ходе Пети.

Термины и понятия

Игровая позиция: пара чисел (a, b) — количество камней в первой и второй кучах.
Ход: добавление 4 камней в одну из куч или удвоение количества камней в одной из куч.
Выигрышная позиция: позиция, из которой игрок, делающий ход, может сразу достичь суммы ≥ 133.
Выигрышная стратегия: способность игрока выиграть при любых ходах противника.
Сумма камней: a + b, где a и b — количества камней в кучах.
Порог выигрыша: 133 (сумма, при которой игра завершается).
Первый ход Пети: ход, который делает Петя из начальной позиции (17, S).
Первый ход Вани: ход, который делает Ваня после хода Пети.

Частые ошибки

Неверное определение условия завершения игры: путают сумму ≥ 133 с суммой > 133 или с количеством камней в одной куче.
Путают, кто делает первый ход и кто выигрывает своим первым ходом: Петя ходит первым, Ваня — вторым.
Не учитывают все возможные ходы: забывают про удвоение или добавление 4 камней в каждую из куч.
Ошибка в определении выигрышной позиции: считают, что Ваня выигрывает, если может достичь суммы ≥ 133 хотя бы одним ходом, но не проверяют все ходы Пети.

Как пройти тему

В курсе «Информатика» тема «Задание 19. Анализ алгоритма логической игры» занимает 5 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Задание 18. Системы счисления
Следующая тема: Задание 20. в тексте части 3 название навыка не приведено

Все темы: ЕГЭ по информатике