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

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

Исполнитель ДАША преобразует число, записанное на экране.

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

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

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

3. Разделить на $5$ , если кратно $5$ .

Первая команда уменьшает число на экране на $5$ , вторая — на $2$ , третья — уменьшает число в $5$ раз, если оно кратно $5$ .

Сколько существует программ, для которых при исходном числе $49$ результатом является число $1$ и при этом траектория содержит число $13$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Программа:

def f(x, y):
    if x == y:
        return 1
    if x < y:
        return 0

    if x % 5 == 0:
        return f(x - 5, y) + f(x - 2, y) + f(x // 5, y)
    else:
        return f(x - 5, y) + f(x - 2, y)

print(f(49, 13) *f(13, 1))

Ответ: 3425