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

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

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

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

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

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

4. Наконец, вычислим количество путей в конечный пункт H. В него ведут стрелки из городов F и G:
$N(H) = N(F) + N(G)$
Подставим найденные значения:
$N(H) = 3 + 3 = 6$

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

Ответ: 6

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