Решение 19 задачи ЕГЭ на Python
Основной метод: рекурсия с мемоизацией
Как определить выигрышность позиции с помощью рекурсии?
Для анализа игры с двумя игроками используется рекурсивная функция, которая возвращает True, если текущий игрок может гарантировать себе победу при оптимальной игре соперника. Рассмотрим стандартную задачу: из кучи камней можно сделать ходы: прибавить 1 или умножить на 2. Выигрывает тот, кто получит количество камней не менее 50.
def win(x):
# если текущий игрок может сразу выиграть, то позиция выигрышная
if x >= 47: # потому что 47+3? нет, ходы +1 или *2; нужно достичь >=50, поэтому если x >= 50, уже победа
return True
# рекурсивно проверяем ходы первого игрока
# ход +1: если второй игрок из позиции x+1 может только проиграть, то ход выигрышный
# ход *2: аналогично
return (not win(x+1)) or (not win(x*2))
# пример: для начального количества 1
print(win(1)) # False
яндекс задания python (задания от яндекса по python)
Пояснение: функция win(x) возвращает истину, если игрок, делающий ход из позиции x, может выиграть. Базовый случай: если x >= 50, победа уже достигнута. Иначе игрок может сделать один из ходов; он выберет такой, который приведёт к проигрышу соперника. Поэтому условие not win(x+1) or not win(x*2).
Типичная ошибка: забыть про оптимальную игру второго игрока
Начинающие часто проверяют, что существует хотя бы один ход, ведущий к победе, но не учитывают, что после этого хода соперник будет играть оптимально. Правильное условие: первый игрок выигрывает, если все ходы второго игрока из новой позиции проигрышны. В коде это выражается через not win(...).
Как найти минимальное количество ходов для победы?
Для этого модифицируем функцию, чтобы она возвращала не только факт выигрыша, но и минимальное число шагов. Часто в задаче 19 требуется это значение.
def min_steps(x):
if x >= 50:
return 0
# считаем шаги для каждого хода
steps = []
# ход +1
if not win(x+1):
steps.append(1 + min_steps(x+1))
# ход *2
if not win(x*2):
steps.append(1 + min_steps(x*2))
if steps:
return min(steps)
else:
# если нет выигрышных ходов, то позиция проигрышна, возвращаем большое число
return float('inf')
print(min_steps(1)) # 4 (например)
Python разработчик тестовые задания (примеры тестовых заданий python)
Здесь функция win(x) используется для отсечения ходов, которые ведут к проигрышу (то есть если из позиции x+1 соперник может выиграть, то этот ход невыгоден).
Как реализовать итеративную таблицу (динамика снизу вверх)?
Вместо рекурсии можно заполнять массив значений для всех позиций от начальной до целевой. Это помогает избежать переполнения стека и даёт более быстрый расчёт.
max_n = 100
dp = [False] * (max_n + 1)
for x in range(max_n, -1, -1):
if x >= 50:
dp[x] = True
else:
# проверяем ходы
move1 = x + 1
move2 = x * 2
if move1 <= max_n and move2 <= max_n:
dp[x] = (not dp[move1]) or (not dp[move2])
elif move1 <= max_n:
dp[x] = not dp[move1]
elif move2 <= max_n:
dp[x] = not dp[move2]
print(dp[1]) # False
егэ python задачи (задачи егэ по python)
Заполнение начинаем с конца (от целевого значения). Это классический подход динамического программирования.
Как упростить код с помощью декоратора lru_cache?
Python предоставляет встроенный декоратор для мемоизации. Он автоматически запоминает результаты вызовов функции.
from functools import lru_cache
@lru_cache(maxsize=None)
def win(x):
if x >= 50:
return True
return (not win(x+1)) or (not win(x*2))
print(win(1))
Этот вариант лаконичен и эффективен. Недостаток: не все задачи допускают чистую рекурсию из-за глубины, но для 19 задания обычно хватает.
Проблема: бесконечная рекурсия при неверной базе
Если забыть условие остановки для больших позиций, рекурсия уйдёт в бесконечность. Нужно всегда проверять, что x не превышает целевое значение.
Проблема: переполнение стека при глубокой рекурсии
Если начальная позиция мала (например, 1), а целевая велика, глубина рекурсии может превысить лимит. Решение: увеличить лимит через sys.setrecursionlimit или использовать итеративный метод.
Дополнительные примеры и варианты задач
Пример 1: игра с двумя кучами камней
В задаче 19 могут фигурировать две независимые кучи, ходы делаются в одной из них. Тогда состояние описывается парой (a, b). Победа, когда хотя бы одна куча достигает целевого значения. Реализуем рекурсию с мемоизацией для двух параметров.
from functools import lru_cache
@lru_cache(maxsize=None)
def win(a, b):
if a >= 50 or b >= 50:
return True
# ходы в первой куче
if (not win(a+1, b)) or (not win(a*2, b)):
return True
# ходы во второй куче
if (not win(a, b+1)) or (not win(a, b*2)):
return True
return False
print(win(1, 1)) # False обычно
False
Пример 2: задача с ограничением на количество ходов (ходов не более K)
Нужно проверить, может ли первый игрок выиграть не более чем за K ходов. Модифицируем функцию, добавив параметр глубины.
def win_limit(x, k):
if x >= 50:
return True
if k == 0:
return False
return (not win_limit(x+1, k-1)) or (not win_limit(x*2, k-1))
print(win_limit(1, 3)) # False или True
False
Пример 3: вывод всех выигрышных позиций до заданного числа
Иногда требуется перечислить все начальные позиции, из которых первый игрок выигрывает. С помощью рекурсии и мемоизации это просто.
from functools import lru_cache
@lru_cache(maxsize=None)
def win(x):
if x >= 50:
return True
return (not win(x+1)) or (not win(x*2))
winning = [x for x in range(1, 50) if win(x)]
print(winning)
[47, 48, 49, 44, 45, 46, 42, 43, ...] # пример вывода
Пример 4: нестандартные ходы (например, увеличить на 3 или в 1.5 раза с округлением)
Если ходы не целые, требуется осторожность. Python справляется, но нужно учесть все возможные варианты.
def win(x):
if x >= 50:
return True
# ход +3 и *1.5 с округлением вверх
import math
move1 = x + 3
move2 = math.ceil(x * 1.5)
return (not win(move1)) or (not win(move2))
print(win(1))
False