Разборы · ЕГЭ, задание 13

Задание 13 ЕГЭ по информатике: количество программ исполнителя

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

У исполнителя две или три команды, которые меняют число на экране. Нужно посчитать, сколько существует программ, переводящих одно число в другое; иногда траектория должна проходить через заданное число или обходить его. 1 балл.

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

• Число программ из n в конечное число равно сумме чисел программ из всех чисел, в которые n переходит одной командой. Это рекурсия.
• Если команды только увеличивают число, рекурсия обязательно закончится: когда число стало больше конечного, программ 0.
• Траектория через X: количество(start → X) · количество(X → end). Траектория в обход X: в функции считаем, что из X программ 0.
• @lru_cache запоминает уже посчитанные значения, и программа работает мгновенно.

Как решать

1. Напишите функцию count(n, end) по правилу выше.
2. Аккуратно запишите условие применимости команд — в нём чаще всего и ошибаются.
3. Для особых условий на траекторию используйте произведение или «запрет» числа.

Пример из демоверсии 2027

Команды: A — «Прибавь 1», B — «Поменяй местами». Команда B применяется, только если цифра десятков меньше цифры единиц, и меняет местами две младшие цифры (например, 13 → 31). Сколько программ переводят 100 в 141?

Решение. Команда B применяется, только когда число от этого увеличивается, поэтому обе команды увеличивают число, и рекурсия конечна.

from functools import lru_cache

def swap(n):                                # меняем местами две младшие цифры
    tens, units = n // 10 % 10, n % 10
    return n - 10 * tens - units + 10 * units + tens

@lru_cache(None)
def count(n, end):
    if n == end:
        return 1
    if n > end:
        return 0
    res = count(n + 1, end)                 # команда A
    if n // 10 % 10 < n % 10:               # команда B применима
        res += count(swap(n), end)
    return res

print(count(100, 141))                      # 16

Ответ: 16. Если бы траектория должна была проходить через 120, ответ был бы count(100, 120) * count(120, 141). Перед тем как запускать программу на исходных числах, проверьте её на маленьком случае, который можно пересчитать руками, — например, сколько программ переводят 13 в 15.

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

• Неверно записывают условие применимости команды (здесь — строго «меньше»).
• При условии «траектория не содержит X» забывают запретить X в функции: нужна строка if n == X: return 0.
• Не ставят проверку n > end, и рекурсия уходит в бесконечность.

Потренироваться: задание 13 новые варианты с проверкой ответа