Информатика·Задания Д13 B13. Поиск путей в графе·11 класс

Сколько существует различных путей из пункта А в пункт С, проходящих

Условие

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

Рисунок к задаче

Ответ

Решение по шагам

Как рассуждать
Решение. Количество путей до пункта Х = количество путей добраться в любой из тех пунктов, из которых есть дорога в Х.При этом если путь должен не проходить через какой-то пункт, нужно просто не учитывать этот пункт при подсчёте сумм. А если пункт, наоборот, обязательно должен лежать на пути, тогда для пунктов, в которые из нужного пункта идут дороги, в суммах нужно брать только этот пункт.С помощью этого наблюдения посчитаем последовательно количество путей до каждого из пунктов:А = 1;Г = А = 1;В = А + Г = 2;Е = В + Г = 3;И = Е = 3;Л = Е = 3;Ж = Е + И + Л = 9;Н = И + Ж = 12;М = Ж + Н = 21;Р = М = 21;С = М + Р =

Осталось ещё 1 шаг — откроются после входа:

Шаг 2

Получить полное решение

Бесплатно · займёт минуту

Другие задачи по теме «Задания Д13 B13. Поиск путей в графе»

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

Похожая задача?Сфотографируйте своё условие — ИИ разберёт его по шагам так же