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

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

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

Пояснение

Решение. Для решения этой задачи мы воспользуемся методом динамического подсчёта путей. Суть метода заключается в том, что количество путей в пункт $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

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