Задание 23 ЕГЭ информатика

1. Введение

Главная идея: мы не ищем одну подходящую последовательность команд, а считаем все возможные пути от начального числа к конечному.

В задании №23 исполнитель преобразует число на экране с помощью нескольких команд.

Программой называется последовательность команд, а траекторией вычислений — все числа, которые появляются на экране от начала до конца.

Нужно определить, сколько разных программ переводят исходное число A в число B. В условии может быть дополнительное требование: траектория не должна содержать число C или, наоборот, обязана через него пройти.

Задание проверяет умение:

представлять команды исполнителя как переходы между числами;
считать количество путей в ориентированном графе;
использовать принцип сложения и принцип умножения;
задавать базовые случаи рекурсивной функции;
переводить условие задачи в короткую программу на Python.

Каждая ветвь соответствует первому выбору команды; дальше ветвление продолжается до числа B.

Важно: приведённый ниже шаблон предназначен для задач, где все команды увеличивают число и A < B. Тогда значение, превысившее B, уже не сможет вернуться назад.

2. Теория: как решать задачу вручную

Удобно представить числа как вершины графа, а команды — как стрелки. Тогда требуется посчитать количество путей из A в B.

Шаг 1. Задаём начало

Обозначим через K(x) количество программ, которые переводят A в x.

Для стартового числа всегда записываем:

K(A) = 1

Есть один способ оказаться в A, не выполняя ни одной команды.

Шаг 2. Находим предшественников каждого числа

Для очередного числа x выясняем, из каких меньших чисел в него можно попасть одной командой. Затем складываем уже найденные количества путей из всех предшественников.

Для команд:

«прибавить 1»;
«умножить на 2»;
«умножить на 3»

возможны переходы из:

x - 1
x / 2
x / 3

Деление учитываем только тогда, когда получается целое число не меньше A.

Например, в число 6 можно прийти из 5, 3 и 2, поэтому количества путей складываются.

Шаг 3. Доходим до конечного числа

Продолжаем вычисления по возрастанию чисел. Значение K(B) и будет искомым количеством программ.

Пример: исполнитель переводит число 2 в число 10 командами +1, ×2 и ×3.

n	2	3	4	5	6	7	8	9	10
K(n)	1	1	2	2	4	4	6	7	9

В конечной вершине записано 9, значит существует 9 программ.

Как учитывать дополнительное число C

Траектория не должна содержать C

Считаем число C запрещённой вершиной:

K(C) = 0

и не продолжаем из неё ни один путь.

В рекурсивном коде та же идея задаётся условием x == C, при котором функция возвращает 0.

Запрещённая вершина обрывает каждую попавшую в неё ветвь.

Траектория обязана содержать C

Любая подходящая программа состоит из двух независимых частей:

путь из A в C;
путь из C в B.

Поэтому используем принцип умножения:

Количество = K(A → C) · K(C → B)

Каждый первый участок можно соединить с каждым вторым участком.

3. Теория: как решать задачу кодом

Создадим функцию F(x, y), которая возвращает количество программ, переводящих текущее число x в конечное число y.

def F(x, y):
    if x > y:
        return 0

    if x == y:
        return 1

    if x < y:
        return F(x + 1, y) + F(x * 2, y) + F(x * 3, y)

Что делает каждая часть кода:

x > y — путь вышел за конечное число; этот вариант не подходит, поэтому возвращаем 0;
x == y — конечное число достигнуто; найден ровно один подходящий путь, поэтому возвращаем 1;
x < y — пробуем каждую возможную следующую команду и складываем результаты всех ветвей.

Схема полностью повторяет порядок проверок в функции.

В строке return должны стоять именно команды из условия. Если команды другие, меняем только рекурсивные вызовы, сохраняя общий принцип.

4. Прототипы задач

Прототип 1. Базовый

Условие

Исполнитель преобразует число на экране. У исполнителя есть три команды:

A. прибавить 1;
B. умножить на 2;
C. умножить на 3.

Сколько существует программ, для которых при исходном числе 2 результатом является число 30?

Решение

Дополнительных ограничений нет, поэтому используем базовую функцию и один вызов F(2, 30).

