Навигация по странице
О задании
В задании 18 ЕГЭ по информатике нам дано некоторое квадратное поле, по которому может перемещаться виртуальный робот-сборщик монет. Поле это представлено в виде электронной таблицы, где в каждой ячейке записано число от 1 до 100 – количество монет, которое достанется нашему роботу, если он попадёт на эту ячейку.
На перемещения робота накладываются некоторые ограничения. Так, в зависимости от задания, он может перемещаться только по определённым направлениям: вправо и вниз, влево и вверх или еще какие-либо вариации этих команд. Также на самом поле присутствуют стены, роль которых выполняют границы ячеек. Соответственно, проходить сквозь этим стены робот не может.
Правда в редких случаях авторы наделяют робота способностями к телепортации. Однако, такие формулировки заданий с телепортациями робота не встречаются в официальных вариантах ЕГЭ по информатике и рассматривать их решение мы не будем.
В результате данного задания необходимо подсчитать количество монет, которое может собрать робот, перемещаясь из начальной ячейки в конечную. Конечной будет называться ячейка, с обеих сторон ограниченная стенами, преодолеть которые робот не в состоянии. Например, при наличии команд «вправо» и «вниз» такой ячейкой будет правая нижняя.
В ответ нас просят дать два числа: максимальную и минимальную сумму, которую может собрать робот за время своего путешествия по ячейкам. Иными словами, нам здесь требуется найти оптимальный путь в матрице (таблице значений). А решение подобных задач сводится к динамическому программированию.
Динамическое программирование
Представьте ситуацию: вы пишете программу для навигатора, который должен найти самый быстрый маршрут из точки А в точку Б в большом городе. Или создаёте игру, где персонаж должен собрать максимум золота, перемещаясь по подземелью. Или решаете задачу на ЕГЭ по информатике, где робот собирает монеты на поле 30×30 клеток.
Что общего у всех этих задач? Нужно найти оптимальный путь среди множества возможных вариантов. И здесь начинаются проблемы.
Давайте возьмём простой пример: поле 3×3, где в каждой клетке лежит какое-то количество монет. Робот начинает путь в левом верхнем углу и должен дойти до правого нижнего, двигаясь только вправо или вниз. Нужно собрать максимум монет.
Первая мысль: «Давайте просто переберём все возможные пути».
Путь 1: вправо → вправо → вниз → вниз
Сумма: 1 + 5 + (-2) + 1 + 2 = 7
Путь 2: вправо → вниз → вправо → вниз
Сумма: 1 + 5 + (-3) + 1 + 2 = 6
И так далее… Всего для поля 3×3 существует 6 различных путей. Ну ничего, можно перебрать.
А теперь задумайтесь: сколько путей на поле 4×4? Уже 20. На поле 5×5? 70 путей. А на реальном экзаменационном поле 30×30 клеток количество возможных путей превышает 30 миллиардов!
Попробуйте перебрать 30 миллиардов вариантов вручную или даже на компьютере – задача станет практически нерешаемой. Даже мощный процессор будет считать несколько минут, а то и часов. На экзамене у вас такого времени точно нет.
Но что, если эту же задачу можно решить за несколько секунд, проверив всего 900 клеток вместо 30 миллиардов путей? Звучит как волшебство, но это реальность.
Секрет кроется в динамическом программировании – методе, который превращает задачу поиска среди миллиардов вариантов в простое заполнение таблицы. Вместо того чтобы строить все возможные пути, мы на каждом шаге запоминаем только одно число – лучший результат до этой точки. И этого достаточно!
Сравните:
- Перебор всех путей на поле 30×30: ~30 000 000 000 операций
- Динамическое программирование на том же поле: ~900 операций
Разница – в 30 миллионов раз! Именно поэтому динамическое программирование используется в навигаторах, играх, системах искусственного интеллекта и, конечно же, в задачах ЕГЭ по информатике.
Динамическое программирование – это метод решения сложных задач путём разбиения их на более простые подзадачи и запоминания результатов этих подзадач, чтобы не решать их повторно.
Звучит довольно сложно, не так ли? На самом деле принцип очень простой. Представьте, что вы едете из своего города в другой город на машине, и по дороге в каждом населённом пункте можете заправиться.
На разных заправках разные цены, и вам нужно потратить минимум денег на бензин. Из каждого города можно поехать в несколько разных направлений – есть множество маршрутов.
Глупый подход: для каждого возможного маршрута (а их могут быть тысячи!) пересчитывать всю стоимость бензина от начала до конца.
Умный подход: для каждого города по пути записать одно число – «сколько минимум денег мне нужно потратить, чтобы добраться до этого города». Когда приезжаете в следующий город, просто смотрите на уже посчитанные результаты для предыдущих городов и выбираете самый дешёвый вариант.
Вот и весь фокус динамического программирования: запоминать промежуточные результаты, чтобы не пересчитывать одно и то же много раз.
В динамическом программировании существуют три основных принципа:
- Оптимальность подзадач: если мы знаем оптимальное решение для маленькой части задачи, мы можем использовать его для решения большей части.
- Перекрывающиеся подзадачи: одни и те же маленькие задачи встречаются много раз при решении большой задачи.
- Запоминание результатов: вместо того чтобы решать одну и ту же подзадачу несколько раз, мы один раз решаем её и запоминаем ответ.
Использование методов динамического программирования
Но давайте вернёмся к нашему примеру поля 3×3 и попробуем решить поставленную задачу, но уже не простым перебором, а с помощью динамического программирования.
Нам не нужно строить все возможные пути решения, достаточно на каждом этапе выбирать наиболее выгодный путь. То есть нам важнее не куда мы можем попасть из выбранной ячейки, а наоборот: из какой ячейки нам выгоднее прийти в нужную.
Так как нам доступно передвижение только вниз или вправо, то две ячейки в первом столбце (1, -1) и в первой строке (1, 5) имеют только два возможных маршрута:
- По прямой вниз, пока не дойдём до последней строки (2, 3, 2)
- По прямой вправо, пока не дойдём до самого правого столбца (-2, 1, 2)
Для последних ячеек первого столбца (2) и первой строки (-2) выбор уже не такой богатый: это либо движение только вправо, либо только вниз, соответственно.
С возможными передвижениями разобрались, но где нам подсчитывать количество монет, собранное за каждое перемещение? Давайте для этого составим вторую таблицу. В ней будем писать в каждой ячейке суммарное количество монет за все перемещения к ней.
Например, в крайней правой ячейке первой строки будет число 4. Его мы получили следующим образом: к начальному значению 1 прибавили число 5 и число -2 (1 + 5 – 2 = 4). Тогда как в последней ячейке первого столбца будет значение 2 (1 + (-1) + 2).
Но на центральной ячейке уже становится интереснее: в неё можно попасть из двух соседних: верхней со значением 6 и левой со значением 0.
Логично, что для получения максимального значения мы выбираем путь сверху вниз. Тогда суммируем уже полученное значение 6 с числом -3 и получаем в центральной ячейке число 3. В противном случае у нас бы получилось число -3 (при движении вправо мы от 0 отняли бы число 3).
Аналогично поступим и со следующими ячейками. В третью ячейку из второй строки выгоднее будет попасть из ячейки, в которой значение 4 (4 + 1 = 5).
Во вторую ячейку третьей строки также попадаем с верхней ячейки со значением 3.
В оставшуюся ячейку, очевидно, будет выгоднее попасть слева, с ячейки, у которой значение 6.
В итоге мы решили задачу, максимально возможное значение при перемещении с левой верхней в правую нижнюю ячейку – число 8.
Сумма на пути у нас была следующая: 1 + 5 – 3 + 3 + 2 = 8.
Теперь давайте сделаем вывод по данному решению. Если требуется найти максимальную сумму на пути, то в случае «развилки», когда перед нами стоит выбор из какой ячейки лучше прийти в текущую, мы выбираем ячейку с большей суммой и прибавляем к этой сумме значение текущей ячейки.
Со значениями на границах проще: нам не приходится выбирать максимальное, так как путь в текущую только один: сверху или слева.
Давайте выразим все сказанное в виде формул. Пусть исходная таблица будет А, а таблица , которую мы будем получать в процессе суммирования значений будет B.
Начальные значения (левые верхние ячейки) у нас будут одинаковые, то есть собранная сумма равна значению в клетке:
B[0][0] = A [0][0]
Выведем формулу перехода на ячейку i-ой строки и j-ого столбца:
B[i][j] = max(B[i-1][j], B[i][j-1]) + A[i][j]
Что тут написано? Значение в ячейке i-ой строки и j-ого столбца равно сумме максимального из значений ячеек сверху и слева и значению из той же строки и столбца исходной таблицы.
В нашем примере это выглядело так:
B[1][1] = max(B[0][1], B[1][0]) + A[1][1] = max(6, 0) + (-3) = 6 – 3 = 3
В случае, когда слева или сверху расположена граница, то значение с этой стороны отсутствует, так что выбирать максимальное не из чего и суммировать будем только значение из прошлой ячейки и соответствующей ячейки исходной таблицы.
Например, для верхних строк можем привести такую формулу:
B[0][j] = B[0][j-1] + A[0][j]
В нашей задачи было так:
B[0][1] = B[0][0] + A[0][1] = 1 + 5 = 6
Тогда для крайнего левого столбца приведём такую формулу:
B[i][0] = B[i-1][0] + A[i][0]
Если же требуется найти не максимальную, а минимальную сумму за весь пусть, то алгоритм будет аналогичным, только выбирать будем не максимальное значение, а минимальное.
Алгоритм решения
Давайте составим алгоритм решения любого задания 18:
- Ниже исходной таблицы начинаем строить новую, с суммами значений
- Значение начальной ячейки переносим. Строку и столбец с ней заполняем по формуле:
<Значение предыдущей ячейки> + <Значение соответствующей ячейки исходной> - Для остальных значений в таблице используем формулу
МАКС(<Значение ячейки с одной стороны>,< Значение ячейки с другой стороны >)+ <Значение соответствующей ячейки исходной>. Так, если двигаемся только вправо и вниз то формула следующая:МАКС(<Значение ячейки слева>,< Значение ячейки сверху >)+ <Значение соответствующей ячейки исходной> - Добавляем стены из исходной таблицы с помощью функции «Формат по образцу»
- Отмечаем конечные точки. Если двигаемся только вправо и вниз, то это точки со стенами справа и снизу
- Удаляем значения с тех ячеек, в которые Робот не может попасть. Например, сверху от стены
- Редактируем формулы вдоль стен (убираем функцию
МАКС()и оставляем только сумму двух ячеек) - Выбираем наибольшее значение из конечных точек
- Меняем формулу
МАКС()наМИН()с помощью инструмента «Заменить…» - Выбираем наименьшее значение из конечных точек
Теперь рассмотрим работу этого алгоритма на конкретных примерах.
Задание 1814
«Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа – сначала максимальную сумму, затем минимальную.»
Откроем приложенный к заданию файл и увидим таблицу с числами в диапазоне от А1 до T20.
Выделяем всю таблицу и копируем её (Ctrl+C). Переходим к ячейке А22 и вставляем (Ctrl+V) таблицу. Сразу удаляем все значения (клавиша Del), кроме начального, которое находится в ячейке А22.
Заполняем первые столбец и строку этой таблицы. В ячейке B22 пишем формулу «=A22+B1» и растягиваем её до T22.
Аналогично, в ячейке А23 используем формулу «=A22+A2» и растягиваем до А41.
Далее заполняем «внутренние» ячейки таблицы. В B23 пишем следующую формулу:
«=МАКС(A23;B22)+B2»
Эту формулу растягиваем вправо и вниз, пока вся таблица не заполнится.
При этом мы потеряли границы ячеек с исходной таблицы. Чтобы их вернуть выделяем исходную таблицу, выбираем на панели сверху пункт «Формат», в нём инструмент «Копировать формат» (курсор при этом принимает форму наклоненной банки с краской).
Выделяем ячейки от А22 до Т41 и вставляем скопированный формат.
Теперь отметим зелёным цветом все возможные конечные точки. Это точки, справа и снизу от которых расположены стены. Таких точек в данной задачи всего 4.
Из этих значений мы и будем выбирать ответ, но пока еще рано это делать. Нам необходимо изменить формулы вблизи стен. В данной задаче меняются формулы справа и снизу от стен.
Ячейки снизу от стен отметим оранжевым цветом.
Ячейки справа от стен – синим цветом.
Еще обратите внимание, что в группу ячеек от M31 до N36 робот никак попасть не сможет – туда попросту нет путей сверху и слева. Этот диапазон выделим красным.
Теперь будем править формулы в подкрашенных ячейках. Начнём с оранжевых. Оставляем только сумму значения слева и соответствующего значения из исходной таблицы (можно просто скопировать формулу с ячеек 22 строки).
Для ячеек справа от стен (синих) – только сумма значения сверху и из исходной таблицы.
Из значений в конечных точках выбираем большее. У нас это 2362 (ячейка S39). Это и будет первый ответ на данное задание.
Теперь выбираем инструмент «Заменить» (Ctrl+H). В поле «Найти» пишем «МАКС», в поле «Заменить на» пишем «МИН». Тем самым мы меняем во всех формулах функцию МАКС() на функцию МИН().
Видим, как поменялись все значения. Находим минимальное в конечных точках. Здесь таким значением является 1205 (ячейка O41).
Таким образом ответ на данное задание будет следующий: 2362 1205.
Пример 1
Для закрепления решим еще одно задание со схожей формулировкой:
Задание 1811
«Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.»
Алгоритм решения всех остальных задач будет идентичным, так что подробно останавливаться на каждом шаге уже не будем.
Открываем приложенный к заданию файл.
Копируем таблицу ниже и заполняем накопленными суммами.
Теперь выделяем все ячейки справа и снизу от стен, конечные ячейки и те, в которые робот никак попасть не сможет.
Поправим формулы во всех граничных ячейках и ищем максимальное значение среди конечных.
Максимальным является значение в ячейке T41 – 2132.
Теперь заменяем во всех формулах «МАКС» на «МИН» и ищем минимальное значение в зелёных ячейках.
Таким значением будет 663.
В итоге ответ на это задание – числа 2132 и 663.
Пример 2
Теперь рассмотрим задание, в котором робот будет передвигаться только влево и только вверх.
В целом алгоритм здесь остаётся прежний, разве что формулы «отзеркаливаются».
Формулировка будет такая:
Задание 1804
«Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и сверху ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую верхнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой нижней клетки в конечную клетку маршрута.
В ответе укажите два числа – сначала минимальную сумму, затем максимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.»
Как обычно, открываем прикреплённый файл с электронной таблицей.
Копируем её ниже. Но оставляем теперь левую нижнюю ячейку (А41)!
Формулы также будут немного другие: для ячеек с левой границей будем использовать такую формулу: «=<Значение нижней ячейки> + <Значение соответствующей ячейки исходной таблицы>». То есть в ячейке А40 будет такая формула: «=A41+A19».
Для ячеек с границей снизу, соответственно: «=<Значение левой ячейки> + <Значение соответствующей ячейки исходной таблицы>». Следовательно, в ячейке B41 формула будет такой: «=A41+B20».
Заполняем таблицу значениями и копируем формат исходной.
Выделяем конечные ячейки и те, у которых граница слева или снизу. Также отметим, что в зону от J38 до T41 робот попасть не сможет.
Поправляем все формулы около границ и выбираем наибольшее значение в зелёных ячейках.
В нашем случае – это 2828.
Производим замену «МАКС» на «МИН» и ищем теперь уже минимальное значение среди конечных ячеек. У нас это 743.
Обратите внимание, что в ответ надо дать сначала минимальное количество, затем максимальное: 743 2828.