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

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

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

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

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

3. Переходим к следующим городам:
В город Д ведёт дорога только из В:
$N(Д) = N(В) = 3$
В город Е ведёт дорога только из В:
$N(Е) = N(В) = 3$
В город Ж ведут дороги из Д и Е:
$N(Ж) = N(Д) + N(Е) = 3 + 3 = 6$

4. Наконец, вычислим количество путей для конечного пункта К:
В город К ведут дороги из В и Ж. Сложим их значения:
$N(К) = N(В) + N(Ж) = 3 + 6 = 9$

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

Ответ: 9

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