Задание №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(Е) = N(В) + N(Г) = 3 + 1 = 4$. Нет, на рисунке в Е ведут стрелки из В и Г? Нет, в Е ведут стрелки из В и Г.
Давайте строго по графу:
$N(A) = 1$
$N(Б) = N(A) = 1$
$N(Г) = N(A) = 1$
$N(В) = N(Б) + N(A) + N(Г) = 1 + 1 + 1 = 3$
$N(Д) = N(В) = 3$
$N(Е) = N(В) + N(Г)$ — нет, в Е ведут стрелки из В и Г. По рисунку: в Е ведут стрелки из В и Г.
Тогда $N(Е) = 3 + 1 = 4$.
Тогда $N(К) = N(Д) + N(Е) = 3 + 4 = 7$? Нет.
Посмотрим на рисунок внимательнее:
Из В в К дороги нет. В К ведут дороги из Д и Е.
В Д ведет дорога из Б и В.
$N(Б) = 1$
$N(Г) = 1$
$N(В) = N(Б) + N(A) + N(Г) = 1 + 1 + 1 = 3$
$N(Д) = N(Б) + N(В) = 1 + 3 = 4$
$N(Е) = N(В) + N(Г) = 3 + 1 = 4$
$N(К) = N(Д) + N(Е) = 4 + 4 = 8$.

Ответ: 8

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