Данное задание проверяет умение использовать электронные таблицы для обработки целочисленных данных.
Условие задачи
Квадрат разлинован на n × m клеток. Робот перемещается по клеткам, за одно перемещение выполняя одну из двух команд: «вправо» или «вниз». Команда «вправо» перемещает робота в соседнюю правую клетку, команда «вниз» — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками могут быть внутренние стены; сквозь стену робот пройти не может. В каждой клетке лежит монета достоинством от 1 до 100. Посети клетку, робот забирает монету. Это относится к начальной и конечной клеткам. Необходимо определить максимальную и минимальную сумму, которую может собрать робот, пройдя из левой верхней клетки в правую нижнюю. В ответе указать два числа: сначала максимальную сумму, затем минимальную.
Решение задачи методом динамического программирования
Для решения используется динамическое программирование. Вычисления проводятся поэтапно. Робот использует две команды: «вправо» и «вниз».
- Вспомогательная таблица: Создаётся копия таблицы с монетами. В ней будут рассчитываться накопленные суммы для каждой клетки.
- Левая верхняя клетка: В левую верхнюю клетку вспомогательной таблицы записывается значение количества монет из соответствующей клетки исходной таблицы.
- Верхняя граница: Для клеток верхней границы робот может двигаться только вправо. Значение каждой клетки — сумма монет в предыдущей и текущей клетках исходной таблицы. Формула расчёта: =B1+A2 (где B1 — предыдущая клетка, A2 — текущая). Формула копируется до конца границы.
- Левая граница: Для клеток левой границы робот может двигаться только вниз. Значение каждой клетки — сумма монет в предыдущей и текущей клетках исходной таблицы. Формула расчёта: =A1+A2 (где A1 — предыдущая клетка, A2 — текущая). Формула копируется до конца границы.
- Внутренние клетки: Для внутренних клеток робот может прийти из двух соседних клеток: сверху или слева. Для максимальной суммы используется функция МАКС(), для минимальной — МИН(). Значение каждой клетки — сумма монет в текущей клетке исходной таблицы и максимального (или минимального) значения из двух соседних клеток вспомогательной таблицы. Формула для максимальной суммы: =A2+МАКС(B1;A1). Формула для минимальной суммы: =A2+МИН(B1;A1). Формулы копируются для всех внутренних клеток.
- Учёт границ: При наличии внутренних стен формулы корректируются с учётом возможности движения только в одном направлении.
- Результат: Максимальная и минимальная суммы находятся в правой нижней клетке вспомогательной таблицы.
Решение задачи 18 из демоверсии ЕГЭ по информатике 2022 года основано на динамическом программировании. Поэтапное заполнение вспомогательной таблицы позволяет определить максимальную и минимальную сумму монет, которую может собрать робот, двигаясь из левой верхней клетки в правую нижнюю, с учётом ограничений, накладываемых стенами.