ЕГЭ Информатика 2022: Разбор задачи 23 (динамическое программирование)

Задание проверяет умение анализировать результаты исполнения алгоритма и основано на методе динамического программирования. Методика решения аналогична заданию из демоверсии 2021 года.

Постановка задачи

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

Прибавить 1
Умножить на 2

Программа для исполнителя — последовательность команд. Необходимо определить количество программ, для которых при начальном числе 1 результатом является число 20, и при этом траектория вычисления содержит число 10.

Решение с использованием динамического программирования

Для решения задачи воспользуемся динамическим программированием. Задачу можно разбить на две части: поиск количества программ от 1 до 10 и от 10 до 20. Количество программ от 1 до 20 — произведение этих двух величин.

Обозначим через k(n) количество программ, приводящих к числу n. Рассмотрим несколько первых чисел:

1: k(1) = 1 (одна программа: пустая последовательность)
2: k(2) = 2 (две программы: 1 + 1 и 1 * 2)
3: k(3) = 2 (две программы: из 2 прибавить 1)
4: k(4) = 4 (четыре программы: из 2 умножить на 2, из 3 прибавить 1, из 1 прибавить 1 и прибавить 1 и прибавить 1, из 1 прибавить 1 и умножить на 2)
5: k(5) = 4 (из 4 прибавить 1)
6: k(6) = 6 (из 5 прибавить 1, из 3 умножить на 2)
7: k(7) = 6 (из 6 прибавить 1)
8: k(8) = 10 (из 7 прибавить 1, из 4 умножить на 2)
9: k(9) = 10 (из 8 прибавить 1)
10: k(10) = 14 (из 9 прибавить 1, из 5 умножить на 2)

Рекуррентная формула:

Для нечётных n: k(n) = k(n-1)
Для чётных n: k(n) = k(n-1) + k(n/2)

Вычисляя значения k(n) последовательно, получим k(10) = 14.

Для чисел от 10 до 20, в 20 можно попасть двумя способами: последовательно прибавляя 1 (1 программа) или умножив 10 на 2 (1 программа). Количество программ от 10 до 20 равно 2.

Окончательный ответ: 14 * 2 = 28

Решение с использованием языка программирования

Более эффективный способ — использование рекурсивной функции на языке программирования.

Функция f(a, b) принимает два аргумента: текущее число a и целевое число b.

def f(a, b):
    if a > b:
        return 0
    elif a == b:
        return 1
    else:
        return f(a + 1, b) + f(a * 2, b)

print(f(1, 10) * f(10, 20)) # вывод 28

Функция рекурсивно подсчитывает количество программ. Результат вычисления f(1, 10) * f(10, 20) равен 28.

Задание 23 можно решить как вручную с использованием динамического программирования, так и с помощью рекурсивной функции на языке программирования. Второй способ, как правило, более быстрый и удобный.