Задание 13. Анализ хода исполнения алгоритма – ЕГЭ по информатике

Что проверяет задание

Задание 13 – исполнитель с двумя или тремя командами: он преобразует число на экране, а спрашивают, сколько существует программ, переводящих начальное число в конечное. Иногда добавляют условие на траекторию – например, что она не содержит заданного числа.

1 балл, норматив 7 минут. Задание решается программой строк на десять; вручную считаются только самые короткие варианты, и то на грани ошибки. Рекомендую сразу писать код.

Что нужно знать заранее:

рекурсия: функция, вызывающая саму себя с другим аргументом;
чем рекурсия отличается от итерации и зачем запоминать уже посчитанное: одно и то же число считается заново по каждому пути, который в него ведёт;
целочисленное деление и остаток: цифру десятков достают как n // 10 % 10, цифру единиц – как n % 10.

Типовой пример

Задание 13 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь 1
B. Поменяй местами

Первая из этих команд увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.

Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 100 результатом является число 141?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.

Как рассуждать

Программа – это путь. Каждая последовательность команд даёт ровно одну цепочку чисел, поэтому «сколько существует программ» и «сколько разных путей ведёт из 100 в 141» – один и тот же вопрос.
Обе команды увеличивают число. У A это очевидно, у B – потому что она применима только тогда, когда цифра десятков меньше цифры единиц, а обмен таких цифр даёт число больше. Значит все пути идут только вперёд: цикла быть не может, и всё, что перескочило 141, выбывает.
Заводим ленту клеток. Выпишем в строку все числа от 100 до 141 и в клетке $n$ будем хранить $G(n)$ – сколько программ ведёт из 100 в $n$. В стартовой клетке $G(100) = 1$: пустая программа, ни одной команды выполнять не нужно. Ответ окажется в последней клетке.
Из каждой клетки ведут стрелки вперёд. Команда A – шаг в соседнюю клетку, из $n$ в $n + 1$. Команда B – прыжок в $s(n)$, число с переставленными младшими цифрами, и только если цифра десятков меньше цифры единиц. Например, из 101 ведут две стрелки: A в 102 и B в 110.

1001A

1011

1021

1031

1041

1051B: 101 → 110

1061

1071

1081

1091

1102

Клетки заполняются слева направо, и каждая отдаёт своё число вперёд по своим стрелкам. Поэтому в 110 стоит 2: одна программа пришла цепочкой команд A из 109, вторая прыгнула из 101.

Чтобы записать это формулой, посмотрим на ту же картинку с другой стороны – не какие стрелки из клетки выходят, а какие в неё входят. В клетку $m$ всегда приходит стрелка A из $m - 1$. Стрелка B приходит из $s(m)$, но не всегда: команда B применяется к числу, у которого десятков меньше, чем единиц, и переставляет их – значит у её результата десятков больше. Так что условие в соотношении перевёрнуто: $a > b$, где $a$ и $b$ – цифры десятков и единиц числа $m$.

Рекуррентное соотношение

\[ G(m) = \begin{cases}1, & m = 100,\\G(m-1) + G(s(m)), & m > 100,\ a > b,\\G(m-1), & m > 100,\ a \le b.\end{cases} \]

Из формулы в программу

Ответ – это $G(141)$, последняя клетка ленты. Дальше дело техники, и техника здесь в одну строчку хитрее, чем кажется: в программе удобнее не собирать стрелки, входящие в клетку, а раздавать число по стрелкам, выходящим из неё. Тогда условие переворачивать не надо – берём его прямо из условия задачи. Цикл идёт по $n$ слева направо и прибавляет значение клетки $n$ в клетки $n + 1$ и $s(n)$; к моменту, когда цикл до клетки доходит, все стрелки в неё уже пришли – по пункту 2 они все идут вперёд.

Строка соотношения	Что значит	Строка кода
$G(100) = 1$	старт: годится пустая программа	`count[START] = 1`
$G(m - 1)$	пришли командой A из соседней клетки	`count[n + 1] += count[n]`
$G(s(m))$ при $a > b$	пришли командой B прыжком	`count[swap(n)] += count[n]`
ответ $G(141)$	последняя клетка	`print(count[TARGET])`

Способ 1: таблица

Это ровно лента из предыдущего блока: список клеток и цикл слева направо. У такого счёта есть имя – динамическое программирование: задача разбита на клетки, и каждая считается один раз через уже посчитанные.

Способ надёжен тем, что в нём нечему ломаться – нет предела вложенности, нечего забыть продекорировать, нечем переполнить стек. И таблицу видно целиком: её можно распечатать и сверить глазами, а в отладке это дороже скорости.

Число	Как складывается	Программ
100	1 – пустая программа	1
110	1 (A из 109) + 1 (B из 101)	2
120	2 (A из 119) + 1 (B из 102)	3
121	3 (A из 120) + 2 (B из 112)	5
130	5 (A из 129) + 1 (B из 103)	6
131	6 (A из 130) + 2 (B из 113)	8
132	8 (A из 131) + 5 (B из 123)	13
140	13 (A из 139) + 1 (B из 104)	14
141	14 (A из 140) + 2 (B из 114)	16

