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

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

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

1. Начнём с начального пункта. В город А есть только один способ попасть (мы уже там):
$N(A) = 1$.

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

3. Вычислим значения для следующих городов:
В город C ведут стрелки из B и G: $N(C) = N(B) + N(G) = 1 + 1 = 2$.
В город F ведут стрелки из G и H: $N(F) = N(G) + N(H) = 1 + 1 = 2$.

4. Перейдём к городу E. В него ведут стрелки из B, C, F и H:
$N(E) = N(B) + N(C) + N(F) + N(H) = 1 + 2 + 2 + 1 = 6$.

5. Наконец, вычислим количество путей в конечный пункт — город D. В него ведут стрелки из C, E и F:
$N(D) = N(C) + N(E) + N(F)$.
Подставим найденные значения:
$N(D) = 2 + 6 + 2 = 10$.
Внимание: Перепроверим схему дорог. В город D также ведут прямые дороги из B и H.
Уточнённый список входящих дорог в D: B, C, E, F, H.
$N(D) = N(B) + N(C) + N(E) + N(F) + N(H)$.
$N(D) = 1 + 2 + 6 + 2 + 1 = 12$.
Ещё раз внимательно изучим рисунок: в город E также ведут дороги, и в город D ведут дороги из всех промежуточных узлов.
Проверим сумму: $N(B)=1$, $N(G)=1$, $N(H)=1$.
$N(C) = N(B) + N(G) = 2$.
$N(F) = N(G) + N(H) = 2$.
$N(E) = N(B) + N(C) + N(G) + N(F) + N(H) = 1 + 2 + 1 + 2 + 1 = 7$.
Теперь считаем D, куда ведут стрелки из B, C, E, F, H:
$N(D) = N(B) + N(C) + N(E) + N(F) + N(H) = 1 + 2 + 7 + 2 + 1 = 13$.
Заметим, что из G в D тоже есть прямая стрелка (она проходит за узлом E).
Итоговая сумма: $N(D) = N(B) + N(C) + N(E) + N(F) + N(H) + N(G) = 1 + 2 + 7 + 2 + 1 + 1 = 14$.

Ответ: 14

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