def F(x, y):
    if x > y:
        return 0

    if x == y:
        return 1

    if x < y:
        return F(x + 1, y) + F(x * 2, y) + F(x * 3, y)


print(F(2, 30))

Ответ: 152

Прототип 2. Траектория не проходит через C

Условие

Исполнитель имеет команды «прибавить 1», «умножить на 2», «умножить на 3».

Сколько программ переводят число 2 в число 30, если траектория вычислений не должна содержать число 8?

Решение

Число 8 запрещено. Поэтому в первом условии добавляем or x == 8.

Как только ветвь приходит в 8, функция возвращает 0 и больше эту ветвь не продолжает.

def F(x, y):
    if x > y or x == 8:
        return 0

    if x == y:
        return 1

    if x < y:
        return F(x + 1, y) + F(x * 2, y) + F(x * 3, y)


print(F(2, 30))

Ответ: 80

Прототип 3. Траектория проходит через C

Условие

Исполнитель имеет команды «прибавить 1», «умножить на 2», «умножить на 3».

Сколько программ переводят число 2 в число 30, если траектория вычислений должна содержать число 8?

Решение

Сначала считаем программы из 2 в 8, затем программы из 8 в 30.

Каждый первый участок можно соединить с каждым вторым, поэтому результаты умножаем.

def F(x, y):
    if x > y:
        return 0

    if x == y:
        return 1

    if x < y:
        return F(x + 1, y) + F(x * 2, y) + F(x * 3, y)


print(F(2, 8) * F(8, 30))

Получаем:

F(2, 8) = 6
F(8, 30) = 12

6 · 12 = 72

Ответ: 72

Проверка трёх прототипов

Все программы из 2 в 30 делятся на две непересекающиеся группы:

траектория содержит 8;
траектория не содержит 8.

Поэтому ответы должны удовлетворять равенству:

80 + 72 = 152

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

5. Практика с решениями на Python

В каждой задаче сначала определяем направление движения и доступность команд. После этого меняем в шаблоне только:

граничное условие;
рекурсивные вызовы;
если нужно — способ объединения частей пути.

Практика 1. Команды +2 и +7

Условие

Исполнитель имеет две команды: «прибавить 2» и «прибавить 7».

Сколько программ переводят число 5 в число 49?

Разбор

Обе команды увеличивают число. Значит, если x стал больше 49, вернуться к цели уже нельзя.

В последней строке функции записываем ровно два перехода из условия:

x + 2
x + 7

def F(x, y):
    if x > y:
        return 0

    if x == y:
        return 1

    return F(x + 2, y) + F(x + 7, y)


print(F(5, 49))

Ответ: 639

Практика 2. Движение вниз, через 10, но не через 7

Условие

Исполнитель имеет команды:

«вычесть 1»;
«вычесть 4»;
«взять целую часть от деления на 2».

Сколько программ переводят 25 в 3, если траектория содержит 10 и не содержит 7?

Что меняется по сравнению с базовым шаблоном

числа уменьшаются, поэтому неподходящая ветвь определяется условием x < y, а не x > y;
число 7 запрещено, поэтому при x == 7 функция возвращает 0;
число 10 обязательно: отдельно считаем пути 25 → 10 и 10 → 3, затем перемножаем результаты;
в рекурсивной строке записываем команды x - 1, x - 4 и x // 2.

