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

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

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

1. Начнём с исходной точки:
$N(A) = 1$ (это наш единственный начальный путь).

2. Найдём значения для пунктов, в которые можно попасть напрямую из $A$:
$N(B) = N(A) = 1$
$N(C) = N(A) = 1$
$N(D) = N(A) = 1$

3. Теперь рассчитаем количество путей для промежуточных пунктов:
$N(E) = N(B) + N(C) = 1 + 1 = 2$
$N(F) = N(C) + N(D) = 1 + 1 = 2$

4. Переходим к пункту $G$. В него ведут стрелки из $E$, $C$ и $F$:
$N(G) = N(E) + N(C) + N(F) = 2 + 1 + 2 = 5$

5. Наконец, рассчитаем количество путей в финальный пункт $H$. В него ведут стрелки из $E$, $G$ и $F$:
$N(H) = N(E) + N(G) + N(F) = 2 + 5 + 2 = 9$

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

Ответ: 9

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