Задание 4 ОГЭ по информатике 2027

Что проверяет задание 4

Дана таблица длин дорог между пунктами: нужно найти длину самого короткого маршрута, иногда с условием «через пункт» или «не заезжая в пункт». Часть 1, ответ — число в бланке № 1, 1 балл.

Часть1
Ответчисло в бланке № 1
Баллы1 балл
Проверяетумение анализировать простую модель — таблицу дорог между пунктами
Сколько времени закладыватьоколо 3 минут по спецификации ФИПИ

Какие бывают подтипы

Пример с полным разбором

Условие. Между пунктами A, B, C, D, E построены дороги, их длины в километрах даны в таблице; пустая клетка означает, что прямой дороги нет. Найдите длину кратчайшего пути из A в E. Каждый пункт можно посетить не больше одного раза.

ABCDE
A7312
B724
C3288
D481
E1281
  1. Прямая дорога из A в E есть, её длина 12 — это только первый кандидат.
  2. Из A ближе всего до C (3 км). Из C в E напрямую 8 км, вместе .
  3. Из C можно свернуть в B (2 км), оттуда в D (4 км), а из D в E (1 км): .
  4. Остальные маршруты длиннее: A–B–D–E и A–C–D–E дают по 12 км.

Ответ: 10

Ещё задания с решением

Кратчайший путь

Условие.

Лера составила карту дорог между населёнными пунктами.

Между пунктами А, Б, В, Г, Д, Е построены дороги. Длины приведены в таблице (пустая ячейка означает, что прямой дороги нет):

АБВГДЕ
А411107
Б412
В113312
Г1034
Д39
Е7121249

Определите длину кратчайшего пути между пунктами Б и Г. Передвигаться можно только по дорогам из таблицы. Каждый пункт можно посетить только один раз.

Решение.

Нужно найти кратчайший путь от Б до Г по таблице.

Алгоритм: перебираем все возможные маршруты (граф маленький, до 6! = 720 вариантов), запоминаем минимум.

Длина кратчайшего пути: 14.

Ответ: 14

Через указанный пункт

Условие.

Денис составил карту дорог между населёнными пунктами.

Между пунктами А, Б, В, Г, Д, Е построены дороги. Длины приведены в таблице (пустая ячейка означает, что прямой дороги нет):

АБВГДЕ
А15102
Б1515
В101114
Г1168
Д1514610
Е2810

Определите длину кратчайшего пути между пунктами Е и Г, проходящего через пункт Б. Передвигаться можно только по дорогам из таблицы. Каждый пункт можно посетить только один раз.

Решение.

Нужно найти такой маршрут Е → … → Г, в котором обязательно встречается Б.

Можно мысленно разбить путь на две части: Е → Б и Б → Г, но не повторять вершины. Перебираем все маршруты, удовлетворяющие условию.

Длина кратчайшего такого пути: 38.

Ответ: 38

Минуя пункт

Условие.

Гриша нарисовал схему транспортных маршрутов.

Между пунктами A, B, C, D, E, F построены дороги. Длины приведены в таблице (пустая ячейка означает, что прямой дороги нет):

ABCDEF
A75610
B714210
C5146
D6210
E10
F10610

Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт C. Передвигаться можно только по дорогам из таблицы. Каждый пункт можно посетить только один раз.

Решение.

В графе исключаем вершину C и все её рёбра, затем ищем кратчайший путь A → F обычным перебором.

Длина кратчайшего пути в этих условиях: 16.

Ответ: 16

Частые ошибки

Что нужно знать для задания 4

Оглавление курса «ОГЭ по информатике» под это задание. Содержание открывается после оплаты.

  1. Как читать таблицу
  2. Дерево перебора маршрутов
  3. Отсечение лишних веток
  4. Кратчайший путь без дополнительных условий
  5. Путь через указанный пункт
  6. Варианты с условиями
  7. Алгоритм решения

Открыть темы в курсе

Ответы на частые вопросы

Сколько баллов за задание 4?
Один, за число в бланке № 1, полностью совпавшее с верным.
Почему числа в таблице повторяются?
Дорога между двумя пунктами записана дважды — в строке одного пункта и в строке другого, поэтому таблица симметрична относительно диагонали.