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

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

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

Прибавить $2$
Умножить на $3$
Прибавить остаток от деления на $2$ и прибавить $2$

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

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

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

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

def f(st, fn, exit_number):
    if st == fn:
        return 1
    if st > fn or st == exit_number:
        return 0
    x = f(st + 2, fn, exit_number)
    y = f(st * 3, fn, exit_number)
    z = f(st + st % 2 + 2, fn, exit_number)
    return x + y + z
print(f(1, 15, 13))

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

a = [0] * 16 * 3
a[1] = 1
for i in range(1, 15):
    if i != 13:
        a[i + 2] += a[i]
        a[i * 3] += a[i]
        a[i + i % 2 + 2] += a[i]
print(a[15])

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

a = [0] * 16
a[1] = 1
# 2 -> 2 + 0 + 2 = 4
# 1 -> 1 + 1 + 2 = 4
for i in range(2, 16):
    a[13] = 0
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0) + (a[i - 2] + a[i - 2 - 1]) * (i % 2 == 0)
print(a[15])

Ответ: 2