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

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

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

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

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

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

Первая из них увеличивает число на экране на $1$ , вторая увеличивает число на $2$ , третья увеличивает число в $3$ раза.

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

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

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

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

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

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

Ответ: 112