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

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

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

1. Начнём с начального пункта. В город A существует только один путь (начальная точка):
$N(A) = 1$

2. Найдём количество путей для городов, в которые ведут стрелки из A:
В город B ведёт только одна стрелка из A:
$N(B) = N(A) = 1$
В город C ведут стрелки из A и из B:
$N(C) = N(A) + N(B) = 1 + 1 = 2$

3. Теперь рассмотрим города D и E:
В город D ведёт только одна стрелка из B:
$N(D) = N(B) = 1$
В город E ведут стрелки из C и из D:
$N(E) = N(C) + N(D) = 2 + 1 = 3$

4. Наконец, вычислим количество путей в конечный пункт F. В него ведут стрелки из городов C и E:
$N(F) = N(C) + N(E)$
Подставим уже найденные значения:
$N(F) = 2 + 3 = 5$
Внимание: Перепроверим схему дорог. В город F также ведёт прямая дорога из города D.
Следовательно, полная формула для F выглядит так:
$N(F) = N(C) + N(D) + N(E)$
Подставляем значения:
$N(F) = 2 + 1 + 3 = 6$

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

Ответ: 6

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