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

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

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

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

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

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

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

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

Решение 1 (Рекурсия)

def f(s, fi, flag):
    if s > fi:
        return 0
    if s == 10:
        flag = True
    if s == fi and flag:
        return 1
    return f(s + 1, fi, flag) + f(s + 2, fi, flag) + f(s * 3, fi, flag)
print(f(2, 13, False))

Решение 2 (Динамика)

a = [0] * 14
a[2] = 1
for i in range(3, 14):
    a[i] += a[i - 1] + a[i - 2]
    if i % 3 == 0:
        a[i] += a[i // 3]
    if i == 10:
        for i in range(i):
            a[i] = 0

print(a[13])

Ответ: 120