Квадрат разлинован на n × n клеток. Исполнитель Робот перемещается по клеткам, выполняя за одно перемещение одну из двух команд: «вправо» или «вниз». Команда «вправо» перемещает робота в соседнюю правую клетку, команда «вниз» — в соседнюю нижнюю. При выходе за границу квадрата робот разрушается.
Перед каждым запуском в каждую клетку кладут монету достоинством от 1 до 100. Посетив клетку, робот забирает монету. Это относится к начальной и конечной клеткам.
Необходимо определить максимальную и минимальную сумму, которую может собрать робот, пройдя из левой верхней клетки в правую нижнюю. В ответе указать два числа: сначала максимальную сумму, затем минимальную.
Исходные данные — электронная таблица размером n × n, где каждая ячейка соответствует клетке квадрата. Пример — таблица 10 × 10, но размеры могут быть другими (например, 15 × 5). Задача — поиск наиболее выгодного пути для робота, перемещающегося только вправо или вниз, от левой верхней клетки к правой нижней.
Решение в Excel
Решение задачи удобно реализовать в Excel. Создадим вспомогательную таблицу под исходной.
- Инициализация: В первую ячейку вспомогательной таблицы запишем значение из левой верхней ячейки исходной. Например, если значение в исходной таблице равно 51, то в первую ячейку вспомогательной таблицы запишем =51.
- Движение вправо: В следующей ячейке вспомогательной таблицы (справа от первой) рассчитаем сумму при движении только вправо: =51 + B1 (где B1 – значение из второй ячейки первого ряда исходной таблицы). Формулу копируем вправо на всю ширину таблицы.
- Движение вниз: Под первой ячейкой вспомогательной таблицы рассчитаем сумму при движении только вниз: =13 + A2 (где A2 – значение из второй ячейки первого столбца исходной таблицы). Формулу копируем вниз на всю высоту таблицы.
- Максимальный путь: В ячейки вспомогательной таблицы между путями «только вправо» и «только вниз» впишем формулу, находящую максимальное значение из двух возможных путей: =B2 + MAX(C2; B3) (где B2 — значение текущей ячейки в исходной таблице, C2 — значение ячейки справа в вспомогательной таблице, B3 — значение ячейки снизу в вспомогательной таблице). Формулу копируем на всю вспомогательную таблицу.
- Определение максимальной суммы: В правом нижнем углу вспомогательной таблицы будет максимальное количество монет, которое может собрать робот.
- Минимальный путь: Для нахождения минимальной суммы повторяем шаги 1-5, заменив функцию MAX на MIN. В правом нижнем углу вспомогательной таблицы будет минимальное количество монет.
Ответ
Результат расчётов — два числа: максимальная и минимальная сумма монет, которые может собрать робот. Например, 1204 502. Это и будет ответом на задание 18.