Базовый (1 балл)
Время: 3-5 мин
Excel / Calc
Формулы МАКС/МИН
Динамика
Все задачи №{ topic_num } в каталоге
Задание №18. Динамическое программирование в таблицах (Робот-сборщик)
Тема: Сбор монет на прямоугольном поле, стены и угловые клетки
Робот перемещается из левой верхней клетки (A1) в правую нижнюю клетку поля NxN, двигаясь только ВПРАВО и ВНИЗ. Требуется найти максимальную и минимальную денежную сумму, которую соберет Робот.
1. Алгоритм решения в Excel за 2 минуты:
- Скопируйте исходную таблицу $N \times N$ и вставьте её правее/ниже. Очистите числа внутри копии, оставив границы и стены.
- В стартовую клетку копии напишите
=A1. - Верхняя строка: Робот может прийти в неё ТОЛЬКО слева -> пишем
=предыдущая_слева + исходная_ячейкаи протягиваем вправо. - Левый столбец: Робот может прийти ТОЛЬКО сверху -> пишем
=предыдущая_сверху + исходная_ячейкаи протягиваем вниз. - Внутренние клетки: Робот выбирает лучший путь -> пишем
=МАКС(слева; сверху) + исходная_ячейкаи растягиваем на всю таблицу. - Для поиска минимума замените функцию
МАКСнаМИНчерезCtrl + H.
Разновидности и прототипы задания на экзамене
Тип 1: Классическое поле без стен
Динамика вида `=A1 + МАКС(предок_сверху; предок_слева)`.
Тип 2: Поле с внутренними стенами
Сквозь стены Робот проходить не может — ячейки вдоль стен заполняются с учетом ограничений.
Анти-примеры (Типичные ошибки vs Как делать правильно)
Как делать НЕ надо:
Ошибка: Забыть восстановить формулы вдоль внутренних стен
Если сверху ячейки стоит стена, брать значение сверху нельзя!Как делать ПРАВИЛЬНО:
Правильно: Под стеной брать строго ячейку слева, справа от стены — строго ячейку сверху.
ГРОБ
ГРОБ №18: Робот может двигаться в 3 направлениях (вправо, вниз и по диагонали)
Добавлена диагональная команда.
Как обойти ловушку: В формулу МАКС добавьте третьего предка: `=МАКС(слева; сверху; по_диагонали_слева_сверху) + исходная`.
Лайфхаки и подводные камни на экзамене:
- Используйте быстрый автопоиск и замену `Ctrl + H`: замените `МАКС` на `МИН` — мгновенно получите вторую часть ответа!