В этой статье рассмотрим основные способы и формулы для решения задания № 18 ЕГЭ по информатике. Суть задачи заключается в том, чтобы определить наибольшее или наименьшее количество монет, которое робот сможет собрать, перемещаясь по заданному маршруту из начальной точки в конечную. Для её решения используется динамическое программирование: на каждом шаге выбирается локальный минимум или максимум, что позволяет получить оптимальный итоговый результат.
Термины, которые будем использовать: алгоритм, динамическое программирование, робот-сборщик.
Алгоритм
Рассмотрим пошаговый алгоритм решения задачи в Excel:
Открыть файл Excel с исходным полем (стоимости монет). Создать новый лист или скопировать таблицу рядом для расчётов.
В ячейку B2 (или A1 в зависимости от формата) скопировать значение первой клетки.
Первый столбец: каждая следующая ячейка = предыдущая ячейка + монета в текущей клетке (робот идёт только вниз).
Первая строка: каждая следующая ячейка = предыдущая ячейка + монета в текущей клетке (робот идёт только вправо).Для остальных ячеек формула выглядит так:- Поиск максимальной суммы: =ЯЧЕЙКА_С_МОНЕТОЙ + МАКС(ЯЧЕЙКА_СВЕРХУ; ЯЧЕЙКА_СЛЕВА).
- Поиск минимальной суммы: =ЯЧЕЙКА_С_МОНЕТОЙ + МИН(ЯЧЕЙКА_СВЕРХУ; ЯЧЕЙКА_СЛЕВА).
Протянуть эту формулу (например, из B3) на всю таблицу. Это автоматически заполнит все клетки накопленными суммами.
Найти значения в «угловых» клетках (на правом и нижнем краях поля), где путь заканчивается. Определить среди них максимальное и минимальное значения.
Сначала можно использовать формулу =МАКС(), получить первый ответ, затем заменить её на МИН и найти второй.
Горячие клавиши
| Действие | Сочетание (Windows) | Примечание |
|---|---|---|
| Копировать ячейку | Ctrl + C | Копирование формулы или значения |
| Вставить | Ctrl + V | Вставка скопированного |
| Отменить действие | Ctrl + Z | Вернуть шаг назад |
| Заполнить всю таблицу | Ctrl + D (вниз), Ctrl + R (вправо) | Скопировать формулу из верхней/левой ячейки во все выделенные |
| Функция МАКС | Вручную или через мастера | =МАКС(число1; число2) |
| Функция МИН | Вручную или через мастера | =МИН(число1; число2) |
| Функция ЕСЛИ | Вручную | =ЕСЛИ(условие; значение_если_истина; значение_если_ложь) |
| Функция ABS | Вручную | =ABS(число) — модуль числа |
| Открыть окно «Найти и заменить» | Ctrl + H | Можно одним нажатием заменить все МАКС на МИН, чтобы получить минимальные суммы |
Практикум
Применим наш алгоритм к реальным задачам 2025 года, которые встретились на ЕГЭ.
Общее условие
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа: сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Задание 1
Скопируем исходную таблицу и вставим её справа, сохранив только формат без значений. Добавим сверху новую строку. В левую верхнюю ячейку новой таблицы введём формулу =МАКС(U2;V1)+A2 и протянем её на весь диапазон. После этого вернём исходное форматирование таблицы.
Удалим все значения из клеток, расположенных справа или снизу от стены:
Справа от стены можно идти только сверху вниз, под стеной — только слева направо.
Заполним пустые ячейки новой формулой:
Серым цветом выделены слепые зоны робота, в них он побывать не может. Жёлтым цветом выделены конечные клетки маршрута.
Максимальная сумма — 1608.
Меняем МАКС на МИН в формулах, получаем минимальную сумму — 767.
Ответ: 1608 767.
Задание 2
Сначала создадим расчётную таблицу: скопируем исходное поле и вставим его справа, оставив только формат без значений. Добавим сверху новую строку. В левую верхнюю ячейку новой таблицы введём формулу =МАКС(U2;V1)+A2 и протянем её на весь диапазон. После этого восстановим исходное форматирование.
Удалим значения из ячеек, расположенных справа и снизу от стен:
При этом учитываем ограничения: справа от стены движение возможно только сверху вниз, а под стеной — только слева направо.
Оставшиеся пустые ячейки заполним по той же формуле:
Серым цветом обозначены недостижимые зоны (робот туда попасть не может), жёлтым — конечные клетки маршрута.
Максимальная сумма — 2132.
Заменим в формулах МАКС на МИН и получим минимальную сумму — 663.
Ответ: 2132 663.
Задание 3
Скопируем начальную таблицу, вставим её справа без значений, сохранив только формат. Добавим новую строку сверху и пропишем в левой верхней ячейке новой таблицы формулу =МАКС(U2;V1)+A2, протянем её на все ячейки таблицы, вернём изначальный формат.
Удалим все значения из клеток, расположенных справа или снизу от стены:
Справа от стены можно идти только сверху вниз, под стеной — только слева направо.
Заполняем пустые ячейки новой формулой:
Серым цветом выделены слепые зоны робота — в них он побывать не может, жёлтым цветом выделены конечные клетки маршрута.
Максимальная сумма — 1608.
Меняем МАКС на МИН в формулах, получаем минимальную сумму — 767.
Ответ: 1608 767.
Заключение
В статье мы разобрали, как решать задание № 18 ЕГЭ по информатике в электронной таблице с помощью динамического программирования. Теперь ты умеешь строить расчётную таблицу, находить максимальную и минимальную сумму пути с помощью функций МАКС и МИН, учитывать стены и недостижимые клетки. Эти навыки помогают быстро проверять решение и автоматизировать вычисления в Excel.
После изучения темы ты сможешь самостоятельно решать задачи на поиск оптимального маршрута робота. Главное — внимательно анализировать поле, правильно задавать формулы и проверять конечные клетки маршрута.
Автор статьи
