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

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

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

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

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

3. Переходим к следующим вершинам:
В город E ведёт стрелка только из C:
$N(E) = N(C) = 2$.
В город F ведут стрелки из C и D:
$N(F) = N(C) + N(D) = 2 + 1 = 3$.

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

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

Ответ: 7

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