Если вы разобрались с заданиями 16, 19-21 23 не составит труда. Задание 23 очень похоже на задания по теории игр и на задание 16, решаемое через рекурсию.
Задание 23 в демоверсии на 2025г. выглядит следующим образом:
Сразу покажу решение, которого и стоит придерживаться, на мой взгляд, на ЕГЭ: мало кода и по сути повторяет программку для 19-21 задач.
Используем это задание, чтобы поглубже разобраться в программировании.
Решим задание 23 без компьютера
Числа в данном задании совсем небольшие и решить это задание можно буквально на пальцах. Правда немного надо разбираться в комбинаторике.
Предварительно решим такую задачку: из пункта А в пункт В — n дорог, а из пункта В в пункт С — m дорог. Сколько способов добраться из пункта А в пункт С? Если посмотреть на рисунок, то ответ напрашивается сам собой.
Даже не вспоминая комбинаторики, можно заметить, что на одну дорогу из А в В, приходиться m вариантов дорог из В в С, а для n дорог количество способов будет равно произведению n*m.
По аналогии решается и задание 23. Подсчитаем количество способов попасть из 38 в 16 и количество способов попасть из 16 в 2. Произведение этих двух чисел даст ответ.
Дерево вариантов
Чтобы рассмотреть все возможные ситуации, удобнее всего воспользоваться деревом возможных вариантов. Данное понятие широко используется в комбинаторике.
Дерево вариантов (возможностей) дает наглядное представление о том, как получаются всевозможные результаты и помогает решать разнообразные задачи, касающиеся перебора вариантов происходящих событий.
С помощь такого дерева можно упорядочить многошаговый процесс.
Попробуем проанализировать с помощью дерева, как из 38 можно получить 16:
Получим всего 3 способа. Расчеты в дереве вариантов ведутся до тех пор, пока есть надежда получить 16.
Аналогично, посчитаем количество способов из 16 получить 2:
В этом случае получается 12 способов.
И ответ к демоверсии задания №23: 3*12 = 36
Обратите внимание, что использование дерева вариантов позволяет наглядно решать многие комбинаторные задачи
В информатике дерево — это граф, где любые две вершины связаны только одним путем. Т.е. в таком графе нет циклов, есть один входящий путь и может быть несколько исходящих. Узел, для которого нет входящих путей, называется корнем, а узлы из которых ничего не исходит — это листья, остальные ветви.
Динамическое программирование
Как только в задаче возникает вопрос: сколько способов или найдите максимум (минимум), как в задании 18, опытный программист сразу смотрит в сторону динамического программирования.
Термин “динамическое программирование” пришел из математики, и слово “программирование”, в данном случае, не имеет отношение к написанию кода, просто так исторически сложилось.
Представим себе числовую ось, по которой Исполнитель может прыгать как кузнечик (традиционно знакомство с динамическим программированием начинается с задачи о кузнечике).
Для числа 38 будет один способ попасть на 38: по условию задачи Исполнитель изначально находится там. На число 37 - нет никакой возможности попасть - 0 способов, на число 36 - 1 способ (38-2=36). Получается, что двигаясь вдоль числовой оси к цели, мы можем подсчитать количество способов для конкретного числа, если известны (уже подсчитаны) предыдущие значения.
Заполнять таблицу руками долго, да и можно допустить ошибку по невнимательности. Запрограммируем данное решение на Python.
Заведем массив (список в Python) dp[ ]. Индекс i будет указывать на значение на числовой оси, а хранимая величина - количество способов попасть на это i.
Попасть на значение i можно из:
- значения i+2
- значения i*2
- значения i*2+1 (целочисленное деление на 2 приведет к i)
Если двигаться и в обратном направлении (от 16 к 38), то напрашивается рекурсивная функция. Решение задач динамического программирования через рекурсию называют ленивой динамикой.
И действительно решение задания 23 ленивой динамикой просто и наглядно.
(Решение приведено в начале статьи).
Если рекурсия считает медленно (когда у Исполнителя много вариантов) , нужно применить декоратор кэширования @functools.lru_cache(None).