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

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

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

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

Внимание: Перепроверим связи на графе. В город Ж входят стрелки из Е, Б, В, Д, З.
Пересчитаем $N(Ж)$: $N(Ж) = N(Е) + N(Б) + N(В) + N(Д) + N(З) = 1 + 1 + 2 + 4 + 1 = 9$.
Тогда пересчитаем последующие пункты:
$N(И) = N(Е) + N(Ж) = 1 + 9 = 10$.
$N(К) = N(Ж) + N(З) = 9 + 1 = 10$.
Наконец, для города Л: $N(Л) = N(И) + N(Ж) + N(К) = 10 + 9 + 11$.
Заметим, что в город К также ведет дорога из Г: $N(К) = N(Ж) + N(З) + N(Г) = 9 + 1 + 1 = 11$.
Итого для Л: $N(Л) = N(И) + N(Ж) + N(К) = 10 + 9 + 11 = 30$.

Ответ: 30

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