Зачем это в ЕГЭ.
Задание 18 в ЕГЭ по информатике проверяет умение анализировать и обрабатывать данные, представленные в виде графов или таблиц, для нахождения максимального пути или сбора максимального количества монет. Оно даёт 1 первичный балл и встречается в каждом варианте ФИПИ, часто в комбинации с динамическим программированием.
Главная идея.
Задача сводится к поиску оптимального пути в графе или таблице, где каждое ребро или клетка имеет «вес» (например, количество монет). Ключ — использование динамического программирования для последовательного накопления максимальных значений, избегая полного перебора.
Алгоритм (чеклист).
1. Определить структуру данных (таблица, граф) и начальную точку.
2. Заполнить начальные значения (например, первую строку/столбец таблицы).
3. Для каждой следующей клетки/узла вычислить максимальное значение, суммируя текущий «вес» с максимумом из возможных предыдущих шагов.
4. Проверить все возможные направления движения (вправо, вниз, по диагонали и т.д.).
5. Зафиксировать максимальное значение в конечной точке.
6. Восстановить путь, если требуется (обратным проходом).
Опоры (кратко).
- Формула для динамического программирования:
Пример 1 (таблица с монетами)
Дана таблица 3×3 с монетами в клетках:
2 5 1
3 4 7
8 2 6
Шаг 1. Заполняем первую строку: dp[0][0] = 2, dp[0][1] = 2 + 5 = 7, dp[0][2] = 7 + 1 = 8.
Шаг 2. Заполняем первый столбец: dp[1][0] = 2 + 3 = 5, dp[2][0] = 5 + 8 = 13.
Шаг 3. Для dp[1][1] выбираем max(7, 5) + 4 = 11.
Шаг 4. Аналогично: dp[1][2] = max(8, 11) + 7 = 18, dp[2][1] = max(11, 13) + 2 = 15.
Шаг 5. Конечная точка: dp[2][2] = max(18, 15) + 6 = 24.
Ответ: 24.
Пример 2 (граф с ограничениями)
Дана сетка 2×3, движение только вправо или вниз. Монеты:
1 0 2
4 3 1
Шаг 1. Первая строка: dp[0][0] = 1, dp[0][1] = 1, dp[0][2] = 3.
Шаг 2. Первый столбец: dp[1][0] = 1 + 4 = 5.
Шаг 3. dp[1][1] = max(1, 5) + 3 = 8.
Шаг 4. dp[1][2] = max(3, 8) + 1 = 9.
Ответ: 9.
Типичные ошибки.
1. Неправильные начальные условия — забывают инициализировать dp[0][0].
2. Игнорирование направлений — не учитывают все возможные ходы (например, диагонали).
3. Переполнение индексов — выход за границы таблицы при расчётах.
4. Невосстановление пути — если требуется, теряют обратный проход.
5. Путаница с максимумом/минимумом — решают на минимум вместо максимума.
Дальше.
Разберите задачи с препятствиями в таблице или графы с циклами.