Задание 9

Умение анализировать информацию, представленную в виде схем · 52 задания

Задание №9
№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города A , B , C , D , E , F , G , H . По каждой дороге можно двигаться только в одном направлении, указанном ст…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, B, C, D, E, G, H, F. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. С…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ско…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К иЛ. По каждой дороге можно двигаться только в одном направлении, указанном с…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой.…
Графы
Задание №9
№9
На рисунке – схема дорог, связывающих города А, B, C, D, E, F, G, H. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. С…
Графы

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

На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город G?

Правильный ответ

Пояснение

Решение. Для решения задачи по поиску количества путей в ориентированном графе воспользуемся методом динамического программирования. Мы будем последовательно вычислять количество способов добраться из начального пункта $A$ в каждый следующий пункт, суммируя значения в тех вершинах, из которых ведут стрелки в текущую.

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

1. Начнём с исходной точки:
$N(A) = 1$ (это наш единственный начальный путь).

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

3. Теперь рассчитаем значения для следующих вершин:
$N(E) = N(B) + N(D)$ . Подставляем: $N(E) = 1 + 3 = 4$ .
$N(F) = N(C) + N(D)$ . Подставляем: $N(F) = 1 + 3 = 4$ .

4. Наконец, вычислим количество путей до конечного пункта $G$ :
В город $G$ ведут дороги из пунктов $E$ и $F$ .
$N(G) = N(E) + N(F)$
$N(G) = 4 + 4 = 8$ .

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

Ответ: 8

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