Разборы · ОГЭ, задание 9
Задание 9 ОГЭ по информатике: количество путей в графе
Дана схема дорог с односторонним движением. Нужно найти число различных путей из одного города в другой (иногда — проходящих или не проходящих через заданный город). 1 балл.
Как решать
Для каждого города пишем число путей из начального города. У начального — 1. Число у любого города равно сумме чисел у городов, из которых в него ведут стрелки. Идём по схеме слева направо — так, чтобы к моменту подсчёта города все входящие в него уже были посчитаны.
- «Через город X»: считаем число путей до X, затем начинаем счёт заново от X (у X ставим это число), считая только пути из X.
- «Не через город X»: ставим у X ноль и считаем дальше как обычно.
Пример
На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город G?
Решение.
Считаем для каждого города число путей из A: оно равно сумме чисел у городов, из которых в него ведут дороги.
B = A = 1
C = A + B = 2
D = C = 2
E = C + D = 4
F = C + E = 6
G = F = 6
Ответ: 6.
Типичные ошибки
- Считают город раньше, чем посчитаны все города, из которых в него ведут стрелки.
- Пропускают стрелку — перед подсчётом выпишите для каждого города, откуда в него можно попасть.
Потренироваться: задание 9 новые варианты с проверкой ответа