ОГЭ по информатике: задание 4 — тренажёр
Теория по заданию 4: Кратчайший путь по таблице дорог
Задание 4 — это таблица расстояний между населёнными пунктами (матрица смежности графа). Нужно найти длину кратчайшего пути между двумя пунктами.
Ключевые идеи
- Таблица задаёт граф: на пересечении строки и столбца — длина дороги между пунктами.
- Кратчайший путь ищут перебором разумных маршрутов или методом пометок (как у Дейкстры).
- Путь «через пункт X» = кратчайший путь от начала до X плюс кратчайший путь от X до конца.
Типовой алгоритм решения
- Выпишите все дороги (рёбра) и их длины из таблицы.
- Переберите возможные маршруты от начального пункта к конечному.
- Сложите длины дорог в каждом маршруте и выберите наименьшую сумму.
Типичные ошибки
- Рассматривают только прямую дорогу, упуская более короткий обходной путь.
- Теряют один из участков при сложении длин.
- В задаче «через пункт» забывают, что путь обязан проходить через указанный пункт.
Выберите количество задач на странице, порядок сортировки и решайте задачи. Ответ и пояснение можно открыть по отдельным кнопкам для каждой задачи.
Задание 4. В банке задач: 30. Сейчас показывается 10 задач(и) на странице.
Показать по:
Страница:
Задача 1 (легкая)
ID: 4-001Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице:
| A | B | C | D | E | |
| A | 1 | ||||
| B | 1 | 2 | 2 | 7 | |
| C | 2 | 3 | |||
| D | 2 | 4 | |||
| E | 7 | 3 | 4 |
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Задача 2 (легкая)
ID: 4-002Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице:
| A | B | C | D | E | |
| A | 8 | 16 | |||
| B | 5 | 7 | 7 | ||
| C | 8 | 5 | 2 | ||
| D | 7 | ||||
| E | 16 | 7 | 2 |
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Задача 3 (легкая)
ID: 4-003Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице:
| A | B | C | D | E | |
| A | 5 | 14 | |||
| B | 8 | 2 | 7 | ||
| C | 8 | 3 | |||
| D | 5 | 2 | 3 | 7 | |
| E | 14 | 7 | 7 |
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Задача 4 (легкая)
ID: 4-004Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице:
| A | B | C | D | E | |
| A | 4 | 7 | 12 | ||
| B | 4 | ||||
| C | 7 | 6 | 1 | ||
| D | 6 | 2 | |||
| E | 12 | 1 | 2 |
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Задача 5 (легкая)
ID: 4-005Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице:
| A | B | C | D | E | |
| A | 1 | 14 | |||
| B | 2 | 1 | |||
| C | 1 | 2 | 2 | 8 | |
| D | 2 | ||||
| E | 14 | 1 | 8 |
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Задача 6 (легкая)
ID: 4-006Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице:
| A | B | C | D | E | |
| A | 4 | 5 | 5 | ||
| B | 4 | 4 | 4 | 1 | |
| C | 5 | 4 | 4 | 1 | |
| D | 5 | 4 | 4 | 9 | |
| E | 1 | 1 | 9 |
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Задача 7 (легкая)
ID: 4-007Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице:
| A | B | C | D | E | |
| A | 5 | 15 | |||
| B | 6 | 3 | |||
| C | 5 | 6 | 9 | ||
| D | 9 | 8 | |||
| E | 15 | 3 | 8 |
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Задача 8 (легкая)
ID: 4-008Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице:
| A | B | C | D | E | |
| A | 4 | 6 | 8 | ||
| B | 4 | ||||
| C | 6 | 4 | |||
| D | 8 | 2 | |||
| E | 4 | 2 |
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Задача 9 (средняя)
ID: 4-009Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице:
| A | B | C | D | E | F | |
| A | 2 | 5 | 9 | |||
| B | 2 | 2 | 1 | 5 | ||
| C | 5 | 2 | 1 | |||
| D | 1 | |||||
| E | 1 | 1 | ||||
| F | 9 | 5 | 1 |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Задача 10 (средняя)
ID: 4-010Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице:
| A | B | C | D | E | F | |
| A | 3 | 7 | 2 | |||
| B | 3 | |||||
| C | 7 | 3 | 1 | |||
| D | 3 | 1 | 2 | |||
| E | 1 | 1 | ||||
| F | 2 | 2 |
Определите длину кратчайшего пути между пунктами B и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Показать по:
Страница: