Автор статьи: Андрей Рогов
Введение
Задание № 18 проверяет умение работать с электронными таблицами и обрабатывать целочисленные данные. Это задание считается повышенного уровня сложности, на его выполнение рекомендуют выделять примерно 8 минут.
Основная идея решения — использовать метод динамического программирования. Динамическое программирование — это такой подход, при котором сложную задачу разбивают на более простые подзадачи. Каждая из них решается только один раз, а полученные результаты сохраняются, чтобы не пересчитывать одни и те же вещи заново.
Классические примеры задач, которые можно решить этим методом:
- задача о рюкзаке: как выбрать предметы с максимальной ценностью при ограничении по весу;
- задача о наибольшей общей подпоследовательности: как найти самую длинную общую последовательность элементов в двух последовательностях;
- задача о редакционном расстоянии: сколько минимальных операций нужно для превращения одной строки в другую;
- задача о числах Фибоначчи: быстрое вычисление элементов последовательности без повторных вычислений;
- задача коммивояжёра: как найти самый короткий маршрут, проходящий через все заданные точки.
Можно заметить, что хотя в названии метода есть слово «программирование», речь идёт не обязательно о написании кода — это в целом способ решения задач. Например, в задании № 18 ЕГЭ для этого обычно используются электронные таблицы.
Впервые задание такого типа появилось именно в компьютерной версии ЕГЭ и за всё время изменилось совсем немного. Приведём изначальную формулировку.
Позже в задание добавили стены между клетками, из-за которых Робот не может пройти определённые участки. Потом появились «угловые» клетки — такие, из которых Робот вообще не может выбраться из-за стен. И в последнюю очередь появились клетки, в которые Робот не может попасть совсем.
Сначала разберём общий подход к решению задания, а затем рассмотрим один из его актуальных вариантов.
В этом задании нужно дать сразу два ответа. Очень важно внимательно прочитать, какое число нужно записать первым, а какое — вторым. Если их перепутать, задание будет оценено в 0 баллов, даже если все расчёты верны.
Динамическое программирование
Рассмотрим решение на примере входных данных из задачи. Робот начинает движение из клетки, выделенной жёлтым цветом. Монеты из этой клетки он всегда собирает в самом начале.
В клетки, выделенные синим цветом, Робот может попасть только двигаясь вправо от жёлтой клетки.
В первой (жёлтой) клетке Робот собирает 1 монету. Двигаясь вправо, количество монет накапливается так:
1 + 8 = 9\
9 + 8 = 17\
17 + 4 = 21
Аналогично считается сумма для клеток, которые находятся ниже жёлтой. В них можно попасть только, если двигаться вертикально вниз:
Таким образом, посчитано количество монет, которые Робот соберёт в тех клетках, куда можно попасть только одним путём.
Рассмотрим клетку, отмеченную зелёным цветом.
Монету в самой клетке мы всё равно заберём, независимо от того, с какой стороны в неё попадём. А вот путь — сверху или слева — определяется тем, хотим мы получить больше монет или меньше.
Если задача — набрать минимальное количество монет, выгоднее прийти сверху, потому что там сумма меньше (например, сверху собрано только 9 монет). Если интересует максимум, лучше заходить слева.
Дальше решим задачу для максимального количества монет. Для каждой клетки второй строки нужно сравнивать две клетки — ту, что сверху, и ту, что слева — и выбирать ту, где собрано монет больше.
Клетки, выделенные красным цветом, похожи на клетки первой строки: попасть в них можно только из клетки, которая находится слева.
Для всех остальных клеток всегда выбирается та, где из двух вариантов (слева и сверху) собрано больше монет.
На каждом этапе для каждой новой клетки выбирался лучший предыдущий шаг — то есть решение строилось на уже полученных значениях. Это и есть суть динамического программирования: для подсчёта новых данных используются результаты предыдущих вычислений.
На небольших примерах легко заметить, почему выбирается тот или иной путь. Но если таблица большая, как обычно бывает в задании, выбирать ходы вручную долго и неудобно. Поэтому для основной части задания удобно использовать формулы.
В самом задании речь идёт о «клетках», но в электронных таблицах правильнее говорить «ячейки». Здесь оба эти слова считаются равными по смыслу.
Задача 1. Актуальный тип задания
Решим задание с помощью LibreOffice Calc. Открываем файл и для удобства уменьшаем ширину столбцов. Далее копируем исходные данные ниже и оставляем только оформление. Это можно сделать разными способами: скопировать и удалить числа с помощью Delete или выбрать «Вставить как» → «Только форматы» при вставке.
В итоге получаются две таблицы одна под другой.
В верхней таблице — исходные данные. В нижней таблице будем хранить для каждой ячейки сумму монет, которую можно собрать, двигаясь от первой ячейки до текущей.
Для самой первой ячейки формула максимально простая — просто переписываем в неё то же значение, что и в первой ячейке с данными. Формула здесь не обязательна.
Во всех клетках под стеной действует общее правило: попасть туда можно только из клетки слева. Формула для таких случаев: взять сумму из левой ячейки и добавить значение текущей. Формула работает и для данных, и для вычисленных значений.
Помимо формулы, задаём ячейке цвет фона для лучшей наглядности, где какая формула стоит. Копируем эту формулу на все ячейки верхней строки.
Похожим образом поступаем с ячейками, у которых слева стоит стена — попасть в такие ячейки можно только сверху. Поэтому в формуле прибавляем к текущей ячейке сумму из ячейки сверху.
Теперь ищем максимальную сумму. Для этого берём первую ячейку без стен слева и сверху, у которой известны суммы у соседей (например, ячейка B23). Тут нужно взять значение из двух — сверху и слева — и выбрать максимальное. Чтобы не выбирать вручную, создаётся формула с условием.
Этот вариант удобен для задач с нестандартной логикой. В обычных экзаменационных задачах условия стандартны, поэтому формулу проще упростить, используя функцию МАКС или МИН.
Дальнейшую работу можно организовать двумя способами: сначала заполнить формулы для стен, потом для остальных ячеек, либо наоборот. Второй способ обычно проще. Копируем ячейку B23 со сформированной формулой на остальные нужные ячейки, вставляя только формулы — так оформление стен сохранится.
Получим заполненную таблицу.
Теперь займёмся копированием формул в ячейки под стеной. Любую из зелёных ячеек копируем во все ячейки, которые расположены под стеной, а формулу из красной — в ячейки справа от стены.
Особое внимание нужно уделить ячейкам, выделенным красным цветом. В них Робот не сможет попасть, так как может двигаться только вправо и вниз. Поэтому числа в этих ячейках нужно удалить, чтобы их не учитывала таблица.
Зелёным цветом выделены «угловые» ячейки. Именно там искать нужное число для ответа. Максимальное значение в зелёных ячейках — это 2362. Это и будет максимальная сумма.
Чтобы найти минимальное число, достаточно в формулах заменить функцию МАКС на функцию МИН. Это делается через замену: меню «Правка» → «Найти и заменить» или Ctrl+H.
Формулы пересчитываются заново, в ячейках появляются новые значения для поиска минимальной суммы.
Теперь ищем наименьшее число среди зелёных ячеек — это 1205. Получаем итог: ответ 2362 1205.
Заключение
В статье мы подробно разобрали метод динамического программирования на примере решения задания № 18 из ЕГЭ по информатике.
Основные плюсы динамического программирования:
- можно решать задачи с большими объёмами данных;
- простая автоматизация расчётов;
- универсальность;
- наглядность промежуточных результатов.
Для решения таких задач советуем всегда внимательно разбирать условие, использовать цветовое оформление для наглядности, и проверять правильность формул на маленьких примерах.
Типичные ошибки при решении:
- неверное начальное значение;
- ошибки в формулах при наличии стен;
- пропуск «угловых» клеток;
- неправильное понимание условия;
- путаница при записи итогового ответа.
Таким образом, динамическое программирование — мощный инструмент для решения задач оптимизации. При правильном подходе этот метод позволяет эффективно справляться даже со сложными заданиями. Освоить этот метод — важная часть подготовки к успешной сдаче ЕГЭ по информатике. Для подготовки к этим заданиям советуем попробовать разные способы решения и обязательно решить подборку задач для практики в тренажёре ЕГЭ по информатике Яндекс Учебника.