Автор статьи: Андрей Рогов
Введение
В задании № 23 определить возможные результаты работы алгоритма. Задание относится к повышенному уровню сложности, рекомендуем отвести на него 8 минут.
Есть много способов решения этого задания: ручное построение дерева, в электронных таблицах и с помощью программирования.
Сначала мы решим задание вручную, а затем разберём два подхода к решению задачи с применением программирования: рекурсивное решение и динамический подход. Эти способы похожи на методы решения задания № 16.
Как решить задание вручную
Разберём ход вычислений.
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1\
B. Прибавить 2\
C. Умножить на 2
Программа для исполнителя — это последовательность команд.
Для примера возьмём число 2 и выполним программу CAB.
Таким образом, из числа 2 программа CAB сделает число 7. Число 7 можно получить и с помощью другой программы, например ACA.
Посчитаем, сколько всего существует программ, при выполнении которых из числа 2 результатом будет число 7. Это удобно изобразить с помощью дерева:
- числа в красных кружках — это числа, большие чем 7. Из них уже нельзя вернуться
- зелёными кружками отмечены конечные точки — само число 7. Оно встречается в дереве 12 раз. Следовательно, существует 12 программ получения числа 7 из числа 2
- белые кружки — это промежуточные результаты. Из них можно делать вычисления дальше
Некоторые части дерева повторяются. Так, вычисления из числа 4 можно встретить сразу три раза. В аналитическом решении каждая четвёрка не вычисляется отдельно, а вычисляется только одна из них, и её результат переносится на остальные.
Похожим образом работает динамический подход. А вот рекурсивный, наоборот, вычисляет значения каждый раз, если их не кешировать.
Можно выделить три вида значений:
- Числа, большие конечного значения. Количество программ для получения ответа в них равно нулю
- Конечное значение. Количество программ равно единице
- Промежуточные числа. Чтобы посчитать их значение, необходимо сложить количество программ для чисел, в которые можно попасть из этого числа
Перейдём от словесной модели к математической:
- K(n) = 0, если n больше конечного значения
- K(n) = 1, если n равно конечному значению
- K(n) = K(n + 1) + K(n + 2) + K(n × 2) для остальных значений n
Модель будет верной для текущих условий задачи. Для других команд формулы будут отличаться.
Теперь мы можем вычислить по этим формулам количество программ. Для примера вручную найдём количество программ из 2 в 7. Конечное значение равно 7, поэтому формулы можно записать так:
K(n) = 0, если n > 7\
K(n) = 1, если n = 7\
K(n) = K(n + 1) + K(n + 2) + K(n × 2) для остальных значений n\
K(2) = K(3) + K(4) + K(4)\
K(3) = K(4) + K(5) + K(6)\
K(4) = K(5) + K(6) + K(8) = K(5) + K(6) + 0 = K(5) + K(6)\
K(5) = K(6) + K(7) + K(10) = K(6) + 1 + 0 = K(6) + 1\
K(6) = K(7) + K(8) + K(12) = 1 + 0 + 0 = 1
Мы дошли до значения, которое можно вычислить, и все зависимые значения теперь тоже можно вычислить. Будем делать это в обратном порядке.
K(6) = 1\
K(5) = K(6) + 1 = 1 + 1 = 2\
K(4) = K(5) + K(6) = 2 + 1 = 3\
K(3) = K(4) + K(5) + K(6) = 3 + 2 + 1 = 6\
K(2) = K(3) + K(4) + K(4) = 6 + 3 + 3 = 12
Результат согласуется с деревом, где тоже получилось 12 путей.
Динамическое программирование
Теперь вместо вычислений вручную напишем программу и применим метод динамического программирования. У него есть ряд плюсов. Во-первых, вычисления проводятся за линейное время. Во-вторых, у нас сразу есть все промежуточные результаты. И, наконец, программа масштабируется и адаптируется для разных условий заданий ЕГЭ по информатике.
Под хранение количества программ заведём список. В качестве чисел возьмём индексы списка, значения элементов списка — количество программ. Напомним формулы вычисления:
K(n) = 0, если n > 7\
K(n) = 1, если n = 7\
K(n) = K(n + 1) + K(n + 2) + K(n × 2) для остальных значений n
Так как в формуле используется возрастающая зависимость (для каждого n надо знать значения для больших n), чтобы вычислить количество программ, необходимо написать цикл, идущий в обратном порядке.
k = [0] * 100 # заведомо больше чисел
k[7] = 1 # по условию
for n in range(6, 0, -1):
k[n] = k[n + 1] + k[n + 2] + k[n * 2] # согласно формуле
print(k[2])
# дополнительный вывод
print('\t'.join(str(i) for i in range(10)))
print('\t'.join(str(k[i]) for i in range(10)))
Заведём список со множеством нулей. 7 — конечное число, для которого мы находим значение. Поэтому в элемент с индексом 7 кладём единицу.
Начиная с 6 и до начального числа вычисляем количество программ по формуле. По индексу 2 будет лежать количество программ, которыми можно из числа 2 получить 7. Дополнительный вывод позволяет понять количество программ для всех чисел. Он полностью совпадает с нашими вычислениями вручную и согласуется с деревом.
У этого подхода есть ряд плюсов. Во-первых, вычисления проводятся за линейное время. Во-вторых, у нас сразу есть все промежуточные результаты. И, наконец, программа масштабируется и адаптируется к разным условиям задач. Прежде чем переходить к другим вариантам задания, разберём ещё один подход, рекурсивный.
Рекурсия
Полученные формулы можно описать рекурсивной функцией, так как в них есть все необходимые элементы: база рекурсии и зависимость величины от других значений. Этот метод визуально выглядит проще и позволяет быстрее адаптировать условия задачи.
Запишем формулы в качестве рекурсивной функции.
K(n) = 0, если n > 7\
K(n) = 1, если n = 7\
K(n) = K(n + 1) + K(n + 2) + K(n × 2) для остальных значений n
def k(n):
if n > 7:
return 0
if n == 7:
return 1
return k(n + 1) + k(n + 2) + k(n * 2)
print(k(2))
Этот код тоже нужно адаптировать для каждой задачи. Можно сделать функцию менее зависимой от конечного значения, сделав его как параметр. Это будет удобно для решения некоторых заданий.
def k(n, e):
if n > e:
return 0
if n == e:
return 1
return k(n + 1, e) + k(n + 2, e) + k(n * 2, e)
print(k(2, 7))
В задании № 23 не нужно кешировать значения рекурсивной функции, поскольку глубина рекурсии будет достаточно маленькой.
Попрактикуемся: решим несколько заданий из ЕГЭ по информатике.
Задача 1. Не содержит число
В задании требуется посчитать количество программ с дополнительным условием: что в траектории вычислений нет числа 25.
При динамическом решении необходимо сделать так, чтобы при вычислении 25-го элемента его значение стало равным нулю. Этого можно добиться с помощью дополнительной проверки условия.
Количество элементов в списке определяем так: самое большое значение — 115, самая сильная команда — умножить на 5. 115 × 5 = 575, следовательно нужно задать как минимум 576 элементов.
k = [0] * 1000 # заведомо больше чисел
k[115] = 1 # по условию
for n in range(114, 0, -1):
if n == 25: # пропускаем 25
continue
k[n] = k[n + 3] + k[n * 2] + k[n * 5] # согласно формуле
print(k[5])
В рекурсивном решении также учтём, что значение функции при n = 25 должно быть равно нулю.
def k(n, e):
if n == 25:
return 0 # пропускаем 25
if n > e:
return 0
if n == e:
return 1
return k(n + 3, e) + k(n * 2, e) + k(n * 5, e)
print(k(5, 115))
Оба решения дают в качестве ответа 98.
Задача 2. Траектория вычислений содержит конкретное число
В этой задаче траектория вычислений должна содержать число 30. Тогда мы должны разбить решение на два независимых отрезка: сначала найдём количество программ из числа 3 в 30, затем — из числа 30 в 105. Итоговое количество программ будет равно их произведению.
Поскольку эти два отрезка не зависят друг от друга, в решении динамическим программированием будем использовать вычисления дважды.
k = [0] * 100 # заведомо больше чисел
k[30] = 1 # по условию
for n in range(29, 0, -1):
k[n] = k[n + 3] + k[n * 2] # согласно формуле
k1 = k[3] # сохраняем результат
k = [0] * 1000 # заведомо больше чисел
k[105] = 1 # по условию
for n in range(104, 0, -1):
k[n] = k[n + 3] + k[n * 2] # согласно формуле
k2 = k[30] # сохраняем результат
print(k1 * k2)
В рекурсивном решении функция описывается одна, но вызывается дважды с разными параметрами. Именно для этого дополнительного условия мы вводили в качестве параметра функции конечное число. Если этого не делать, необходимо описывать две разные функции.
def k(n, e):
if n > e:
return 0
if n == e:
return 1
return k(n + 3, e) + k(n * 2, e)
print(k(3, 30) * k(30, 105))
Задача 3. Несколько дополнительных условий
В задании сразу два дополнительных условия: содержит 13, следовательно разбиваем на два вычисления, не содержит 7 — исключаем из вычислений. Ещё одно отличие этой задачи — команды уменьшают числа.
В решении динамикой необходимо запустить цикл в прямом порядке.
k = [0] * 100 # заведомо больше чисел
k[13] = 1 # по условию
for n in range(14, 20):
k[n] = k[n - 1] + k[n - 4] + k[n // 3] # согласно формуле
k1 = k[19] # сохраняем результат
k = [0] * 100 # заведомо больше чисел
k[2] = 1 # по условию
for n in range(3, 14):
if n == 7:
continue
k[n] = k[n - 1] + k[n - 4] + k[n // 3] # согласно формуле
k2 = k[13] # сохраняем результат
print(k1 * k2)
В рекурсивном решении учтём, что остановка рекурсии будет при числах, меньших конечного.
def k(n, e):
if n == 7:
return 0
if n < e:
return 0
if n == e:
return 1
return k(n - 1, e) + k(n - 4, e) + k(n // 3, e)
print(k(19, 13) * k(13, 2))
Заключение
Мы разобрали два эффективных подхода к решению задания № 23 с использованием языка Python: динамическое программирование и рекурсивный метод.
Ключевые преимущества этих подходов: автоматизация вычислений, наглядность и понятность алгоритмов, гибкость при изменении условий задачи, эффективность при работе со сложными случаями.
Рекомендуем начинать решение с анализа команд исполнителя, затем определять направление вычислений в функции и выбирать оптимальный метод решения. Проверяйте корректность работы на простых примерах. При подготовке к ЕГЭ по информатике рекомендуем использовать несколько способов решения для каждого задания.
Если вы освоите эти два метода, то решите это задание даже с новыми условиями. Навыки пригодятся при решении других задач, например на подсчёт количества путей в графах.
Напоследок предлагаем решить подборку задач для практики.