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

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

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

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

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

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

4. Переходим к городу Д. В него ведут стрелки из Б и В:
$N(D) = N(B) + N(V) = 1 + 3 = 4$

5. Переходим к городу Е. В него ведут стрелки из В и Г:
$N(E) = N(V) + N(G) = 3 + 1 = 4$

6. Наконец, вычислим количество путей в конечный пункт К. В него ведут стрелки из городов Д и Е:
$N(K) = N(D) + N(E) = 4 + 4 = 8$

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

Ответ: 8

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