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