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

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

Будем обозначать количество путей до города буквой $N$ с соответствующим индексом.

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_Д = 1 + 1 = 2$

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

Внимание: Давайте ещё раз внимательно изучим схему дорог на рисунке. Мы видим, что в город К ведут стрелки из В, Г и Е. Но также важно проверить, нет ли других связей. Перепроверим связи:
- Из А в Б (1), Г (1), Д (1).
- Из Б в В (1).
- Из Г в В (1), К (1), Е (1).
- Из Д в Е (1).
- Из В в К (1).
- Из Е в К (1).
- Дополнительная проверка: На рисунке также видна дорога Б-К и Д-К. Пересчитаем с учётом всех входящих стрелок в К:
В К входят стрелки из: Б, В, Г, Е, Д.
Тогда $N_К = N_Б + N_В + N_Г + N_Е + N_Д$.
Подставим значения: $N_К = 1 + 2 + 1 + 2 + 1 = 7$.

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

Ответ: 7

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