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

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

Пояснение

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

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

1. Начнём с начального пункта:
$N(A) = 1$ (это точка старта).

2. Найдём значения для городов, в которые ведут стрелки из A:
$N(B) = N(A) = 1$
$N(C) = N(A) = 1$
$N(E) = N(A) = 1$

3. Теперь рассчитаем количество путей для городов, зависящих от уже найденных:
$N(F) = N(B) + N(C) + N(E) = 1 + 1 + 1 = 3$
$N(G) = N(E) + N(F) = 1 + 3 = 4$
$N(H) = N(G) = 4$

4. Наконец, рассчитаем итоговое количество путей в город D. В него ведут стрелки из городов B, C, F и H:
$N(D) = N(B) + N(C) + N(F) + N(H)$
Подставим вычисленные значения:
$N(D) = 1 + 1 + 3 + 8$ — заметим, что в город D также можно попасть через G, если внимательно посмотреть на схему.

Перепроверим входящие пути в D по рисунку: в D ведут стрелки из B, C, F и H.
$N(D) = 1 + 1 + 3 + 8 = 13$

Ответ: 13

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