задание 23

О задании

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

Почему снова? Дело в том, что мы уже применяли методы динамического программирования, например, при решении задания с «роботом» — номер 18. Правда, в тот раз работа велась исключительно с электронной таблицей.

В задании 23 вам представлен некий исполнитель, который имеет определённый набор команд. Подобные исполнители уже встречались нам: это и черепаха, и чертёжник, и редактор, и многие другие. То есть общий подход тут сохраняется: мы «переводим» команды с алгоритмического языка на Python.

Конкретно в 23 заданиях нам помимо реализации работы исполнителя еще предстоит вычислить количество возможных программ для преобразования одного числа в другое, путём математических операций.

В этой статье мы разберемся с методами динамического программирования, научимся составлять программы исполнителя на языке Python и разберём несколько алгоритмов решения 23 заданий.

Динамическое программирование

Динамическое программирование представляет собой способ оптимизации решения сложных задач, путём их последовательного разбиения на более мелкие и простые подзадачи (декомпозиция) и использования результатов решения этих подзадач.

Сам термин «динамическое программирование» был предложен еще в 1950 году Ричардом Беллманом. Так что, как вы понимаете, с привычным нам программирование этот термин не имеет ничего общего.

Изначально это был метод оптимизации математических задач. И только потом он стал применяться в языках программирования.

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

  1. Подзадачи должны общую структуру и однотипный алгоритм для их решения
  2. Должен существовать эффективный способ запоминать и использовать результаты решения подзадачи

Давайте рассмотрим разбиение задачи о нахождении чисел Фибоначчи на подзадачи:

  1. Определение подзадач: задача разбивается на более мелкие подзадачи, которые проще решить. Например, в задаче о нахождении чисел Фибоначчи, подзадачами являются вычисление F(n-1) и F(n-2)
  2. Рекуррентное соотношение: устанавливается связь между решением задачи и решениями её подзадач. Например, для чисел Фибоначчи: F(n) = F(n-1) + F(n-2)
  3. Хранение результатов: Результаты подзадач сохраняются (например, в кеше или словаре), чтобы избежать повторных вычислений

Существует два подхода решения задач динамическим программированием:

  1. Нисходящий подход
  2. Восходящий подход

В первом случае решение задачи начинается с самой большой задачи, которая рекурсивно разбивается на подзадачи. Для сохранения значения каждой подзадачи используется мемоизация.

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

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

Суть табулирования состоит в сохранении результатов вычислений в отдельной переменной (таблице) для повторного использования.

Например, для вычисления чисел Фибоначчи можно использовать такое решение с табулированием (рекурсивное решение с мемоизацией мы рассматривали здесь):

def fibonacci(n):
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fibonacci(35))
>>>9227465

Здесь в списке dp будут сохраняться значения, соответствующие числу из ряда Фибоначчи. Его мы изначально заполнили двумя известными значениями первого и второго элементов – 0 и 1.

В цикле for() мы заполняем список dp вычисленными по рекуррентной формуле значениями. Тогда, чтобы получить значение, например, 35-го элемента, нам достаточно обратиться к элементу списка dp с индексом 35.

В чем смысл динамического программирования в задаче с числами Фибоначчи? В том, что мы не можем «с ходу» дать ответ, что 35-ое число ряда равно 9227465. Это невозможно просто потому, что для его вычисления нам нужно опираться на предыдущие значения.

То есть необходимо разбить сложную и нерешаемую задачу по поиску 35-го числа на более простые, пока не получим известные значения – для чисел Фибоначчи это первые два – 0 и 1. И уже на основе них высчитывать все остальные, вплоть до 35-го.

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

Но для всех остальных заданий базового уровня, которые, вероятней всего, и попадутся вам на экзамене, лучше использовать нисходящий подход с рекурсией. Такое решение выглядит просто и лаконично. К тому же его функционал можно легко расширить в зависимости от типа задания.

Далее давайте рассмотрим рекурсивное решение упрощённой версии 23 задания сначала аналитическим способом, а затем переложим наши теоретические выкладки на язык программирования.

Разберём решение такой задачи:

«У исполнителя есть две возможные операции:

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

Найдите количество способов преобразовать число 1 в число 8, используя сочетания этих двух команд»

Нам проще будет рассматривать решение этой задачи «сверху вниз». То есть будем искать пути, которые могут привести от числа 8 к 1. Все операции тут будут инвертированы (вместо «прибавить» будет «отнять», вместо «умножить» – «разделить»).

Подход «сверху вниз» здесь мы используем только из-за того, что это будет более наглядно и займет меньше ходов решения. В конце мы покажем способ «снизу вверх», то есть будем искать все способы получить из единицы восьмёрку, как это и предложено в задании.

