Алгоритм решения задания 18 ЕГЭ по информатике
Навигация по странице
О задании
В задании 18 ЕГЭ по информатике нам дано некоторое квадратное поле, по которому может перемещаться виртуальный робот-сборщик монет. Поле это представлено в виде электронной таблицы Excel, где в каждой ячейке записано число от 1 до 100 — количество монет, которое достанется нашему роботу, если он попадёт на эту ячейку.
На перемещения робота накладываются некоторые ограничения. Так, в зависимости от задания, он может перемещаться только по определённым направлениям: вправо и вниз, влево и вверх или еще какие-либо вариации этих команд. Также на самом поле присутствуют стены, роль которых выполняют границы ячеек. Соответственно, проходить сквозь этим стены робот не может.
Правда в редких случаях авторы наделяют робота способностями к телепортации. Однако, такие формулировки заданий с телепортациями робота не встречаются в официальных вариантах ЕГЭ по информатике и рассматривать их решение мы не будем.
В результате данного задания необходимо подсчитать количество монет, которое может собрать робот, перемещаясь из начальной ячейки в конечную. Конечной будет называться ячейка, с обеих сторон ограниченная стенами, преодолеть которые робот не в состоянии. Например, при наличии команд «вправо» и «вниз» такой ячейкой будет правая нижняя.
В ответ нас просят дать два числа: максимальную и минимальную сумму, которую может собрать робот за время своего путешествия по ячейкам. Иными словами, нам здесь требуется найти оптимальный путь в матрице (таблице значений). А решение подобных задач сводится к динамическому программированию.
Динамическое программирование
Динамическое программирование — это метод решения задач, который позволяет эффективно находить оптимальные решения для сложных проблем. Он основан на идее разбиения задачи на более мелкие подзадачи и использовании результатов предыдущих решений для ускорения процесса поиска решения.
Звучит довольно сложно, не так ли? Честно говоря, непосредственно для ЕГЭ по информатике, знания алгоритмов динамического программирования избыточно. Но давайте разберемся с тем, как использовать эти алгоритмы для решения задания 18.
Для начала рассмотрим общие подходы. Упростим немного задание и вместо большого поля в 30 на 30 ячеек со стенами рассмотрим поле 3 на 3.
Здесь у нас также есть в каждой ячейке числа, которые суммируются с предыдущим накопленным значением при переходе в ячейку. Предположим, что нам надо попасть с левой верхней в правую нижнюю ячейку, и получить максимальное значение. Передвигаться может только вправо или вниз.
Первое, что приходит на ум: будем просто перебирать все возможные пути от одной ячейки до другой. Например, так: сначала прибавим 5, потом прибавим -2, затем 1 и 2. Получим следующее: 1 + 5 – 2 + 1 + 2 = 7.
Здорово, один путь посчитали. Теперь повторим это действие еще много раз и когда-нибудь да получим ответ.
Согласитесь, не самый надёжный и быстрый способ решения? Здесь и приходит на помощь динамическое программирование. Нам нужно не строить все возможные пути решения, а на каждом этапе выбирать наиболее выгодный путь. То есть нам важнее не куда мы можем попасть из выбранной ячейки, а наоборот: из какой ячейки нам выгоднее прийти в нужную.
Рассмотрим этот подход на примере. Так как нам доступно передвижение только вниз или вправо, то все ячейки в первом столбце и в первой строке имеют только один возможный маршрут: по прямой вниз для столбца и по прямой вправо для строки.
Запишем в каждой ячейке накопленную сумму за все перемещения к ней. Например, в крайней правой ячейке первой строки будет число 4. Его мы получили следующим образом: к начальному значению 1 прибавили число 5 и число -2 (1 + 5 – 2 = 4).
Но на центральной ячейке уже становится интереснее: в неё можно попасть из двух соседних: верхней со значением 6 и левой со значением 0.
Логично, что для получения максимального значения мы выбираем путь сверху вниз. Тогда суммируем уже полученное значение 6 с числом -3 и получаем в центральной ячейке число 3.
Аналогично поступим и со следующими ячейками. В третью ячейку из второй строки выгоднее будет попасть из ячейки, в которой значение 4.
Во вторую ячейку третьей строки также попадаем с верхней ячейки со значением 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
Если же требуется найти не максимальную, а минимальную сумму за весь пусть, то алгоритм будет аналогичным, только выбирать будем не максимальное значение, а минимальное.
Алгоритм решения задания 18
Для начала давайте составим алгоритм решения любого задания 18:
- Ниже исходной таблицы начинаем строить новую, с суммами значений
- Значение начальной ячейки переносим. Строку и столбец с ней заполняем по формуле:
<Значение предыдущей ячейки> + <Значение соответствующей ячейки исходной> - Для остальных значений в таблице используем формулу
МАКС(<Значение ячейки с одной стороны>,< Значение ячейки с другой стороны >)+ <Значение соответствующей ячейки исходной>. Так, если двигаемся только вправо и вниз то формула следующая:МАКС(<Значение ячейки слева>,< Значение ячейки сверху >)+ <Значение соответствующей ячейки исходной> - Добавляем стены из исходной таблицы с помощью функции «Формат по образцу»
- Отмечаем конечные точки. Если двигаемся только вправо и вниз, то это точки со стенами справа и снизу
- Удаляем значения с тех ячеек, в которые Робот не может попасть. Например, сверху от стены
- Редактируем формулы вдоль стен (убираем функцию
МАКС()и оставляем только сумму двух ячеек) - Выбираем наибольшее значение из конечных точек
- Меняем формулу
МАКС()наМИН()с помощью инструмента «Заменить…» - Выбираем наименьшее значение из конечных точек
Теперь рассмотрим работу этого алгоритма на конкретных примерах.
Пример 1
Формулировка задания следующая:
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Откроем приложенный к заданию файл и увидим таблицу с числами в диапазоне от А1 до T20.
Выделяем всю таблицу и копируем её (Ctrl+C). Переходим к ячейке А22 и вставляем (Ctrl+V) таблицу. Сразу удаляем все значения, кроме начального, которое находится в ячейке А22.
Заполняем первые столбец и строку этой таблицы. В ячейке B22 пишем формулу =A22+B1 и растягиваем её до T22.
Аналогично, в ячейке А23 используем формулу =A22+A2 и растягиваем до А41.
Далее заполняем «внутренние» ячейки таблицы. В B23 пишем следующую формулу:
=МАКС(A23;B22)+B2
Эту формулу растягиваем вправо и вниз, пока вся таблица не заполнится.
При этом мы потеряли границы ячеек с исходной таблицы. Чтобы их вернуть выделяем исходную таблицу, выбираем на ленте «Главная» инструмент «Формат по образцу» (курсор при этом принимает форму знака + с малярной кистью справа) и выделяем ячейки от А22 до T41.
Теперь отметим все возможные конечные точки. Это точки, справа и снизу от которых расположены стены. Таких точек в данной задачи всего 5.
Из этих значений мы и будем выбирать ответ, но пока еще рано это делать. Нам необходимо изменить формулы вблизи стен. В данной задаче меняются формулы справа и снизу от стен (выделены синим).
Для ячеек снизу от стен мы в формуле оставляем только сумму значения слева и соответствующего значения из исходной таблицы. Для ячеек справа от стен — только сумма значения сверху и из исходной таблицы.
Из значений в конечных точках выбираем большее. У нас это 2671 (выделено зелёным). Это и будет первый ответ на данное задание.
Теперь выбираем инструмент «Заменить» (Ctrl+H). В поле «Найти» пишем «МАКС», в поле «Заменить на» пишем «МИН». Тем самым мы меняем во всех формулах функцию МАКС() на функцию МИН().
Видим, как поменялись все значения. Находим минимальное в конечных точках. Здесь таким значением является 419 (выделено зелёным).
Таким образом ответ на данное задание будет следующий: 2671 419
Пример 2
Рассмотрим аналогичную задачу, но здесь Робот будет передвигаться только влево и только вверх.
В целом алгоритм здесь остаётся прежний, разве что значения «отзеркаливаются».
Также открываем файл и видим таблицу от А1 до P16.
Копируем её и вставляем ниже, начиная с ячейки A18. Но теперь оставляем только правое нижнее значение в ячейке P33.
Заполняем значениями столбец P и строку с номером 33. В ячейке P32 будет следующая формула: =P33+P15, её растягиваем вверх. А в ячейке O33 такая: =P33+O16, её будем растягивать влево.
Для «внутренних» ячеек, в целом, формула не поменяется, только растягивать будем влево-вверх. Записываем в ячейке O32 формулу: =МАКС(O33;P32)+O15 и растягиваем.
С помощью инструмента «Формат по образцу» переносим границы ячеек с исходной таблицы.
Здесь у нас только одна конечная точка: ячейка А18 в правом верхнем углу таблицы. В ней и будет искомое значение.
Поправим формулы справа и сверху от стен. Обратите внимание, что для строки мы начинаем править формулу в ячейке M26 и растягиваем её влево. Для столбца правим формулу в C29 и растягиваем вверх.
Получаем, что максимальное количество монет, которое может собрать робот в этой задаче — 2130. Теперь найдём минимальное. Для этого заменяем слово «МАКС» на «МИН» при помощи инструмента «Заменить» (Ctrl+H).
В итоге получаем второй ответ: 1049.