def F(x, y):
    if x < y or x == 7:
        return 0

    if x == y:
        return 1

    return F(x - 1, y) + F(x - 4, y) + F(x // 2, y)


print(F(25, 10) * F(10, 3))

Умножение в print не является украшением кода: оно заставляет каждую учтённую программу пройти через 10.

Запрет на 7 остаётся внутри функции и действует на всех участках пути.

Ответ: 546

Практика 3. Основная волна 2026 — «Поменяй местами»

Условие

Исполнитель имеет команды «прибавь 1» и «поменяй местами».

Вторая команда применяется только тогда, когда цифра десятков меньше цифры единиц, и меняет две последние цифры местами.

Сколько программ переводят 100 в 150?

Пример: 124 превращается в 142, потому что 2 < 4. Цифра сотен не меняется.

Разбираем решение по шагам

Сохраняем обычные базовые случаи. Обе команды увеличивают число: +1 очевидно, а перестановка при десятки < единицы тоже даёт большее число. Поэтому x > y означает неудачную ветвь.
Получаем цифру единиц:

ed = x % 10

Для числа 124 это 4.

Получаем цифру десятков:

dec = x // 10 % 10

Для числа 124 это 2.

Команда +1 доступна всегда, поэтому сначала записываем:

s = F(x + 1, y)

Переменная s хранит уже найденное количество продолжений.

Проверяем условие второй команды:

if dec < ed:

Если оно ложно, ветвь с перестановкой создавать нельзя.

Собираем новое число:

new_x = x // 100 * 100 + ed * 10 + dec

Здесь:

x // 100 * 100 сохраняет сотни и старшие разряды;
ed * 10 ставит бывшую единицу в разряд десятков;
dec ставит бывший десяток в разряд единиц.

Для 124 получаем:

100 + 40 + 2 = 142

Добавляем количество путей из нового числа:

s += F(new_x, y)

Затем возвращаем общую сумму:

return s

def F(x, y):
    if x == y:
        return 1

    if x > y:
        return 0

    ed = x % 10
    dec = x // 10 % 10

    s = F(x + 1, y)

    if dec < ed:
        new_x = x // 100 * 100 + ed * 10 + dec
        s += F(new_x, y)

    return s


print(F(100, 150))

Почему здесь неудобна обычная строка:

return F(...) + F(...)

Вторая команда разрешена не для каждого x. Сначала считаем обязательную ветвь +1, а условную ветвь добавляем только после проверки цифр.

Ответ: 35

Практика 4. Основная волна 2026 — «Измени цифру»

Условие

Исполнитель имеет команды «прибавь 1» и «измени цифру».

Вторая команда доступна, если в записи числа есть хотя бы одна цифра 1, и заменяет каждую цифру 1 на 2.

Сколько программ переводят 11 в 92?

Строковый метод replace меняет сразу все вхождения:

101 → 202

а не:

101 → 201

или:

101 → 102

Разбираем решение по шагам

Базовые случаи остаются прежними: при x > y возвращаем 0, при x == y — 1. Обе команды увеличивают число.
Переводим число в строку:

s = str(x)

Так удобно проверять и заменять цифры.

Проверяем доступность команды выражением:

'1' in s

Например:

для строки '34' команда недоступна;
для строки '41' команда доступна.

Выражение:

s.replace('1', '2')

заменяет все цифры 1.

Затем int(...) превращает полученную строку обратно в число:

new_x = int(s.replace('1', '2'))

Если единица есть, складываем две ветви:

после +1;
после замены.

Если единицы нет, остаётся только ветвь +1.

def F(x, y):
    if x > y:
        return 0

    if x == y:
        return 1

    s = str(x)

    if '1' in s:
        new_x = int(s.replace('1', '2'))
        return F(x + 1, y) + F(new_x, y)
    else:
        return F(x + 1, y)


print(F(11, 92))

Главная деталь формулировки — слово «каждая». Метод replace подходит именно потому, что заменяет все вхождения. Если без проверки вызвать команду для числа без единицы, программа начнёт считать несуществующий вариант.

Ответ: 1408

1. Введение

2. Теория: как решать задачу вручную

Шаг 1. Задаём начало

Шаг 2. Находим предшественников каждого числа

Шаг 3. Доходим до конечного числа

Как учитывать дополнительное число C

Траектория не должна содержать C

Траектория обязана содержать C

3. Теория: как решать задачу кодом

4. Прототипы задач

Прототип 1. Базовый

Условие

Решение

Прототип 2. Траектория не проходит через C

Условие

Решение

Прототип 3. Траектория проходит через C

Условие

Решение

Проверка трёх прототипов

5. Практика с решениями на Python

Практика 1. Команды +2 и +7

Условие

Разбор

Практика 2. Движение вниз, через 10, но не через 7

Условие

Что меняется по сравнению с базовым шаблоном

Практика 3. Основная волна 2026 — «Поменяй местами»

Условие

Разбираем решение по шагам

Практика 4. Основная волна 2026 — «Измени цифру»

Условие

Разбираем решение по шагам

Читайте также

Задание 25 ЕГЭ информатика

Задание 22 ЕГЭ информатика

Задание 3 ЕГЭ информатика