Суть нашего подхода в том, чтобы разбить сложную задачу «Найти все способы получить из 8 число 1» на более мелкие:

  1. Что можем получить, если к 8 применим обе операции?
  2. Что можем получить, если к результатам этих операций снова применим их?

И такое разбиение будет продолжаться до тех пор, пока не получим желаемое число 1.

Давайте перейдём к решению. Если число чётное, то оно может быть получено с помощью любой из двух наших команд. Тогда применим обе: отнимем от 8 число 3 и разделим 8 на 2.

Задание 23 1

В результате получаем два числа: 4 и 5. То есть мы из 4 можем получить 8, умножим 4 на 2 и из 5 получить 8, прибавив к 5 число 3. Теперь перед нами стоят следующие задачи:

  1. Найти все способы получить из 4 число 1
  2. Найти все способы получить из 5 число 1

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

Рассмотрим число 5. Получить целое число, поделив 5 на 2 мы не можем. Значит, остаётся только одна команда – отнять 3, в результате которой получим число 2.

Задание 23 2

Чтобы получить исходное число 1 у нас есть только один путь: поделить число 2 на 2.

Задание 23 3

Готово, мы нашли один путь, чтобы получить из 8 число 1.

Теперь вернёмся к четвёрке. Здесь можем сразу отнять 3 и получим число 1. Но также нам здесь доступна команда «разделить на 2», в результате которой получаем число 2.

Задание 23 4

Ну а к числу 2, как мы уже знаем, можно применить команду «разделить на 2».

Задание 23 5

Таким образом, мы получили 3 способа получить из числа 1 искомое число 8 (или наоборот). Давайте попробуем реализовать это решение на языке Python. Только в Python уже будем идти в «верном» порядке, то есть от числа 1 к 8.

Напишем рекурсивную функцию f(x, y), которая будет принимать два аргумента: исходное число (x) и искомое число, в которое нужно попасть (y). Далее, для удобства вместо терминов «исходное число» и «искомое число» будем использовать «начальная точка» и «конечная точка».

Внутри функции мы будем рекурсивно вызывать её же, но изменяя значения первого параметра. То есть будем применять к нему одну из двух доступных операций.

Начнём расписывать нашу функцию. Сначала определим условие x=y, которое нам скажет, что событие произошло:

def f(x, y):
    if x == y:
        return 1

Далее есть два пути: мы либо «перескочили» конечную точку, либо не добрались до неё. Для первого случая будем возвращать ноль, это означает, что таким сочетанием операций мы не можем получить из x y.

if x > y:
    return 0

Ну и самое интересное условие: если мы еще не добрались до конечной точки, то будет вызывать эту же функцию, применяя все возможные операции и складывая результаты вызова функций:

if x < y:
    return f(x + 3, y) + f(x * 2, y)

Почему будем именно складывать эти результаты? Дело в том, что базовым случаем в нашей рекурсивной функции будет именно условие равенства двух аргументов (x==y). Если условие истинно, то возвращается значение 1, означающее, что эта траектория вычисления нам подходит.

Следовательно, чтобы определить, сколько будет подходящих траекторий, нам достаточно просуммировать результаты работы функции со всеми операциями.

Весь код функции будет такой:

def f(x, y):
    if x == y:
        return 1

    if x > y:
        return 0

    if x < y:
        return f(x + 3, y) + f(x * 2, y)

Теперь вызываем функцию с нужными значениями и выводим результат:

print(f(1, 8))

В итоге получаем число 3, что и требовалось.

На изображении ниже показано, что происходит с аргументом x при работе функции.

Задание 23 6

Визуализировать работу своей рекурсивной функции можете с помощью этого сервиса.

Таким образом, на левой ветке дерева происходит вызов функции f(x + 3, y), а на правой – f(x * 2, y). Здесь видим, что если первая операция «Прибавить 3», то получим всего одну подходящую траекторию: «Прибавить 3» и «Умножить на 2».

Если же первой операцией будет «Умножить на 2», то получаем две подходящие траектории. Когда все вызовы рекурсивной функции будут завершены, то, подставив эти значения в условие, получим следующее выражение:

    if x < y:
        return 1 + 2

Что и вернёт нам количество всех возможных способов преобразовать число 1 в число 8, используя сочетания заданных команд.

Алгоритм решения

Базовый алгоритм решения заданий 23 мы рассмотрели выше. Но такие простые формулировки вам точно не попадутся. В целом, эти задания можно разделить на 3 типа:

  1. Когда траектория вычислений должна содержать какое-то число A
  2. Когда траектория вычисления не должна содержать какое-то число B
  3. И комбинация двух типов, когда траектория содержит число А и не содержит число B

