Задание №9 — Теоретические основы информатики

Решение. Для решения этой задачи мы воспользуемся методом динамического подсчёта путей. Суть метода заключается в том, что количество способов добраться в конкретный город равно сумме способов добраться во все города, из которых в него ведут прямые дороги.

Обозначим через $N(X)$ количество различных путей из города А в город $X$.

Шаг 1. Начальная точка.
Для города А, который является началом пути, принимаем:
$N(A) = 1$.

Шаг 2. Расчёт для промежуточных городов.
Будем двигаться последовательно от начала графа к его концу, выбирая те вершины, для которых уже известны значения всех входящих в них стрелок.
1. В город B ведёт только одна дорога из A:
$N(B) = N(A) = 1$.
2. В город E ведёт только одна дорога из A:
$N(E) = N(A) = 1$.
3. В город F ведут дороги из A и E:
$N(F) = N(A) + N(E) = 1 + 1 = 2$.
4. В город G ведут дороги из E и F:
$N(G) = N(E) + N(F) = 1 + 2 = 3$.
5. В город H ведут дороги из F и G:
$N(H) = N(F) + N(G) = 2 + 3 = 5$.

Шаг 3. Расчёт для городов верхней ветки и финиша.
6. В город C ведут дороги из B и F:
$N(C) = N(B) + N(F) = 1 + 2 = 3$.
7. Теперь мы можем найти количество путей в финальный город D. В него ведут дороги из городов C, F и H:
$N(D) = N(C) + N(F) + N(H)$.
Подставим найденные значения:
$N(D) = 3 + 2 + 5 = 10$.

Таким образом, существует 10 различных путей из города А в город D.

Ответ: 10

Источник: ФИПИ