Задача к ЕГЭ по информатике на тему «Количество программ из A в B (на убывание)» №1

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

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

Вычесть $3$
Поделить на $3$ , если число кратно $3$
Поделить на $2$ , если число кратно $2$

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

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

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

def f(st, fn):
    if st == fn:
        return 1
    if st < fn:
        return 0
    x = f(st // 3, fn) * (st % 3 == 0)
    y = f(st // 2, fn) * (st % 2 == 0)
    z = f(st - 3, fn)
    return x + y + z
print(f(30, 3))

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

a = [0] * 31
a[30] = 1
for i in range(30, 1, - 1):
    a[i - 3] += a[i]
    a[i // 2] += a[i] * (i % 2 == 0)
    a[i // 3] += a[i] * (i % 3 == 0)
print(a[3])

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

a = [0] * 100
a[30] = 1
for i in range(29, 2, -1):
    a[i] = a[i + 3] + a[i * 3] + a[i * 2]
print(a[3])

Ответ: 23