Здесь выписаны не все клетки, а только те, куда ведёт обмен: их 8. В остальные приходит ровно одна стрелка, и строка повторяла бы соседнюю, ничего не объясняя. Последняя строка – 141, она выделена жирным: это ответ.

START = 100
TARGET = 141


def can_swap(n):
    """Команда B применима: цифра десятков меньше цифры единиц."""
    return n // 10 % 10 < n % 10


def swap(n):
    """Меняем местами две младшие цифры, старшие разряды не трогаем."""
    return n // 100 * 100 + n % 10 * 10 + n // 10 % 10


count = [0] * (TARGET + 1)
count[START] = 1                       # в стартовое число ведёт пустая программа

for n in range(START, TARGET):
    count[n + 1] += count[n]                        # команда A: n -> n + 1
    if can_swap(n) and swap(n) <= TARGET:
        count[swap(n)] += count[n]                  # команда B: n -> swap(n)

print(count[TARGET])                   # 16

Способ 2: рекурсия

Формула та же, считаем её с другого конца: спрашиваем последнюю клетку, она спрашивает предыдущую и ту, из которой в неё прыгнули, те – свои. Соотношение переписывается в функцию строка в строку, вместе с перевёрнутым условием >: функция, как и формула, смотрит на входящие стрелки.

Ловушек ровно две, и обе стоят решённой задачи.

sys.setrecursionlimit(30000). Python по умолчанию обрывает вложенность на 1000 вызовах и падает с RecursionError. Здесь глубина всего 41 шаг – цепочка команд A от 100 до 141, – но в вариантах этого же номера просят получить из 3 число в несколько тысяч: там цепочка «прибавь 1» длиннее тысячи, и программа упадёт не на неверном ответе, а на трассировке. Задирать лимит до небес тоже нельзя: setrecursionlimit(10 ** 9) меняет RecursionError на аварийное завершение процесса – глубина ограничена ещё и размером стека.

@lru_cache. Без кеша одна и та же клетка считается заново по каждому пути, который в неё ведёт: на демоварианте это 148 вызовов там, где клеток всего 42. Разницы не заметно, но на вариантах с умножением и диапазоном в несколько тысяч она становится решающей: число путей растёт лавинообразно, и без кеша программа не досчитает до конца. Одна строка декоратора превращает перебор путей в подсчёт по каждой клетке ровно один раз – ровно то, что таблица делает сама собой. Обеих ловушек у способа с таблицей нет, потому подход с динамическим программированием идет первым.

import sys
from functools import lru_cache

sys.setrecursionlimit(30000)   # предел по умолчанию – 1000 вложенных вызовов

START = 100
TARGET = 141


def swap(m):
    """Меняем местами две младшие цифры, старшие разряды не трогаем."""
    return m // 100 * 100 + m % 10 * 10 + m // 10 % 10


@lru_cache(maxsize=None)
def count(m):
    if m == START:
        return 1                  # старт: годится пустая программа
    if m < START:
        return 0                  # левее ленты клеток нет
    total = count(m - 1)          # пришли командой A
    if m // 10 % 10 > m % 10:     # ... и командой B, если она сюда ведёт
        total += count(swap(m))
    return total


print(count(TARGET))              # 16

Если условие другое

Каркас не меняется никогда: считаем пути от начального числа к конечному и складываем вклады. Правят всегда одно из трёх – набор команд, отсечение по траектории или направление обхода.

Что в условии	Что править в коде
есть команда «умножь на 2»	ещё одна строка в цикле: `count[n * 2] += count[n]` с проверкой `n * 2 <= TARGET`; в рекурсии – ещё одно слагаемое `total += count(n * 2)`
«траектория не содержит числа 14»	в таблице `if n == 14: continue`, в рекурсии первой же строкой `if n == 14: return 0`
«траектория содержит число 12»	задача распадается на две: сколько программ ведёт из начала в 12 и сколько из 12 в конец. Ответ – произведение, а не сумма
команды уменьшают число («вычти 1», «целая часть от деления на 2»)	числа убывают, поэтому таблицу заполняют циклом сверху вниз, а в рекурсии отсечение становится `if n < TARGET: return 0`
команда B – не обмен, а замена цифр («каждая цифра 1 меняется на 3»)	меняются только две строчки: применимость – `'1' in str(n)`, сам ход – `int(str(n).replace('1', '3'))`. Каркас тот же: эта команда тоже увеличивает число

Типичные ошибки

Забыли, что пустая программа считается. В стартовой клетке должно стоять count[100] = 1, а не 0: попасть в начальное число можно, ничего не выполнив.
Проверили применимость команды B у результата, а не у исходного числа. После обмена цифра десятков всегда больше цифры единиц – у 41 команда уже неприменима. Поэтому проверка на результате запрещает все обмены разом, и остаётся единственная цепочка из команд A: ответ 1 вместо 16. Условие смотрит на число до хода, а не после.
Не отсекли числа больше 141. В рекурсии это бесконечный спуск: команда A зовёт count(142), тот – count(143), и так до предела вложенности. В таблице – IndexError: count[swap(n)] при обмене, уводящем за 141, лезет за границу списка, потому что список длиной 142. Отсюда и проверка swap(n) <= TARGET рядом с can_swap(n).
Ответили не на тот вопрос. Спрашивают количество программ, а не длину траектории и не сами программы.