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

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

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

1. Начнём с начального пункта. В город $A$ существует только один путь (начальная точка):
$N(A) = 1$

2. Теперь найдём количество путей для городов, в которые ведут стрелки из $A$:
В город $B$ ведёт только одна стрелка из $A$:
$N(B) = N(A) = 1$
В город $E$ ведёт только одна стрелка из $A$:
$N(E) = N(A) = 1$

3. Рассмотрим город $F$. В него можно попасть только из города $E$:
$N(F) = N(E) = 1$

4. Рассмотрим город $G$. В него ведут стрелки из городов $E$ и $F$:
$N(G) = N(E) + N(F) = 1 + 1 = 2$

5. Рассмотрим город $C$. В него ведут стрелки из городов $B$ и $G$:
$N(C) = N(B) + N(G) = 1 + 2 = 3$

6. Наконец, найдём количество путей в целевой город $D$. В него ведут стрелки из городов $B$ и $C$:
$N(D) = N(B) + N(C) = 1 + 3 = 4$

Внимание: Давайте ещё раз внимательно изучим схему дорог на рисунке. Мы видим, что в город $D$ ведут стрелки из $B$, $C$ и напрямую из $G$. Пересчитаем финальный шаг:
В город $D$ ведут стрелки из $B$, $C$ и $G$.
Однако, если внимательно посмотреть на граф, стрелка из $G$ идёт в $C$, а из $C$ в $D$. Также есть прямая стрелка из $G$ в $D$.
Проверим связи для $D$: в него входят стрелки от $B$, $C$ и $G$.
Тогда: $N(D) = N(B) + N(C) + N(G)$.
Но согласно рисунку, в $C$ входят $B$ и $G$. Значит $N(C) = 1 + 2 = 3$.
В $D$ входят стрелки от $B$ (1 путь) и $C$ (3 пути). Также на рисунке видна стрелка от $G$ в $D$.
Следовательно: $N(D) = N(B) + N(C) + N(G)$ не совсем верно, так как $G$ уже входит в $C$.
Посмотрим на рисунок ещё раз: в $D$ входят стрелки от $B$ и $C$. А в $C$ входят стрелки от $B$, $G$ и $F$? Нет, в $C$ входят $B$ и $G$. В $G$ входят $E$ и $F$.
Верный подсчёт по графу:
$N(A) = 1$
$N(B) = N(A) = 1$
$N(E) = N(A) = 1$
$N(F) = N(E) = 1$
$N(G) = N(E) + N(F) = 1 + 1 = 2$
В город $C$ ведут стрелки от $B$ и $G$: $N(C) = 1 + 2 = 3$.
В город $D$ ведут стрелки от $C$ и $G$: $N(D) = N(C) + N(G) = 3 + 2 = 5$.

Ответ: 5

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