По каждой дороге можно двигаться только в одном направлении, указанном
Условие
На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.Сколько существует различных путей из города А в город Т?
Ответ
63
Решение по шагам
Как рассуждать
Решение. Посчитаем количество способов добраться до каждой вершины:А = 1Б =Д = А = 1В = А + Б = 2Г = А + Д = 2Е = А + Б + В + Г + Д = 1 + 1 + 2 + 2 + 1 = 7К = Е = 7Л = Е + К = 14М = К + Л = 14 + 7 = 21Н = М = 21П = Н + К = 21+ 7 = 28Р = Н + Л = 21 + 14 = 35Т = П + Р = 28 + 35 = 63 Ответ: 63.
Осталось ещё 1 шаг — откроются после входа:
- Полный разбор с проверкой ответа
){kind=link}
Бесплатно · займёт минуту
Другие задачи по теме «Задания Д13 B13. Поиск путей в графе»
На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классНа рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классНа рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классНа рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К11 классСколько существует различных путей из пункта А в пункт П, не проходящих11 класс