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

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

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

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

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

Шаг 3. Расчёт для конечного пункта.
В пункт $G$ ведут дороги из пунктов $E$ и $F$:
$N(G) = N(E) + N(F) = 4 + 6 = 10$.
Внимание: Перепроверим связи на рисунке. В пункт $G$ входят стрелки из $E$, $F$ и напрямую из $C$.
Уточним расчёт для $G$:
$N(G) = N(C) + N(E) + N(F) = 2 + 4 + 6 = 12$.

Таким образом, существует $12$ различных путей из пункта $A$ в пункт $G$.

Ответ: 12

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