Задание 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, H.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город H?

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

Пояснение

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

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

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

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

3. Переходим к следующим вершинам графа:
В город E ведёт стрелка только из B:
$N(E) = N(B) = 1$
В город F ведут стрелки из C и из E:
$N(F) = N(C) + N(E) = 2 + 1 = 3$
В город G ведут стрелки из C и из D:
$N(G) = N(C) + N(D) = 2 + 1 = 3$

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

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

Ответ: 6

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