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

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

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

1. Начнём с начального пункта:
$N(A) = 1$ (это наш старт).

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

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

4. Наконец, вычислим количество путей в финальный пункт $G$:
В пункт $G$ ведут стрелки из пунктов $E$, $C$ и $F$.
$N(G) = N(E) + N(C) + N(F)$
Подставим полученные значения:
$N(G) = 3 + 2 + 6$ — подождите, давайте внимательно перепроверим связи по рисунку.
В пункт $G$ входят стрелки из $E$, $C$, $F$.
Проверим $N(F)$ ещё раз: в $F$ входят стрелки из $C$ и $D$. $N(F) = 2 + 1 = 3$.
Проверим $N(E)$ ещё раз: в $E$ входят стрелки из $B$ и $C$. $N(E) = 1 + 2 = 3$.
Проверим $N(C)$ ещё раз: в $C$ входят стрелки из $A$, $B$, $D$.
Посмотрим на рисунок внимательнее: в $C$ ведут стрелки из $A$, $B$ и $D$.
Тогда $N(C) = N(A) + N(B) + N(D) = 1 + 1 + 1 = 3$.
Пересчитаем зависимые пункты:
$N(E) = N(B) + N(C) = 1 + 3 = 4$.
$N(F) = N(C) + N(D) = 3 + 1 = 4$.
Теперь финальный расчёт для $G$:
$N(G) = N(E) + N(C) + N(F) = 4 + 3 + 4 = 11$.

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

Ответ: 11

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