Задание 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. Наша цель — найти $N(G)$ .

1. Для начального пункта A количество путей принимаем равным единице:
$N(A) = 1$ .

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

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

4. Наконец, вычислим количество путей для конечного пункта G:
В город G ведут стрелки из городов E и F:
$N(G) = N(E) + N(F)$ .
Подставим найденные ранее значения:
$N(G) = 2 + 3 = 5$ .
Внимание: Перепроверим схему дорог. В город G также ведёт прямая дорога из города C.
Следовательно, полная формула для G выглядит так:
$N(G) = N(E) + N(C) + N(F)$ .
Подставляем:
$N(G) = 2 + 2 + 3 = 7$ .

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

Ответ: 7

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