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

#56060Задание №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(Б) + N(В) = 1 + 3 = 4$
$N(Е) = N(В) = 3$
$N(Ж) = N(В) + N(Г) = 3 + 1 = 4$

4. Теперь определим количество путей для городов З и И:
$N(З) = N(Д) + N(Е) = 4 + 3 = 7$
$N(И) = N(Е) + N(Ж) = 3 + 4 = 7$

5. Перейдём к городу К:
$N(К) = N(И) = 7$

6. Наконец, вычислим количество путей в конечный пункт Л:
В город Л ведут стрелки из городов З, И и К.
$N(Л) = N(З) + N(И) + N(К)$
$N(Л) = 7 + 7 + 3$ — внимание, перепроверим связи по рисунку:
В город Л входят дороги из З, Е и К.
Посмотрим внимательнее на схему:
$N(Л) = N(З) + N(Е) + N(К)$
$N(Л) = 7 + 3 + 7 = 17$

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

Ответ: 17

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