как решать 19 задание егэ информатика

By /

Задание 19 в ЕГЭ по информатике — это задача на разработку и описание алгоритма, обычно из области рекурсивных вычислений, поиска или перебора вариантов. Это одно из самых сложных заданий в ЕГЭ, которое проверяет не только знание программирования, но и умение логически мыслить и анализировать.

📌 Что представляет собой задание 19?

Задание 19 формулируется так, что нужно:

  • Придумать алгоритм, который выполняет определённую задачу.

  • Иногда — составить функцию (чаще рекурсивную), которая считает количество способов преобразования, например, из числа A в число B, используя допустимые операции.

  • В других случаях — описать стратегию игры, выигрышную или проигрышную позицию, на основании правил.

Пример формулировки (упрощённо):

Сколько существует программ (последовательностей команд), которые преобразуют число A в число B, используя только операции +1 и *2? При этом промежуточные значения не должны превышать C.

Или:

Петя и Ваня играют в игру. На доске лежит куча камней. За ход игрок может добавить 1, 2 или удвоить. Кто выигрывает при идеальной игре?

🔑 Какие бывают типы задач?

Задание 19 можно классифицировать на три основные группы:

1. Рекурсивные преобразования (количество путей)

  • Нужно посчитать, сколькими способами можно превратить одно число в другое с помощью определённых операций.

  • Используются рекурсия или динамическое программирование.

🧠 Основная идея:

Если ты можешь прийти в точку B из A через X операций, то ты можешь подумать: какие предыдущие шаги могли привести в B?

📌 Пример:

python
def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    return f(x + 1, y) + f(x * 2, y)

print(f(2, 10))

🟡 Подзадачи:

  • Иногда накладываются ограничения: запрещённые числа, промежуточные условия.

  • Нужно фильтровать пути (например, только такие, которые проходят через определённую точку).

2. Игровые задачи (выигрышные/проигрышные позиции)

  • Есть игра с чёткими правилами.

  • Нужно определить, кто выигрывает при идеальной игре.

  • Применяются деревья ходов, мемоизация, анализ позиций (выигрышная/проигрышная).

📌 Ключевые понятия:

  • Выигрышная позиция — игрок может совершить ход, после которого противник окажется в проигрышной позиции.

  • Проигрышная позиция — любой ход ведёт в выигрышную позицию соперника.

🧠 Суть:

Рассматриваем все возможные ходы и рекурсивно определяем для каждой позиции, можно ли из неё выиграть.

📌 Пример:

python
def game(x):
    if x >= 21:
        return "W"
    if any(game(x + m) == "W" for m in (1, 2, x * 2)):
        return "P1"
    if all(game(x + m) == "P1" for m in (1, 2, x * 2)):
        return "V1"
    if any(game(x + m) == "V1" for m in (1, 2, x * 2)):
        return "P2"
    return "V2"

for s in range(1, 21):
    print(s, game(s))

Обозначения:

  • W: выигрышная позиция (21 или больше).

  • P1: первый игрок выигрывает первым ходом.

  • V1: второй выигрывает, если первый ошибся.

  • P2, V2: стратегии второго хода.

3. Поиск оптимальных стратегий/решений

  • Нужно найти, например:

    • минимальное/максимальное число ходов,

    • количество программ,

    • оптимальные параметры игры.

Решается через:

  • Рекурсивный перебор,

  • Хранение состояний,

  • Динамику (мемоизация).

🛠 Как решать задание 19 пошагово?

Шаг 1: Внимательно прочитай условие

  • Определи:

    • Что задано (начальное и конечное состояние),

    • Что можно делать (операции),

    • Что нужно найти (кол-во путей, выигрыш, стратегия и т.п.),

    • Есть ли ограничения (например, промежуточные условия, запрещённые значения).

Шаг 2: Типизируй задачу

  • Это рекурсивное преобразование, игра, или оптимизация?

Шаг 3: Составь рекурсивную модель

  • Для задач с путями — функция f(x, y) (откуда-куда).

  • Для игр — дерево возможных ходов и метки (выигрыш/проигрыш).

Шаг 4: Упрости модель

  • Попробуй решить руками на простом примере (например, A = 2, B = 5).

  • Пойми структуру решения.

Шаг 5: Реализуй в коде (Python)

📋 Пример 1 — Сколько программ переводят 2 в 13 с помощью +1 и *2?

python
def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    return f(x + 1, y) + f(x * 2, y)

print(f(2, 13))  # Ответ: количество программ

📋 Пример 2 — Игра: Из 5 до 30. Ход: +1, +2, *2. Кто выигрывает?

python
def game(x):
    if x >= 30:
        return 'W'
    if any(game(x + m) == 'W' for m in (1, 2, x * 2)):
        return 'P1'
    if all(game(x + m) == 'P1' for m in (1, 2, x * 2)):
        return 'V1'
    if any(game(x + m) == 'V1' for m in (1, 2, x * 2)):
        return 'P2'
    return 'V2'

for s in range(1, 30):
    print(s, game(s))

🧠 Полезные советы:

  • Используй мемоизацию (@lru_cache) для ускорения:

python
from functools import lru_cache

@lru_cache(None)
def f(x, y):
    ...

  • Рисуй дерево решений на бумаге.

  • Проверяй код на простых примерах (2–5 шагов).

  • Чётко расписывай базу рекурсии.

  • Запоминай типовые паттерны (операции, стратегии).

📚 Что почитать и где потренироваться?

Если хочешь — могу разобрать конкретную задачу 19 из демо-версии, реального варианта или тренировочной. Напиши её сюда — разложу по полочкам.

Scroll to Top

Карта сайта