Задание 18: робот-сборщик и динамика в таблице
Коротко
Робот идёт из левого верхнего угла в правый нижний, двигаясь только вправо или вниз, и собирает числа из клеток. Максимальную (минимальную) сумму находят динамикой: в каждой клетке записывают её значение плюс максимум (минимум) из соседей сверху и слева. Первая строка и первый столбец считаются накопительно. Стены учитывают, запрещая соответствующие переходы.
Формула
S[i][j] = A[i][j] + max(S[i − 1][j], S[i][j − 1]).
В электронной таблице: =A1+МАКС(верхняя; левая) и протянуть.
Пример
| 1 | 3 | 1 |
|---|---|---|
| 1 | 5 | 1 |
| 4 | 2 | 1 |
Минимальная сумма: 1 → 3 → 1 → 1 → 1 = 7.
Стены
Если между клетками стена, при подсчёте клетки соседа за стеной не берите.
Типичные ошибки
- Первая строка считается с МАКС от пустых клеток.
- Не учитывают стены.
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 18
Пример 1 из 2
Поле 3 × 3 (по строкам): 1 3 1 / 1 5 1 / 4 2 1. Минимальная сумма пути вправо/вниз?
- Разбор
- Динамика по таблице даёт 7 (путь 1, 3, 1, 1, 1).
- Ответ
- 7
Пример 2 из 2
Как считается клетка первой строки?
- Разбор
- Пришли можно только слева.
- Ответ
- Значение + сумма левой клетки
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Какие ходы разрешены роботу обычно?
Показать ответ
Ответ: Вправо и вниз.
Поэтому динамика по соседям сверху и слева.
- Вопрос 2 из 5
Формула для максимума?
Показать ответ
Ответ: A + max(сверху, слева).
Накопление.
- Вопрос 3 из 5
Как учитывать стену?
Показать ответ
Ответ: Не брать соседа за стеной.
Вручную правим формулу.
- Вопрос 4 из 5
Где ответ?
Показать ответ
Ответ: В правой нижней клетке.
Финиш.
- Вопрос 5 из 5
Нужно ли перебирать все пути?
Показать ответ
Ответ: Нет.
Динамика быстрее.
Проверьте всё задание 18, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти