Задание №18 на ЕГЭ по информатике. Робот — сборщик монет

Задание 18 ЕГЭ по информатике. Робот – сборщик монет

В задании 18 дан некий алгоритм для робота – сборщика монет. Поле, по которому перемещается робот, задано в виде электронной таблицы. Необходимо обработать данные в этой таблице, т.е. каким-то образом их преобразовать, чтобы ответить на вопрос задачи.

Пример задания 18.
Квадрат разлинован на N×N клеток (1<N<17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков – сначала максимальную сумму, затем минимальную.

Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.

Решение:

Итак, исполнитель Робот шагает по клеточкам и собирает монетки. Очень похоже на компьютерную игру. Цель игры – собрать как можно больше монеток. Как же это сделать? Давайте представим, что вместо Робота шагает Буратино по Полю Чудес, на котором вырыты ямки, а в них лежат монетки, и Буратино хочет собрать как можно больше монеток, чтобы купить себе учебники для школы. Но левая нога у Буратино не двигается, поэтому он может шагать только правой ногой (вниз по полю), и назад правая нога тоже не двигается, поэтому ею он может шагать только вперед (вправо по полю). Какую же стратегию выбрать Буратино, чтобы собрать как можно больше монеток?

Что если Буратино жадный, то как он будет перемещаться? Он будет выбирать всякий раз ямку, где монетка больше, т.е. двигаться по пути №1. Из первойямки в левом верхнем углу Буратино возьмет монетку «1», увидит, что в ямке внизу лежит монетка «10», а в ямке справа – монетка «8». Он где-то слышал, что 10 больше 8, поэтому пойдет вниз и возьмет монетку «10». Далее в обоих ямках снизу и справа по одинаковой монетке «1». Буратино расстроится, что нельзя забрать монетку побольше, закроет глаза и наугад шагнет, допустим вниз. Затем перед ним монетки «2» и «3», он выбирает «3», потому что тоже где-то слышал, что 3 больше 2, и т.д. В итоге «жадный» Буратино соберет 1+10+1+3+12+5+6+8+2=48 монеток. Хорошо, но на все учебники не хватит. Буратино очень переживает, а не мог бы он собрать больше монеток? Кстати, Буратино так и называет свой путь «жадным».

У жадного Буратино есть брат-близнец, случайный Буратино, который выбирает ямки случайным образом, т.е. наугад. Тогда его путь может оказаться, например, путем №2, и его «урожай» составит 1+8+8+4+3+2+6+8+2=42 монетки. Еще меньше. Пока побеждает жадный Буратино.

Что общего в рассуждениях жадного и случайного Буратино? То, что они решают, КУДА им пойти из текущей ячейки.

Ну, конечно же, по правилам хорошей сказки, у них есть третий брат-близнец, умный Буратино, который будет рассуждать по-другому. Он будет анализировать, ОТКУДА ему лучше прийти в такую-тоямку. Он просчитает все возможные пути и выберет тот, по которому он соберет максимальное количество монеток. Он составит план местности и каждой ямкеприпишет число (метку), которое будет означать, какое максимальное количество монеток он сможет собрать на пути из левого верхнего угла до этой ямки. Как Буратино посчитает метку, например, ямки «12»? Он посмотрит на метку верхней и левой ямок, выберет максимальную из них и прибавит к ней количество монеток «12». Ведь, если Буратино собрал максимально возможное количество монеток до ямки «12», то и вместе с монетками из этой ямки он тоже получит максимально возможное количество монеток на данном шаге.И так до нижней правой ямки. Вручную Буратино будет это делать долго. Мы же можем посчитать метки ячеек быстро с помощью электронной таблицы.

Предварительно добавим в таблицу пустую строку сверху и пустой столбец слева. Это необходимо для того, чтобы формулы во всех ячейках были одинаковыми, в том числе в ячейках верхней строки 2 и левого столбца В. Функция МАКС просто игнорирует пустую ячейку.

Совет №1: Если сомневаетесь или не знаете, как работает какая-то функция в какой-то нестандартной ситуации, разберите эту ситуацию отдельно (можно даже на отдельном листе электронной таблицы)с минимальным количеством ячеек и с простыми значениями в этих ячейках. И только потом применяйте в большой и сложной таблице.

Совет №2: Пользуйтесь автозаполнением формул. После этого обязательно проверяйте правильность заполнения: не «съехали» ли адреса ячеек. Это удобно делать в строке формул: все используемые ячейки подсвечиваются разными цветами.

Слева исходная таблица (Поле Чудес), справа план местности умного Буратино с метками ячеек. Метка ячейки L6 равна максимальному количеству монеток, которые Буратино сможет собрать, двигаясь из верхнего левого угла к нижнему правому, и равна 51.

Для того, чтобы посчитать минимальное количество монеток, нужно во всех формулах функцию МАКС заменить на МИН (Панель инструментов ->Главная ->Найти и выделить ->Заменить). Это уже путь №4 скромного брата-близнеца Буратино. Меньше, чем 23 монетки, он не сможет собрать.

Ответ: 5123

Совет №3: Внимательно читайте условие задачи (направление движения, количество клеточек при движении, стены, тупики и т.д.). Внимательно читайте, в каком виде нужно записать ответ (сначала максимальное число, а потом минимальное, или наоборот, с пробелом или без, или только максимальное и т.д.).

Еще пример задания 18.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщенными линиями.

Решение:

В этой задаче на поле появились стены, о которые Робот может разбиться. Через горизонтальные стены Робот не может проходить сверху вниз, а через вертикальные стены – не может проходить слева направо. Соответственно, в желтых ячейках (под горизонтальной стеной) необходимо убрать ссылки на верхние ячейки, а в зеленых ячейках (справа от вертикальной стены) – убрать ссылки на левые ячейки. Максимальная сумма равна 48.

Аналогично, чтобы найти минимальную сумму, заменим во всех формулах функцию МАКС на МИН. Минимальная сумма равна 25.
Ответ: 4825.