Задание 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 — Теоретические основы информатики

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, И, К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

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

Пояснение

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

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

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

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

3. Теперь вычислим значение для города В. В него ведут дороги из А и Б:
$N(В) = N(A) + N(Б) = 1 + 1 = 2$

4. Вычислим значение для города Д. В него ведёт только одна дорога из В:
$N(Д) = N(В) = 2$

5. Вычислим значение для города Е. В него ведёт только одна дорога из Г:
$N(Е) = N(Г) = 1$

6. Вычислим значение для города И. В него ведут дороги из В и Г:
$N(И) = N(В) + N(Г) = 2 + 1 = 3$

7. Наконец, вычислим количество путей в конечный пункт К. В него ведут дороги из городов Д, В, И, Г и Е:
$N(К) = N(Д) + N(В) + N(И) + N(Г) + N(Е)$
Подставим найденные значения:
$N(К) = 2 + 2 + 3 + 1 + 1 = 9$

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

Ответ: 9

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