Динамическое программирование: Робот-сборщик монет
Задание 18 · Билет 1 · ЕГЭ по информатике
Условие
Задание выполняется с использованием прилагаемого файла. Поле разлиновано на N×N клеток. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. Поле ограничено внешними стенами; между соседними клетками также могут стоять внутренние стены — сквозь стену Робот пройти не может. Перед запуском в каждой клетке лежит монета достоинством от 1 до 100; посетив клетку, Робот забирает монету (это касается и начальной, и конечной клеток).
В клетках, справа и снизу ограниченных стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько. Определите максимальную и минимальную денежные суммы среди всех итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную.
| 1 | 8 | 8 | 4 |
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
На рисунке — пример входных данных (4×4). Толстыми линиями обозначены стены; в файле поле другого размера.
Разбор задачи
Задание 18 ЕГЭ по информатике — работа с электронной таблицей на клетчатом поле: исполнитель Робот идёт из левой верхней клетки только вправо и вниз, собирая монеты и обходя стены.
Нужно найти максимальную и минимальную итоговые суммы. Решают накоплением: для каждой клетки считают сумму по уже посчитанным соседям, а затем выбирают лучшую и худшую среди конечных клеток.
Что важно знать
- Задание базового уровня — оценивается в 1 балл
- Робот ходит только вправо и вниз; сквозь стены пройти нельзя
- Конечная клетка — та, справа и снизу от которой стена; таких клеток может быть несколько
Потренируйся на поле со стенами: найди максимальную и минимальную суммы накопленных монет — от разминки до формата экзамена.
Решение
Теория с нуля: что нужно знать
Зачем этот блок. Показать, как накапливаются суммы: алгоритм по очереди вычисляет значение каждой клетки, опираясь на уже посчитанных соседей.
Динамическое программирование — это способ решать задачу по частям: значение для каждой клетки считаем один раз и запоминаем, а для новой клетки берём уже посчитанных соседей. Здесь так можно, потому что прийти в клетку можно только сверху или слева. Значит, сумму считают одним проходом по полю слева-направо и сверху-вниз:Нажимайте «Вперёд» — клетки заполняются по порядку. Подсвечены текущая клетка и два соседа, откуда можно прийти; соседа за стеной не используем.
Поле: монеты и стены
| A | B | C | D | |
|---|---|---|---|---|
| 1 | 1 | 8 | 8 | 4 |
| 2 | 10 | 1 | 1 | 3 |
| 3 | 1 | 3 | 12 | 2 |
| 4 | 2 | 3 | 5 | 6 |
Минимум до клетки
| A | B | C | D | |
|---|---|---|---|---|
| 1 | 1 | |||
| 2 | ||||
| 3 | ||||
| 4 |
Максимум до клетки
| A | B | C | D | |
|---|---|---|---|---|
| 1 | 1 | |||
| 2 | ||||
| 3 | ||||
| 4 |
A1 — старт. Робот начинает здесь, поэтому накопленная сумма равна монете 1 и для максимума, и для минимума.
Зачем этот блок. Показать, как эти же вычисления записываются формулами в LibreOffice и работают при копировании: одна формула на все клетки, а у стен её правят вручную.
В электронной таблице те же суммы считают формулами. Рядом с монетами заводят таблицу сумм, и формула ссылается на монету той же строки и на суммы соседей — =монета + МАКС(сверху; слева) для максимума, с МИН — для минимума. В формулу вписывают только ссылки на клетки, поэтому значения подставляются сами. Если сосед за стеной, ссылку на него не ставят. Посмотрите, как формула меняется по клеткам:Слева — монеты (A–D), через пустой столбец E — таблица сумм (F–I). Ниже — формула текущей клетки и её опорные ячейки.
Достаточно одной формулы. В каждую клетку таблицы сумм копируют одну и ту же формулу: монета + МАКС(сумма сверху; сумма слева) (для минимума — МИН). При копировании ссылки смещаются сами, поэтому каждая клетка смотрит на свою монету и своих соседей. Протяните формулу маркером автозаполнения или выделите диапазон и нажмите Ctrl+D — вручную правят только клетки у стен.
Стены формула «не видит». В таблице стена — это оформление ячейки, а не данные, поэтому в формуле её нет: протянутая формула везде одинакова и смотрит на обоих соседей. Но если сосед закрыт стеной, пройти из него нельзя — значит, его убирают из формулы вручную. Формулы в таких клетках отличаются от остальных; ниже они подсвечены, разберитесь с ними отдельно. На остальных клетках менять ничего не нужно.
| A | B | C | D | F | G | H | I | ||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 8 | 8 | 4 | 1 | ||||
| 2 | 10 | 1 | 1 | 3 | |||||
| 3 | 1 | 3 | 12 | 2 | |||||
| 4 | 2 | 3 | 5 | 6 |
монета этой клетки сумма сверху сумма слева за стеной — в формулу не входит у стены: формулу правят вручную
F1 — старт: сумма равна монете A1 = 1.
Решение
шагов: 8 из 8Откройте файл в LibreOffice Calc
Скачайте таблицу task18-1-robot.ods и откройте её двойным щелчком — формат .ods открывается в LibreOffice без предупреждений. Поле — это N×N клеток с числами-монетами. Толстые линии между клетками — внутренние стены, внешняя рамка поля — тоже стена.
Заведите таблицу накопленных сумм
Рядом с полем (или на новом листе) сделайте такую же пустую таблицу N×N — в неё будем писать суммы. В левой верхней клетке сумма равна её монете: маршрут всегда начинается здесь. Остальные клетки заполним формулами.
Формула для максимума
Рядом с монетами заведите таблицу сумм (через пустой столбец или на новом листе). Формула клетки сумм ссылается на монету той же строки и берёт наибольшую из сумм соседей сверху и слева. Например, монеты — A1:D4, суммы — F1:I4; тогда формула клетки F2 — =A2+МАКС(F1), а клетки G2 — =B2+МАКС(G1;F2). Числа в формулу не вписывают — только ссылки, значения подставляются сами.
Учитывайте стены вручную
Формула стену не видит: стена — это оформление ячейки, а не данные, поэтому после протяжки формула везде одинаковая и смотрит на обоих соседей. Но из клетки за стеной прийти нельзя, значит, в клетках рядом со стеной формулу правят вручную — убирают ссылку на закрытого соседа. Например, если слева стена, вместо =B2+МАКС(G1;F2) пишут =B2+МАКС(G1). Такие клетки удобно сразу пометить цветом, чтобы не потерять; у клеток на верхней и левой границе сосед тоже только один.
Заполните суммы по клеткам
Идите по клеткам слева-направо и сверху-вниз: когда дошли до клетки, суммы сверху и слева уже посчитаны. Поставьте формулу в первую клетку и протяните её маркером автозаполнения (маленький крестик в правом нижнем углу выделенной ячейки) или выделите диапазон и нажмите Ctrl+D. Клетки со стенами поправьте вручную — убрав лишнюю ссылку.
Повторите для минимума
Сделайте ещё одну таблицу — для минимума. Формулы в ней такие же, только вместо МАКС берут МИН. Заполните её по тому же правилу, с учётом стен.
Найдите конечные клетки и ответ
Конечная клетка — та, у которой и справа, и снизу стена (внешняя граница поля тоже стена). Таких клеток может быть несколько. Соберите их итоговые суммы: наибольшая по таблице максимумов — это максимум, наименьшая по таблице минимумов — минимум. Удобно выделить конечные клетки цветом (Главная → условное форматирование) и посмотреть =МАКС(...) и =МИН(...) по ним.
Проверьте ответ
Ответ для этого билета — 772 193 (сначала максимум, затем минимум). Проверьте себя: пересчитайте вручную две-три клетки в середине поля — они должны совпасть с формулами.
Проверка
Типовые ошибки и проверка
- Пускают маршрут сквозь стену или берут в формулу соседа за стеной.
- Останавливаются только в правом нижнем углу, хотя конечных клеток может быть несколько.
- Берут не всех доступных соседей: формула должна смотреть и верхнюю, и левую клетку (если они не закрыты стеной).
- Путают таблицы максимума и минимума или берут max там, где нужен min.
- Складывают монеты по «жадному» пути (всегда вниз или всегда вправо): так находят лишь один маршрут, а нужен лучший из всех.
- Проверка: на маленьком поле сверьте две-три клетки таблицы сумм вручную и убедитесь, что сходится.
Режимы
Сейчас открыт режим обучения: теория, разбор и ответ видны. Скоро появится режим проверки — только условие и поле ответа, без подсказок.
Практикум Все задания Режим проверки — скоро