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

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

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

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

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

3. Теперь рассмотрим город В. В него ведут дороги из Б, А и Г:
$N(В) = N(Б) + N(A) + N(Г) = 1 + 1 + 1 = 3$

4. Перейдём к городу Д. В него можно попасть только из города Г:
$N(Д) = N(Г) = 1$

5. Рассмотрим город Е. В него ведут дороги из В и Д:
$N(Е) = N(В) + N(Д) = 3 + 1 = 4$

6. Наконец, вычислим количество путей в финальный пункт — город К. В него ведут дороги из городов В и Е:
$N(К) = N(В) + N(Е) = 3 + 4 = 7$
Внимание: Перепроверим схему. В город К ведут стрелки из В, Е и Д.
Уточним расчёт для К: $N(К) = N(В) + N(Е) + N(Д)$.
Подставим значения: $N(К) = 3 + 4 + 1 = 8$.

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

Ответ: 8

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