Кратчайший путь по таблице — тренажёр

Шесть задач — по одной на каждый тип задания 4 ОГЭ. Задача всегда одна: дана таблица дорог, найти длину самого короткого пути. Разное в них — сколько пунктов, есть ли прямая дорога и надо ли пройти через заданный пункт. Условие — картинка, скопировать его не получится: таблицу читаем глазами, граф рисуем в тетради.

Оценка—

Подсказка: как решается задание 4

Что тут вообще происходит

Дана таблица. На пересечении строки и столбца стоит длина дороги между двумя пунктами; пустая клетка — дороги нет. Нужно найти самый короткий путь из одного пункта в другой и записать его длину.

Как читать таблицу

Таблица симметрична: дорога A–B и дорога B–A — одна и та же, поэтому каждое число стоит в ней дважды. Достаточно смотреть на половину выше закрашенных клеток. Удобно сразу выписать дороги списком: A–B 2, A–C 3, B–D 3 …

Порядок действий

Прочитать вопрос до конца: откуда, куда и нет ли слов «проходящего через пункт».
Нарисовать таблицу графом: каждый пункт — кружок, каждое число — линия между двумя пунктами, длину подписать на линии. Сколько чисел выше закрашенных клеток, столько и линий.
Провести по графу все пути от начала до конца, не заходя в пункт дважды, и у каждого написать сумму.
Если есть «через пункт» — оставить только пути через него.
Выбрать наименьшую сумму и обвести этот путь цветом. Это ответ.

Пример: из A в F. Пути 12, 14, 13, 16 и 11 — кратчайший A–C–D–E–F = 3 + 3 + 2 + 3 = 11 (зелёный), хотя дорог в нём больше всех.

Три ловушки

ловушка	в чём дело
прямая дорога	Она почти всегда есть и почти всегда длинная: в обход короче. Но не всегда — поэтому её сумму сравнивают с остальными, а не отбрасывают не глядя.
мало дорог — не значит коротко	Путь из четырёх коротких дорог бывает короче пути из двух. Считать надо километры, а не число дорог.
«только один раз»	Если нужно пройти через пункт, нельзя просто сложить кратчайший путь до него и кратчайший путь от него: эти отрезки могут проходить через один и тот же пункт, а дважды заходить нельзя.

Почему нельзя «по самой короткой дороге»

Выбирать из каждого пункта самую короткую дорогу — не способ: короткая дорога в начале может привести туда, откуда дальше только длинные. Иногда так выходит верно, иногда нет — и заранее не узнать. Надёжно только одно: выписать все пути и сравнить суммы.

Где теряют балл

Почти всегда — на чтении таблицы: взяли число из соседней клетки или «пошли» по дороге, которой нет (клетка пустая). И на арифметике: лучший путь отличается от следующего всего на 1–2 км, одна ошибка в сложении меняет ответ.

Как записывают ответ

Только цифры: 9. Без «км», без точки, без пробелов и без нуля впереди. Информатику сдают за компьютером, и ответ сверяет машина — знак в знак.

Откуда эти задачи

Задачи авторские, составлены в форме задания 4 ОГЭ по информатике. Форма задания и способ решения — как на экзамене, а таблицы в задачах свои: у каждого своя задача, но работа во всех одна и та же.

Материалы подготовлены с использованием технологий искусственного интеллекта.