Разборы · ОГЭ, задание 4
Задание 4 ОГЭ по информатике: кратчайший путь по таблице
В задании 4 дана таблица длин дорог между пунктами. Нужно найти длину кратчайшего пути между двумя пунктами. 1 балл.
Как решать
- Нарисуйте схему: пункты — точки, дороги — линии с длинами. Таблица симметрична, каждую дорогу рисуйте один раз.
- Двигайтесь от начального пункта и пишите у каждого пункта длину кратчайшего известного пути до него. Если нашёлся путь короче — исправляйте.
- Прямая дорога не всегда самая короткая: путь через два-три пункта часто выгоднее.
Пример
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 6 | 1 | ||||
| B | 6 | 5 | 5 | 6 | ||
| C | 5 | 3 | ||||
| D | 5 | 7 | 6 | |||
| E | 1 | 6 | 3 | 7 | ||
| F | 6 |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение.
Удобно нарисовать схему дорог и двигаться от начального пункта, записывая у каждого пункта длину кратчайшего известного пути до него.
Кратчайший путь: A–E–D–F, его длина 1 + 7 + 6 = 14.
Типичные ошибки
- Берут прямую дорогу, не проверив обходные пути.
- Пропускают дорогу из таблицы при рисовании схемы — сверяйте число линий с числом заполненных клеток (делённым на 2).
Вид задания: путь через пункт
Дерево путей строится как обычно: из начального пункта — все дороги, кроме тех, что ведут туда, где уже были. Но в ответ берутся только ветки, в которых встретился нужный пункт. Если сложили два куска пути, выпишите маршрут целиком и проверьте, нет ли повторов пунктов.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 2 | 4 | 3 | |||
| B | 2 | 1 | 3 | |||
| C | 1 | 1 | ||||
| D | 4 | 3 | 4 | |||
| E | 3 | 1 | 9 | |||
| F | 4 | 9 |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Решение.
Строим дерево путей из A: из каждого пункта — все дороги, кроме тех, что ведут туда, где уже были. Дерево строится как обычно, но в ответ берём только ветки, в которых встретился пункт C.
Пути через C (от коротких к длинным):
A–E–C–B–D–F: 3 + 1 + 1 + 3 + 4 = 12
A–B–C–E–F: 2 + 1 + 1 + 9 = 13
A–D–B–C–E–F: 4 + 3 + 1 + 1 + 9 = 18
Без условия ответ был бы 8 по пути A–D–F, но он не заходит в C.
Сложить два кратчайших куска (A–C и C–F) нельзя: получилось бы 11, но такой маршрут дважды проходит один и тот же пункт. Выпишите путь целиком и проверьте повторы.
Ответ: 12.
Потренироваться: задание 4 новые варианты с проверкой ответа