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

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

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

1. Начнём с начального пункта:
$N(A) = 1$ (это точка старта).

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

3. Теперь рассчитаем количество путей для городов, зависящих от уже найденных:
$N(F) = N(B) + N(C) + N(E) = 1 + 1 + 1 = 3$
$N(G) = N(E) + N(F) = 1 + 3 = 4$
$N(H) = N(G) = 4$

4. Наконец, рассчитаем итоговое количество путей в город D. В него ведут стрелки из городов B, C, F и H:
$N(D) = N(B) + N(C) + N(F) + N(H)$
Подставим вычисленные значения:
$N(D) = 1 + 1 + 3 + 8$ — заметим, что в город D также можно попасть через G, если внимательно посмотреть на схему.

Перепроверим входящие пути в D по рисунку: в D ведут стрелки из B, C, F и H.
$N(D) = 1 + 1 + 3 + 8 = 13$

Ответ: 13

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