Главная / Задания ОГЭ / Задание 9
Задание 9 ОГЭ по информатике
Количество путей в графе. По схеме дорог с односторонним движением нужно посчитать число различных путей из одного города в другой, иногда через заданный город или в обход него.
Как решать
- Начальному городу запишите 1.
- Идите по городам по порядку: число путей в город = сумма чисел городов, из которых в него ведут стрелки.
- Путь через город X: (пути до X) × (пути от X до конца).
Частые ошибки
- Пропускают одну из входящих стрелок.
- Считают пути через X, забыв начать заново с X.
Пример задания
На рисунке — схема дорог, связывающих различные города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Схема дорог: стрелка показывает единственно разрешённое направление движения. Начальный город выделен амбером, конечный — бирюзой.
Сколько существует различных путей из города А в город К, проходящих через город Ж?
Показать ответ и разбор
Ответ: 6
Путей А→Ж: 3, путей Ж→К: 2. Через Ж: 3 × 2 = 6.
В тренажёре каждый раз новое задание этого типа: ответ проверяется сразу, после ответа виден короткий разбор.
Все задания ОГЭ
Нужна помощь с ОГЭ?
На пробном уроке посмотрим ваш уровень по 2–3 темам ОГЭ по информатике и составим план подготовки.
Записаться на пробный урок