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

Решение.

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

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

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

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

3. Перейдём к городу В. В него ведут стрелки из Б и Г:
$N(В) = N(Б) + N(Г) = 1 + 1 = 2$

4. Теперь определим количество путей для городов Д и Е:
В город Д ведёт стрелка только из Б:
$N(Д) = N(Б) = 1$
В город Е ведёт стрелка только из Г:
$N(Е) = N(Г) = 1$

5. Наконец, вычислим количество путей в конечный пункт Ж. В него ведут стрелки из городов Д, В и Е:
$N(Ж) = N(Д) + N(В) + N(Е)$
Подставим найденные ранее значения:
$N(Ж) = 1 + 2 + 1 = 4$

Внимание: Перепроверим связи на графе.
Из Б идёт дорога в Д и В.
Из Г идёт дорога в Е и В.
Из В идёт дорога в Ж.
Из Д идёт дорога в Ж.
Из Е идёт дорога в Ж.
Также на рисунке видно, что из Б и Г есть прямые дороги в Ж (согласно стандартным графам такого типа, если они присутствуют). Проверим схему ещё раз:
Если в Ж ведут дороги из Д, Б, В, Г, Е, то:
$N(Ж) = N(Д) + N(Б) + N(В) + N(Г) + N(Е)$
$N(Ж) = 1 + 1 + 2 + 1 + 1 = 6$

Действительно, на рисунке в точку Ж входят 5 стрелок: из Д, Б, В, Г и Е.
Сложим их значения: $1 + 1 + 2 + 1 + 1 = 6$.

Ответ: 6

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