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

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

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

1. Вычесть $3$

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

3. Поделить на $2$ , если число четное

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

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

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

def f(st, fn, count, end_count):
    if st == fn and count == end_count:
        return 1
    if st < fn or count > end_count: # если счетчик перешел максимальное
# значение, то прекращаем считать
        return 0
    x = f(st // 2, fn, count + 1, end_count) * (st % 2 == 0)
    y = f(st - 3, fn, count + 1, end_count)
    z = f(st - 1, fn, count + 1, end_count)
    return x + y + z
print(f(33, 12, 0, 9))

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

a = [33]
for i in range(9):
    n = len(a)
    for j in range(n):
        k = a.pop(0)
        if k > 12:
            a.append((k // 2) * (k % 2 == 0))
            a.append(k - 3)
            a.append(k - 1)
print(a.count(12))

Ответ: 85