Задание 18
Пример
Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100.
Посетив клетку, Робот забирает монету с собой только в том случае, если её номинал – число, кратное 3; если номинал монеты – число, не кратное 3, то Робот не берёт монету; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные для Робота записаны в файле 18-0.xls в виде электронной таблицы прямоугольной формы.
Функция
ОСТАТ(число; делитель)
имеет два аргумента и возвращает остаток от деления значения параметра число на значение параметра делитель, который можно сравнить с 0 для определения кратности числа делителю.
Функция
ЕСЛИ(условие; значение_если_да; значение_если_нет)
имеет три аргумента: первый - это условие, второй - возвращаемое значение, если условие выполнено, третий - значение, если не выполнено
откроем файл с электронной таблицей размером 10 на 10:
Робот начинает движение из верхнего левого угла (из ячейки А1) и перемещается в правый
нижний (то есть в J10)
при использования метода динамического программирования требуется выделить для вычислений дополнительную таблицу такого же размера; проще всего сделать так:
- скопировать исходную таблицу вниз
- обвести её рамкой (и/или выделить фоном), чтобы запомнить исходный размер;
- стереть все данные в копии. вот что должно получиться:
дальше мы будем работать только с областью, выделенной жёлтым фоном
предположим, что робот уже находится в правом нижнем углу; в этом случае он может получить
только сумму в этой ячейке, то есть величину J10, НО при условии, что она кратна 3;
записываем в J22 формулу
= ЕСЛИ(ОСТАТ(J10; 3) = 0; J10; 0)
Третий аргумент функции ЕСЛИ() можно вообще не указывать. Тогда при ложном
условии поле останется пустым и при вычислениях будет эквивалентно 0.
После ввода формулы видим в ячейке J22 значение 33, как и ожидалось:
рассмотрим нижний ряд: если Робот находится в одной из ячеек последней строки 10, то
он может идти только вправо, собирая монеты в последней строке; например, начав движение
из ячейки I10 он соберёт монету в этой ячейке, если её номинал кратен 3 и во всех (в данном
случае – в одной) следующих (опять же только если номинал монет кратен 3), то есть формула
в ячейке I22 должна быть
= ЕСЛИ( ОСТАТ( I10;3 ) = 0 ; I10 ; 0 ) + J22
В отличие от ячейки J10 значение
в ячейке I10 не кратно 3, поэтому наблюдаем, что сумма осталась прежней (33) (то есть, если
бы Робот стартовал из ячейки I10, то он набрал бы только 33, так как 40 не делится на 3):
эту формулу копируем (протаскиваем за маркер заполнения) по всей строке 22:
аналогично если Робот находится в последнем столбце, он может двигаться только вниз, собирая по пути все монеты, номинал которых кратен 3; вводим в ячейку J21 формулу
= ЕСЛИ(ОСТАТ(J9; 3) = 0; J9; 0) + J22
и протаскиваем (копируем) её вверх на весь стол-бец J вспомогательной таблицы:
Займёмся центральными ячейками жёлтой таблицы, которые пока не заполнены; пусть
Робот находится в ячейке I9; тогда для того, чтобы получить максимальную сумму, ему
нужно выбрать лучший из двух путей – пойти в I10 или в J9; из второй таблицы видим,
что значения в этих ячейках одинаковы, но, тем не менее, формулу напишем таким образом,
чтобы она правильно работала и для разных значений, ведь мы распространим её на всю
оставшуюся часть таблицы с помощью маркера автозаполнения. В формуле нужно выбрать
максимум из значений ячеек I10 и J9, получаем
= ЕСЛИ(ОСТАТ(I9; 3)= 0; I9; 0) + МАКС(I22; J21)
Оба аргумента функции МАКС находятся в рабочей таблице
для всех оставшихся ячеек принцип вычисления максимальной суммы тот же самый: нужно
добавить к значению этой ячейки в исходной таблице максимум из накопленных сумм,
которые Робот собирает в случае двух возможных шагов; копируем формулу из I21 на
весь диапазон A13:I21 (сначала можно растянуть формулу на диапазон-столбец I13:I21,
а затем этот диапазон – на нужный диапазон A13:I21)
Первый ответ к задаче – это максимальная сумма, накопленная при движении из левого
верхнего угла; она записана в левом верхнем углу рабочей таблицы, то есть в ячейке A13
(она выделена зелёным фоном):
чтобы найти наименьшую возможную сумму, нужно в формуле в п. 9 заменить функцию МАКС
на МИН:
= ЕСЛИ(ОСТАТ(I9; 3) = 0; I9; 0) + МИН(I22; J21)
Ответ: 684 105.
При данном условии задачи все равно, в каком направлении двигаться: мы получим тот же результат, если будем рассматривать обратное движение – влево и вверх из правого нижнего угла. Поэтому задачу можно решать, начиная с левого верхнего угла таблицы, при этом ответ получается в правом нижнем углу рабочей области.