На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город H?
Ответ:
Демонстрационный вариант ОГЭ 2026 по информатике задание №9
Решение:
Посчитаем количество путей динамически, справа налево.
Из города H в H один путь:
- P(H) = 1
Из G можно попасть только в H:
- P(G) = P(H) = 1
Из F идут дороги в G и H:
- P(F) = P(G) + P(H) = 1 + 1 = 2
Из E – в F и G:
- P(E) = P(F) + P(G) = 2 + 1 = 3
Из D – только в F:
- P(D) = P(F) = 2
Из C – в E и F:
- P(C) = P(E) + P(F) = 3 + 2 = 5
Из B – только в E:
- P(B) = P(E) = 3
Наконец, из A дороги ведут в B, C и D:
- P(A) = P(B) + P(C) + P(D) = 3 + 5 + 2 = 10
Ответ: 10