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

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

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

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

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

Шаг 3. Перейдём к городам, зависящим от B и G.
В город F ведут стрелки из B и G:
$N(F) = N(B) + N(G) = 1 + 1 = 2$
В город E ведёт только одна стрелка из B:
$N(E) = N(B) = 1$

Шаг 4. Найдём значение для города C.
В город C ведут стрелки из E и F:
$N(C) = N(E) + N(F) = 1 + 2 = 3$

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

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

Ответ: 7

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