ОГЭ, задание 4
Четвёртое задание экзамена. Дана таблица дорог между пунктами — и надо найти длину самого короткого пути из одного пункта в другой.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 2 | 3 | 16 | |||
| B | 2 | 5 | ||||
| C | 3 | 3 | ||||
| D | 5 | 3 | 2 | 7 | ||
| E | 2 | 3 | ||||
| F | 16 | 7 | 3 |
Найдите длину кратчайшего пути из пункта A в пункт F. Ехать можно только по дорогам из таблицы. В каждом пункте разрешено побывать не больше одного раза.
1 балл, три-четыре минуты. Формул тут нет — нужны порядок и аккуратное сложение. Балл теряют на спешке: «и так видно, какой путь короче». Не видно.
с чего начать
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 2 | 3 | 16 | |||
| B | 2 | 5 | ||||
| C | 3 | 3 | ||||
| D | 5 | 3 | 2 | 7 | ||
| E | 2 | 3 | ||||
| F | 16 | 7 | 3 |
Число на пересечении строки и столбца — длина дороги между этими пунктами.
Пустая клетка — дороги нет. Из B в C проехать напрямую нельзя.
Таблица симметрична: A–B и B–A — одна и та же дорога, поэтому каждое число стоит дважды. Читать достаточно половину выше закрашенных клеток.
Первое действие — выписать дороги списком: A–B 2, A–C 3, A–F 16, B–D 5, C–D 3, D–E 2, D–F 7, E–F 3. Восемь дорог — восемь чисел в половине таблицы: сошлось, ничего не потеряли.
чтобы увидеть
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 2 | 3 | 16 | |||
| B | 2 | 5 | ||||
| C | 3 | 3 | ||||
| D | 5 | 3 | 2 | 7 | ||
| E | 2 | 3 | ||||
| F | 16 | 7 | 3 |
дороги спискомA–B 2A–C 3A–F 16B–D 5C–D 3D–E 2D–F 7E–F 3
Каждое число таблицы — одна линия на рисунке, все восемь. Сразу видно: все пути сходятся в D, а прямая дорога A–F (16) — длинная. Длины не в масштабе, важны соединения и числа.
главный приём
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 2 | 3 | 16 | |||
| B | 2 | 5 | ||||
| C | 3 | 3 | ||||
| D | 5 | 3 | 2 | 7 | ||
| E | 2 | 3 | ||||
| F | 16 | 7 | 3 |
дороги спискомA–B 2A–C 3A–F 16B–D 5C–D 3D–E 2D–F 7E–F 3
+5 на линии — длина дороги из таблицы7 в рамке у пункта — сумма от начала11 у F — длина всего пути
Из A три дороги — три ветки. Из B новая дорога одна — в D: 2 + 5 = 7; назад нельзя. Из C после D идти некуда — тупик. До F дошли пять путей: 12, 14, 11, 13, 16. Кратчайший — A–C–D–E–F, хотя дорог в нём больше всех.
почему нельзя на глаз
A–F — 16 км, а в обход — 11. Прямая дорога почти всегда длинная. Но не всегда: её сумму сравнивают с остальными, а не отбрасывают не глядя.
A–C–D–F — три дороги, 13 км. A–C–D–E–F — четыре дороги, 11 км. Считаем километры, а не дороги.
Из A самая короткая дорога — в B (2). Но через B выходит 12, а через C — 11. Короткая дорога в начале может привести на длинную.
Выписать все пути и сравнить суммы. Лучший обгоняет следующий всего на 1–2 км — на глаз это не видно.
второй вид задачи
Граф той же таблицы, что на слайде 3. Вопрос: из A в F, проходящий через пункт B — он на графе в рамке.
Проводим по графу все пути и оставляем те, что задевают B: 12 и 14. Пути 11, 13 и 16 идут мимо — вычёркиваем. Слова «через пункт» стоят в середине предложения — пропустить их легче всего.
ловушка последних лет
Дороги: A–B 3, A–F 15, B–C 2, B–D 2, C–E 4, D–E 1, D–F 2, E–F 5. Из A в F через E (он в рамке).
Пути через E: 11, 12 (A–B–C–E–D–F) и 14 (A–B–C–E–F). Складывать отрезки «до» и «от» можно, только если у них нет общих пунктов. Надёжнее не складывать, а провести пути по графу целиком.
порядок работы
где теряют балл
Взяли число из соседней строки или «поехали» по дороге, которой нет. Ведите по строке пальцем или линейкой.
Нашли два-три пути и остановились. Кратчайший часто самый неочевидный — с наибольшим числом дорог.
Нашли кратчайший путь вообще — а он идёт мимо нужного пункта.
Лучший путь отличается от следующего на 1–2 км: одна ошибка в сумме — и ответ другой. Суммы от начала спасают.
итог
Таблица дорог, найти самый короткий путь. Различаются только три вещи.
Пять или шесть пунктов — дерево побольше или поменьше
Прямая дорога — длинная обманка или настоящий соперник
«Через пункт» — отбор путей, а иногда и ловушка с повтором
Дороги — списком
Таблицу — графом, пути — по графу, с суммами
Ответ — наименьшая сумма, только число
Дальше — тренажёр: шесть задач, по одной на каждый тип. Таблицы у всех свои, проверка сразу. Тетрадь и ручка обязательны: граф рисуют на бумаге.