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

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

  1. Вычесть 1  ;
  2. Вычесть 3  ;
  3. Разделить нацело на 3  .

При выполнении команды 3  выполняется деление нацело (остаток отбрасывается). Программа для исполнителя — это последовательность команд. Сколько существует таких программ, которые исходное число 22  преобразуют в число 2  ?

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

def f(a, b):
    if a == b:
        return 1
    if a < b:
        return 0
    return f(a - 1, b) + f(a - 3, b) + f(a // 3, b)

print(f(22, 2))

 

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

a = [0] * 70
a[22] = 1
for i in range(21, 1, -1):
    a[i] = a[i + 1] + a[i + 3] + a[i * 3] + a[i * 3 + 1] + a[i * 3 + 2]
print(a[2])

 

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

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

Ответ: 2196
Оцените статью
Я решу все!