Е23.68 Сколько существует программ, для которых при исходном числе 10 результатом является число 84

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

A. Прибавь 1

B. Измени цифру

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

Программа для исполнителя — это последовательность команд.

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 34, 35.

Ответ:

Резервная волна ЕГЭ по информатике 22.06.2026 – задание №23

Решение:

Решение —

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

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

    if x == y:
        return 1

    s = str(x)

    if s.count('1') > 0:
        s = s.replace('1', '3')
        return f(x + 1, y) + f(int(s), y)
    else:
        return f(x + 1, y)

print(f(10, 84))

def f(x, y):

if x > y:

return 0

if x == y:

return 1

s = str(x)

if s.count('1') > 0:

s = s.replace('1', '3')

return f(x + 1, y) + f(int(s), y)

else:

return f(x + 1, y)

print(f(10, 84))

Разберём программу.

f(x, y) — количество программ, с помощью которых можно получить число y, начиная с числа x;
если x > y, получить y уже невозможно, поэтому возвращается 0;
если x == y, нужное число получено, поэтому возвращается 1;
команда A всегда доступна и переводит число x в x + 1;
если в записи числа есть хотя бы одна цифра 1, дополнительно можно применить команду B и заменить все цифры 1 на 3.

Например, если текущее число равно 21, команда B преобразует его в:

21 → 23

Если число равно 11, то заменяются сразу обе единицы:

11 → 33

Поэтому в случае, когда цифра 1 присутствует, количество возможных программ складывается из двух вариантов:

f(x + 1, y) + f(int(s), y)

1	f(x + 1, y) + f(int(s), y)

Запускаем функцию для исходного числа 10 и конечного числа 84:

print(f(10, 84))

1 2	print(f(10, 84))

Программа выводит:

480

Ответ: 480