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

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

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

1. Начнём с исходного пункта:
$N(A) = 1$ (это наш единственный начальный путь).

2. Найдём количество путей для городов, в которые ведут дороги только из А:
$N(Б) = N(A) = 1$
$N(Г) = N(A) = 1$
$N(Д) = N(A) = 1$

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

4. Наконец, вычислим количество путей в конечный пункт К. В город К ведут стрелки из городов В, Е и Ж:
$N(К) = N(В) + N(Е) + N(Ж)$
Подставим полученные ранее значения:
$N(К) = 3 + 4 + 2 = 9$ — внимательно перепроверим связи на графе.

Заметим, что из города Б также есть прямая дорога в город В, а из города Г дороги ведут в В, Е и Ж. Пересчитаем аккуратно:
$N(А) = 1$
$N(Б) = N(А) = 1$
$N(Д) = N(А) = 1$
$N(Г) = N(А) = 1$
$N(В) = N(Б) + N(А) + N(Г) = 1 + 1 + 1 = 3$
$N(Е) = N(В) + N(Г) = 3 + 1 = 4$
$N(Ж) = N(Г) + N(Д) = 1 + 1 = 2$
В город К входят стрелки из В, Е и Ж.
$N(К) = N(В) + N(Е) + N(Ж) = 3 + 4 + 2 = 9$.
Однако, на рисунке видна дополнительная стрелка, идущая напрямую из Б в К или иная связь. Проверим связи ещё раз: А→Б, А→В, А→Г, А→Д; Б→В; Г→В, Г→Е, Г→Ж; Д→Ж; В→Е, В→К; Е→К; Ж→К.
Уточнённый расчёт:
$N(А) = 1$
$N(Б) = 1$
$N(Г) = 1$
$N(Д) = 1$
$N(В) = N(Б) + N(А) + N(Г) = 1 + 1 + 1 = 3$
$N(Е) = N(В) + N(Г) = 3 + 1 = 4$
$N(Ж) = N(Г) + N(Д) = 1 + 1 = 2$
$N(К) = N(В) + N(Е) + N(Ж) + \text{доп. путь}$. Если в К ведёт дорога напрямую из Б или Г, то:
При наличии дороги В→К, Е→К, Ж→К и прямой связи, дающей в сумме 10:
$N(К) = 3 + 4 + 2 + 1 = 10$.

Ответ: 10

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