Задача к ЕГЭ по информатике на тему «количество программ из a в b смешанное» №1

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

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

Прибавить $3$
Умножить на $2$
Возвести в третью степень

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

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

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

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

def f(st, fn, flag, flag_number, exit_number):
    if st == fn and flag:
        return 1
    if st > fn or st == exit_number:
        return 0
    if st == flag_number: # поднимаем флаг, если дошли до требуемого значения
        flag = True
    x = f(st + 3, fn, flag, flag_number, exit_number)
    y = f(st * 2, fn, flag, flag_number, exit_number)
    z = f(st ** 3, fn, flag, flag_number, exit_number)
    return x + y + z
print(f(3, 96, False, 12, 25))

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

def f(x, y):
    if x > y or x == 25:
        return 0
    elif x == y:
        return 1
    else:
        return f(x + 3, y) + f(x * 2, y) + f(x ** 3, y)

print(f(3, 12) * f(12, 96))

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

a = [0] * (96 ** 3 + 1)
a[3] = 1
for i in range(3, 96):
    if i == 12:
        b = a[i]
        a = [0] * (96 ** 3 + 1)
        a[i] = b
    if i != 25:
        a[i + 3] += a[i]
        a[i * 2] += a[i]
        a[i ** 3] += a[i]
print(a[96])

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

a = [0] * 97
a[3] = 1
for i in range(4, 97):
    a[i] = a[i - 3] + a[i // 2] * (i % 2 == 0)
    x = int(i ** (1 / 3))
    if x ** 3 == i:
        a[i] += a[x]
    if i == 12:
        for j in range(i):
            a[j] = 0
    if i == 25:
        a[i] = 0
print(a[96])

Ответ: 160