Итак, если траектория вычисления должна содержать какое-то число А, то это означает, что мы можем разбить такую траекторию на две части: от начальной точки до числа A и после числа A до конечной точки.

И вторая часть этой траектории возможна только в том случае, если возможна первая. Следовательно, мы будем перемножать результаты функций, которые вычисляют эти траектории.

Например, если начальная точка – это x, конечная – y, а траектория вычисления должна содержать число A, то для вычисления количества всех подходящих траекторий можем воспользоваться следующей записью:

print(f(x, A) * f(A, y))

Далее у нас на рассмотрении второй тип. Здесь нам необходимо, чтобы наша траектория не содержала числа B. Реализовать это очень просто. Вспомним, что у нас есть условие, которое возвращает 0, если рассматриваемое число (x) не может быть в нашей траектории. То есть данным условием мы проверяем выход за пределы допустимых значений.

Например, в прошлой задаче таким условием проверяли, что не «перескочили» конечную точку:

    if x > y:
        return 0

Давайте тогда в это же условие добавим еще одно логическое выражение: если рассматриваемое число равняется значению B, то также будем возвращать 0. То есть такая траектория нам также не будет подходить. Записывается это следующим образом:

if x > y or x == B: 
    return 0

Но обратите внимание, что первая часть (x>y) работает только в том случае, если наша траектория идёт «снизу вверх» – от меньшего числа к большему.

Если же в нашей задаче нужно, наоборот, с числа 8 получить число 1, то следует проверять, что рассматриваемое число не меньше конечной точки. В таком случае можно переписать представленное выше условие так:

if x < y or x == B: 
    return 0

Решение заданий 23 третьего типа представляет собой не что иное, как сочетание подходов, рассмотренных в первом и втором типах.

Резюмируя сказанное, можно сделать такие выводы:

Варианты действий при проверке на выход за пределы допустимых значений:
1. На увеличение числа (из 1 в 8)

if x > y:
    return 0

2. На уменьшение числа (из 8 в 1)

if x < y:
    return 0

Варианты промежуточных точек:
1. Траектория не должна проходить через число B
В проверку на выход за пределы допустимых значений добавляем запись:

if x > y or x == B:
    return 0

2. Траектория должна проходить через число A
В самом конце, при вызове функции для вычисления ответа, добавляем запись:

print(f(x, A) * f(A, y))

Теперь перейдём к решению заданий каждого типа.

Тип 1

Рассмотрим такую формулировку:

Задание 2300

«Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычесть 2
B. Найти целую часть от деления на 2

Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 32 результатом является число 1 и при этом траектория вычислений содержит число 14?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2»

Распишем функцию по шаблону, выведенному ранее:

