Задание №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$
В город Е ведёт стрелка только из Г:
$N(Е) = N(Г) = 1$

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

Стоп! Перепроверим схему дорог внимательно.
На рисунке видно, что из города В также идут дороги в Д и Е, а не только в К. Пересчитаем:
$N(А) = 1$
$N(Б) = N(А) = 1$
$N(Г) = N(А) = 1$
$N(В) = N(Б) + N(А) + N(Г) = 1 + 1 + 1 = 3$
Теперь Д: в него ведут стрелки из Б и В:
$N(Д) = N(Б) + N(В) = 1 + 3 = 4$
Теперь Е: в него ведут стрелки из В и Г:
$N(Е) = N(В) + N(Г) = 3 + 1 = 4$
Теперь К: в него ведут стрелки только из Д и Е:
$N(К) = N(Д) + N(Е) = 4 + 4 = 8$

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

Ответ: 8

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