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

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

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

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

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

3. Теперь рассмотрим город В. В него ведут стрелки из А, Б и Г:
$N(В) = N(A) + N(Б) + N(Г) = 1 + 1 + 1 = 3$

4. Перейдём к городу Д. В него ведут стрелки из Б и В:
$N(Д) = N(Б) + N(В) = 1 + 3 = 4$

5. Рассмотрим город Е. В него ведут стрелки из В и Г:
$N(Е) = N(В) + N(Г) = 3 + 1 = 4$

6. Наконец, вычислим количество путей для конечного пункта К. В него ведут дороги из Д, В и Е:
$N(К) = N(Д) + N(В) + N(Е)$
Подставим уже найденные значения:
$N(К) = 4 + 3 + 4 = 11$

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

Ответ: 11

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