Теория:
Характеристика задания
1. Тип ответа: числовой.
2. Структура содержания задания: дана текстовая задача и данные в виде файла, нужно с помощью динамического программирования найти ответы на вопросы.
3. Уровень сложности: повышенный.
4. Примерное время выполнения: \(8\) минут.
5. Количество баллов: \(1\).
6. Требуется специальное программное обеспечение: да.
7. Задание проверяет умение использовать электронные таблицы для обработки целочисленных данных.
Данное задание решается с помощью электронных таблиц.
Демоверсия
Квадрат разлинован на \(N × N\) клеток (\(1 < N < 30\)). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю.
Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от \(1\) до \(100\). Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
Определи максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.
В ответе укажи два числа — сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером \(N × N\), каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных
Файл для скачивания: 18.ods.
Алгоритм решения задания
1. Открыть файл с данными.
2. Скопировать таблицу с данными ниже.
3. Удалить данные в нижней таблице, оставив только границы.
Рис. \(1\). Таблица для вычислений
4. Данные в первой ячейке переписываются из верхней в нижнюю с помощью формулы: \(=A1\).
Рис. \(2\). Первое значение
5. Робот двигается либо вправо, либо вниз и на своём пути собирает монеты.
В ячейку \(B22\) запишем формулу \(=A22+B1\) и скопируем формулу в ячейки справа — до границы.
Рис. \(3\). Формула и значения скопированные
То же самое сделаем со столбцом \(A\).
Формула \(=A22+A2\).
Рис. \(4\). Формула и скопированные данные
6. По условию задания в ячейке \(B23\) Робот укажет максимальное из сверху или слева стоящих значений плюс значение в ячейке \(B2\), поэтому формула будет такая: \(=B2+МАКС(B22;A23)\).
Рис. \(5\). Формула с максимальным значением
7. Скопируем полученную формулу до нижнего правого угла (условие задачи).
Рис. \(6\). Полученная таблица
8. Как видно, границы исчезли, применим условное форматирование. Для этого выделим первую таблицу с данными, затем не просто вставим, а только вернём форматирование:
- выделить таблицу с данными, Копировать;
- выделить нижнюю таблицу;
- Вставить как..., выбрать только Формат, как на рисунке ниже.
Рис. \(7\). Вставка форматирования
9. По условию задания Робот сквозь стены проходить не может, поэтому нужно пересчитать значения в некоторых диапазонах.
Диапазон \(C23:C29\) нужно пересчитать, формула должна быть в ячейке \(C23\) такой: \(=C22+C2\), так как сквозь стену Робот идти не может, скопируем формулу до ячейки \(C29\).
Сделаем то же самое с диапазонами: \(E26:E34\), \(G31:G39\), \(J23:J30\), \(M27:M35\), \(P30:P39\).
10. Проведём те же операции с диапазонами \(D24:H24\) и \(I39:N39\).
В \(D24\) запишем формулу \(=C24+D3\) и скопируем её до \(H24\).
Рис. \(9\). Вычисление значений ниже горизонтальной стены
Рис. \(10\). Вычисление значений правее вертикальной стены
В нижнем правом углу таблицы получилось максимальное значение 1099.
Это ответ на первый вопрос.
11. Теперь найдём минимальное значение, но не будем переписывать формулы — просто заменим формулу МАКС на МИН.
Выполним команду Найти и заменить, а дальше заменим все МАКС на МИН.
Рис. \(11\). Замена МАКС на МИН
Получили минимальное значение 1026.
Ответ:
1099 | 1026 |
Источники:
Рис. 1. Таблица для вычислений. © ЯКласс.
Рис. 2. Первое значение. © ЯКласс.
Рис. 3. Формула и значения скопированные. © ЯКласс.
Рис. 4. Формула и скопированные данные. © ЯКласс.
Рис. 5. Формула с максимальным значением. © ЯКласс.
Рис. 6. Полученная таблица. © ЯКласс.
Рис. 7. Вставка форматирования. © ЯКласс.
Рис. 8. Вычисление значений вдоль стены. © ЯКласс.
Рис. 9. Вычисление значений ниже первой стены. © ЯКласс.
Рис. 10. Вычисление значений ниже второй стены. © ЯКласс.
Рис. 11. Замена МАКС на МИН. © ЯКласс.
Рис. 2. Первое значение. © ЯКласс.
Рис. 3. Формула и значения скопированные. © ЯКласс.
Рис. 4. Формула и скопированные данные. © ЯКласс.
Рис. 5. Формула с максимальным значением. © ЯКласс.
Рис. 6. Полученная таблица. © ЯКласс.
Рис. 7. Вставка форматирования. © ЯКласс.
Рис. 8. Вычисление значений вдоль стены. © ЯКласс.
Рис. 9. Вычисление значений ниже первой стены. © ЯКласс.
Рис. 10. Вычисление значений ниже второй стены. © ЯКласс.
Рис. 11. Замена МАКС на МИН. © ЯКласс.