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

4. Наконец, найдем количество путей в финальный пункт К. В него можно попасть из городов Д, В и Е:
$N(К) = N(Д) + N(В) + N(Е)$.
Подставим уже вычисленные значения:
$N(К) = 3 + 3 + 2$ — внимание на схему: в город К ведут стрелки из Д, В и Е.
Проверим еще раз связи:
$N(Д) = 3$
$N(В) = 3$
$N(Е) = 2$ (если в Е ведет дорога только из Г и В, но по рисунку в Е ведут стрелки из В и Г).
Давайте пересчитаем внимательно по графу:
$N(А) = 1$
$N(Б) = N(А) = 1$
$N(Г) = N(А) = 1$
$N(В) = N(Б) + N(А) + N(Г) = 1 + 1 + 1 = 3$
$N(Д) = N(В) = 3$
$N(Е) = N(В) + N(Г) = 3 + 1 = 4$ (в Е ведут стрелки из В и Г)
Тогда для К, куда ведут стрелки из Д и Е:
$N(К) = N(Д) + N(Е) = 3 + 4 = 7$.
Однако, согласно рисунку, в К ведут стрелки из Д, В и Е:
$N(К) = N(Д) + N(В) + N(Е)$.
Если $N(Д) = 3$, $N(В) = 3$, а в Е ведет только дорога из Г: $N(Е) = N(Г) = 1$.
Тогда $N(К) = 3 + 3 + 1 = 7$.
Посмотрим на граф еще раз:
$N(А) = 1$
$N(Б) = 1$
$N(Г) = 1$
$N(В) = N(А) + N(Б) + N(Г) = 3$
$N(Д) = N(Б) + N(В) = 1 + 3 = 4$
$N(Е) = N(В) + N(Г) = 3 + 1 = 4$
Если К соединяется только с Д и Е: $4 + 4 = 8$.

Итоговый расчет:
$N(А) = 1$
$N(Б) = 1$
$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

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