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

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

Будем обозначать количество путей до города буквой города (например, $N_A$ — количество путей до города А).

1. Начнём с начального пункта. В город А мы уже находимся, поэтому принимаем:
$N_A = 1$

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

3. Теперь рассмотрим город В. В него ведут стрелки из Б и Г:
$N_В = N_Б + N_Г = 1 + 1 = 2$

4. Рассмотрим город Е. В него ведут стрелки из В, Г и Д:
$N_Е = N_В + N_Г + N_Д = 2 + 1 + 1 = 4$

5. Наконец, найдём количество путей в конечный пункт К. В него ведут стрелки из В, Г и Е:
$N_К = N_В + N_Г + N_Е = 2 + 1 + 4 = 7$

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

Ответ: 7

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