Задача к ЕГЭ по информатике на тему «количество программ из a в b где траектория вычислений содержит число(-а)» №1

Просмотров 6 Комментарии 0

Исполнитель Крабокорм преобразует число на экране.

У исполнителя есть три команды, которым присвоены номера:

1. Вычесть $1$

2. Вычесть $3$

3. Взять целую часть от деления на $3$ .

Первая команда уменьшает число на экране на $1$ , вторая уменьшает число на экране на $3$ , третья заменяет число на экране на целую часть от деления на $3$ .

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

Сколько существует программ, которые преобразуют исходное число $38$ в число $1$ и при этом траектория вычислений содержит число $14$ ?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы $113$ при исходном числе $13$ траектория будет состоять из чисел $12$ , $11$ , $3$ .

Рекурсия:

def f(x, y):
    if x == y:
        return 1
    if x < y:
        return 0
    else:
        return f(x - 1, y) + f(x - 3, y) + f(x // 3, y)

print(f(38, 14) * f(14, 1))

Ответ: 1379664