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

А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, C, Х, Т. По каждой дороге можно

Условие

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

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

Ответ

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

Как рассуждать
Решение. Начнем считать количество путей с конца маршрута — с города Т. Пусть N_X — количество различных путей из города А в город X, N — общее число путей. В город Т можно приехать из Х или С, поэтому N = N_Т = N_Х + N_С. (*) Аналогично:N_Х = N_С = 33;N_С = N_П + N_Н + N_Р = 11 + 11 + 11 = 33;N_П = N_Н = 11;N_Р = N_Н = 11;N_Н = N_К + N_М + N_Л = 1 + 9 + 1 = 11;N_К = N_Б = 1;N_М = N_К + N_Е + N_Л = 1 + 7 + 1 = 9;N_Л = N_Д = 1;N_Д = N_А = 1;N_Е = N_Б + N_В + N_А + N_Г + N_Д = 1 + 2 + 1 + 2 + 1 = 7;N_Б = N_А = 1; N_В = N_А + N_Б = 1 + 1 = 2;N_Г = N_А + N_Д = 1 + 1 = 2;N_Д = N_А =

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

Шаг 2

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

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

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

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

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