Дороги на схеме — это не просто линии, а стрелки: ехать можно только в одну сторону. В задании 9 нужно посчитать, сколько РАЗНЫХ маршрутов ведёт из одного города в другой.
Чему научишься. Считать число путей в графе дорог со стрелками — в том числе путей, обязательно проходящих (или не проходящих) через заданный город.
Что нужно знать
Тема графов и схем — курс «Информатика 5-11»: модели, графы, схемы.
Что проверяет задание 9
Дана схема дорог со стрелками (двигаться можно только в направлении стрелки). Нужно посчитать, сколько РАЗНЫХ путей ведёт из одного города в другой — иногда с условием «через такой-то город» или «не через такой-то». Ответ — число.
Метод накопительного счёта
Не перебирай маршруты по одному — считай числом путей В КАЖДЫЙ город, двигаясь от старта. Число путей в город = сумма чисел путей во все города, откуда в него ведёт стрелка.
Граф: A -> B, A -> C, B -> D, C -> D Путей в A = 1 (старт) Путей в B = путей в A = 1 (только одна стрелка A->B) Путей в C = путей в A = 1 Путей в D = путей в B + путей в C = 1 + 1 = 2 Ответ: из A в D ведёт 2 разных пути (A-B-D и A-C-D)
Порядок решения. 1) поставь число путей 1 у стартового города; 2) для каждого следующего города (по порядку следования стрелок) сложи числа путей всех городов, откуда в него есть стрелка; 3) дойди до конечного города — там и будет ответ. Если нужно «через город X» — посчитай отдельно пути до X и от X, затем перемножь.
Разбор примера («через город»)
Пути A→B→D→C = 3 разных, пути C→E→F = 2 разных. Сколько путей из A в F, обязательно через C?
Умножаем: число путей A→C (3) умножить на число путей C→F (2): 3 × 2 = 6.
Частые ошибки
- Перебирают маршруты вручную и пропускают часть — считай накопительно по городам.
- Забывают, что дороги односторонние — двигаться можно только по стрелке.
- Для «через город X» складывают вместо умножения путей до X и после X.
Проверь себя
Контрольный вопрос. Граф: A→B, A→C, B→D, C→D. Сколько разных путей из A в D? Впиши только число.
Подсказка: Путей в D = путей в B (1) + путей в C (1) = 2.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Граф: A→B, A→C, B→D, C→D, D→E. Сколько разных путей из A в E? Впиши только число.
Подсказка: Путей в D = 2 (как в примере), путей в E = путей в D = 2.
Онлайн-проверка ответа появится позже
Задание. Граф: A→B, A→C, B→D, C→D, B→E, D→E. Сколько разных путей из A в E? Впиши только число.
Подсказка: Путей в B=1, в C=1, в D=путей в B+C=2, в E=путей в B+D=1+2=3.
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Граф: A→B, A→C, A→D, B→E, C→E, D→E. Сколько разных путей из A в E? Впиши только число.
Подсказка: Путей в B=C=D=1 каждый; путей в E = 1+1+1 = 3.
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Граф: A→B, B→C, B→D, C→E, D→E, E→F. Сколько разных путей из A в F? Впиши только число.
Подсказка: Путей в B=1, в C=1, в D=1, в E=1+1=2, в F=2.
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Пути из A в C — 4 разных, пути из C в F — 3 разных. Сколько разных путей из A в F, обязательно проходящих через C? Впиши только число.
Подсказка: 4 × 3 = 12 (для каждого пути до C — любой из путей после C).
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Задание. Граф: A→B, A→C, B→D, C→D, B→C, D→E, C→E. Сколько разных путей из A в E? Впиши только число.
Подсказка: Путей в B=1, в C=путей в A+B=1+1=2, в D=путей в B+C=1+2=3, в E=путей в D+C=3+2=5.
✅ Готово, если: ты ввёл(а) верный ответ, и онлайн-проверка его приняла.
Онлайн-проверка ответа появится позже
Итог
Итог. Считай число путей накопительно: путей в город = сумма путей во все города, откуда есть стрелка. Для условия «через город X» — перемножь пути до X и пути после X.
Дальше — банк задач с РешуОГЭ с видеоразборами. Схема дорог в этих задачах — картинка на сайте-источнике: перейди по ссылке к задаче, посмотри схему и посчитай ответ по методу выше.
Видео. ▶ Видеоразбор задания 9 (обзор)
Задания для тренировки
Банк задач с РешуОГЭ по заданию 9 (29 шт.). Решай прямо на РешуОГЭ; у части задач есть видеоразбор.
- Задача 16017
- Задача 18039
- Задача 18248
- Задача 18263
- Задача 18278
- Задача 18293
- Задача 35586
- Задача 37197
- Задача 37239
- Задача 37262
- Задача 37277
- Задача 37471
- Задача 10245
- Задача 10246
- Задача 10247
- Задача 10248
- Задача 10249
- Задача 10250
- Задача 10251
- Задача 10252 — ▶ Смотреть разбор
- Задача 10253
- Задача 10254
- Задача 10255
- Задача 10257
- Задача 10258
- Задача 11016
- Задача 11017
- Задача 11019
- Задача 11020
← Назад: задание 8 · ⌂ В начало курса · К навигатору задания 9 →
