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

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

Исполнитель ЗВЕЗДОЧКА преобразует число, записанное на экране.

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

1. Прибавить $1$

2. Прибавить $4$

3. Умножить на $2$

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

Сколько существует программ, для которых при исходном числе $33$ результатом является число $72$ и при этом траектория не содержит число $30$ ?

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

Рекурсия:

def f(x, y):
    if x > y or x == 30:
        return 0
    elif x == y:
        return 1
    else:
        return f(x + 1, y) + f(x + 4, y) + f(x * 2, y)

print(f(33, 72))

Динамика:

num = [0] * 73
num[33] = 1
for i in range(34, 73):
    num[i] = ((num[i - 1] + num[i - 4]) + num[i // 2] * (i % 2 == 0)) * (i != 30)
print(num[72])

Ответ: 157430