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

Question

Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь 1
B. Измени цифру
Первая из этих команд увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого в записи присутствует хотя бы одна цифра 1, и действует, заменяя число на экране числом, в котором каждая цифра 1 заменена на цифру 3.
Программа для исполнителя - это последовательность команд.
Сколько существует программ, для которых при исходном числе 11 результатом является число 94?
Траектория вычислений программы - это последовательность результатов выполнения всех команд программы.
Например, для программы АВА при исходном числе 13 траектория состоит из чисел 14, 34, 35.

Accepted Answer

Программное решение:
def f(start, end):
if start > end:
return 0
if start == end:
return 1
str_start = str(start)
if '1' in str_start:
return f(start + 1, end) + f(int(str_start.replace('1','3')), end)
else:
return f(start + 1, end)

print(f(11, 94))
Ответ: 832.

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

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