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

#56027Задание №9ФИПИ

Графы

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К иЛ. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А вгород Л?

Правильный ответ

Пояснение

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

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

1. Для начального пункта А принимаем: $N(А) = 1$ .
2. Город Б: в него ведет только одна дорога из А. $N(Б) = N(А) = 1$ .
3. Город Г: в него ведет только одна дорога из А. $N(Г) = N(А) = 1$ .
4. Город В: в него ведут дороги из А, Б и Г. $N(В) = N(А) + N(Б) + N(Г) = 1 + 1 + 1 = 3$ .
5. Город Д: в него ведут дороги из Б и В. $N(Д) = N(Б) + N(В) = 1 + 3 = 4$ .
6. Город Е: в него ведут дороги из В и Г. $N(Е) = N(В) + N(Г) = 3 + 1 = 4$ .
7. Город Ж: в него ведут дороги из Д, В и Е. $N(Ж) = N(Д) + N(В) + N(Е) = 4 + 3 + 4 = 11$ .
8. Город З: в него ведет только одна дорога из Д. $N(З) = N(Д) = 4$ .
9. Город И: в него ведет только одна дорога из Е. $N(И) = N(Е) = 4$ .
10. Город К: в него ведут дороги из З, Ж и И. $N(К) = N(З) + N(Ж) + N(И) = 4 + 11 + 4 = 19$ .
11. Город Л: в него ведут дороги из З, К и И. $N(Л) = N(З) + N(К) + N(И) = 4 + 19 + 4 = 27$ .

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

Ответ: 27

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