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