def f(x, y):
    if x == y:
        return 1

    if x < y:
        return 0

    if x > y:
        return f(x - 2, y) + f(x // 2, y)

Поскольку траектория должна содержать число 14, то сначала вызовем функцию с аргументами 32 и 14, а затем с аргументами 14 и 1:

print(f(32, 14) * f(14, 1))

Полный код решения будет следующий:

def f(x, y):
    if x == y:
        return 1

    if x < y:
        return 0

    if x > y:
        return f(x - 2, y) + f(x // 2, y)


print(f(32, 14) * f(14, 1))

А ответом на это задание является число 54.

Пример 1

Рассмотрим еще один пример данного типа 23 задания.

Задание 2301

«Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычесть 2
B. Найти целую часть от деления на 2

Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 38 результатом является число 2 и при этом траектория вычислений содержит число 16?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2»

Функция здесь будет буквально идентична прошлой. Единственное отличие будет в вызове этой функции: здесь вызываем f() сначала с аргументами 38 и 16, затем с 16 и 2.

def f(x, y):
    if x == y:
        return 1

    if x < y:
        return 0

    if x > y:
        return f(x - 2, y) + f(x // 2, y)


print(f(38, 16) * f(16, 2))

Ответом в этом задании будет число 36.

Тип 2

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

Начнём с такой формулировки:

Задание 2302

«Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат

Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33»

Добавим число 11 в проверку на выход за пределы допустимых значений:

if x > y or x == 11:
    return 0

В остальном решение будет такое же, как и раньше: просто переписываем операции из условия и в print() вызываем функцию с нужными аргументами.

Код здесь будет такой:

def f(x, y):
    if x == y:
        return 1

    if x > y or x == 11:
        return 0

    if x < y:
        return f(x + 1, y) + f(x * 2, y) + f(x ** 2, y)


print(f(2, 20))

В результате получаем число 37.

Пример 2

Задание 2303

«Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
А. Вычесть 1
В. Вычесть 2
С. Найти целую часть от деления на 3

Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит чисел 9 и 16?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы СВА при исходном числе 13 траектория будет состоять из чисел 4, 2, 1»

В этом задании нам необходимо добавить сразу два числа в условие:

if x < y or x == 9 or x == 16:
    return 0

Таким образом, если наше проверяемое число x будет либо меньше конечного (3), либо по траектории вычисления примет значения 9 или 16, то будет возвращаться 0. Это будет означать, что данная траектория вычислений нам не подходит.

В остальном – без изменений. Код будет таким:

def f(x, y):
    if x == y:
        return 1

    if x < y or x == 9 or x == 16:
        return 0

    if x > y:
        return f(x - 1, y) + f(x - 2, y) + f(x // 3, y)


print(f(19, 3))

В конце работы программы получаем число 180.

Тип 3

Ну и, наконец, самый интересный тип. Здесь решения будут не такими скучными, как в рассмотренных ранее типах. Но подход сохраняется тот же:

  1. Если нужно, чтобы число было в траектории: умножаем функции в print()
  2. Если нужно исключить число из траектории – добавляем его в проверку на выход за пределы допустимых значений

Формулировка здесь следующая:

Задание 2304

«Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 6
C. Найти целую часть от деления на 2

Первая команда уменьшает число на экране на 1, вторая команда уменьшает это число на 6, третья команда делит число нацело на 2. Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые исходное число 34 преобразуют в число 6, и при этом траектория вычислений содержит числа 19 и 29 и не содержит числа 24?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы АВС при исходном числе 14 траектория состоит из чисел 13, 7, 3»

Добавляем число 24 в проверку:

if x < y or x == 24:
    return 0

Функцию будем запускать сначала с аргументами 34 и 29, затем 29 и 19, в конце – 19 и 6. Всегда следите за порядком аргументов, если траектория идёт от большего к меньшему, то сначала вызываем функцию до большего, потом уже до меньшего числа.

print(f(34, 29) * f(29, 19) * f(19, 6))

Весь код решения этого задания представлен ниже:

def f(x, y):
    if x == y:
        return 1

    if x < y or x == 24:
        return 0

    if x > y:
        return f(x - 1, y) + f(x - 6, y) + f(x // 2, y)


print(f(34, 29) * f(29, 19) * f(19, 6))

Ответом на это задание будет число 115.

Пример 3

Следующий пример, конечно, не совсем подходит под этот тип. Но зато его решение будет интересно рассмотреть.

Формулировка здесь следующая:

Задание 2305

«Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 1 в число 24, и при этом никакая команда не повторяется более двух раз подряд?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы BAB при исходном числе 1 траектория состоит из чисел 2, 3, 6»

Основная сложность в этом задании заключается в необходимости делать проверку на то, что никакая команда не повторяется более двух раз.

Обычно есть два способа сделать такую проверку:

  1. Ввести целочисленную переменную, в которую будем записывать количество повторений какой-либо операции. Или же две переменные, если нужно следить за двумя операциями, как здесь
  2. Ввести переменную-строку, в которую будем записывать всю траекторию

В этой статье мы разберём второй способ. В чём его суть?

Давайте после каждой операции добавлять её букву в путь. Вот прямо как у нас указано в условии: для траектории из операций «Умножить на 2», «Прибавить 1» и «Умножить на 2» путь будет выглядеть так BAB.

Добавление операций в наш путь будет выглядеть так:

# Прибавить 1 (А)
f(x + 1, y, path + "A") 
# Умножить на 2 (B)
f(x * 2, y, path + "B")

Как теперь проверить, что операция не повторяется более двух раз подряд?

Все просто, в нашей строке с путём не должно быть подстрок AAA и BBB. Проверка может находиться либо в уже существующих (if x >y или if x==y) или в отдельном блоке if.

Мы разместим её в отдельном блоке, чтобы не нарушать установленную ранее структуру кода:

if "AAA" in path or "BBB" in path:
    return 0

Больше никаких отличий в нашем стандартном коде не будет. Полное решение данного задания выглядит так:

def f(x, y, path=""):
    if "AAA" in path or "BBB" in path:
        return 0

    if x == y:
        return 1

    if x > y:
        return 0

    if x < y:
        return (f(x + 1, y, path + "A") +
                f(x * 2, y, path + "B"))


print(f(1, 24))

После завершения работы программы на экране видим число 6, которое и является ответом на это задание.