На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город П, проходящих через город Л?
[рис.]
Сколько существует различных путей из города А в город П, проходящих через город Л?
[рис.]
💡 Пошаговый разбор и решение:
Количество путей до города П = сумме путей в каждый из тех городов, из которых есть дорога в П. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов, кроме тех, которые не проходят через город Л:
А = 1
Б = А = 1
Д = А = 1
Г = А + Б = 1 + 1 = 2
В = Б + Г = 1 + 2 = 3
Е = Г + Д = 2 + 1 = 3
Ж = В + Г + Е = 3 + 2 + 3 = 8
K = Ж = 8
Н = Ж = 8
М = Ж + Н = 16
Л = К + Ж + М = 8 + 8 + 16 = 32
П = Л = 32 (так как ищем пути проходящие через город Л).
Приведем другое решение.
Заметим, что путь из города А в город П обязательно должен проходить через город Ж. По условию задачи путь должен также проходить через город Л. Тогда количество путей из города А в город П, проходящих через город Л, = произведению количества путей из города А в город Ж, количества путей из города Ж в город Л и количества путей из города Л в город П.
Найдем количество путей из города А в город Ж:
А = 1
Б = А = 1
Д = А = 1
Г = А + Б = 1 + 1 = 2
В = Б + Г = 1 + 2 = 3
Е = Г + Д = 2 + 1 = 3
Ж = В + Г + Е = 3 + 2 + 3 = 8.
Найдем количество путей из города Ж в город Л (при этом Ж - исходный пункт):
Ж = 1
Н = К = Ж = 1
М = Ж + Н = 2
Л = К + Ж + М = 4.
Из города Л в город П есть только один путь.
Тогда количество путей из города А в город П, проходящих через город Л, = 8 · 4 · 1 = 32.
Ответ: 32.
А = 1
Б = А = 1
Д = А = 1
Г = А + Б = 1 + 1 = 2
В = Б + Г = 1 + 2 = 3
Е = Г + Д = 2 + 1 = 3
Ж = В + Г + Е = 3 + 2 + 3 = 8
K = Ж = 8
Н = Ж = 8
М = Ж + Н = 16
Л = К + Ж + М = 8 + 8 + 16 = 32
П = Л = 32 (так как ищем пути проходящие через город Л).
Приведем другое решение.
Заметим, что путь из города А в город П обязательно должен проходить через город Ж. По условию задачи путь должен также проходить через город Л. Тогда количество путей из города А в город П, проходящих через город Л, = произведению количества путей из города А в город Ж, количества путей из города Ж в город Л и количества путей из города Л в город П.
Найдем количество путей из города А в город Ж:
А = 1
Б = А = 1
Д = А = 1
Г = А + Б = 1 + 1 = 2
В = Б + Г = 1 + 2 = 3
Е = Г + Д = 2 + 1 = 3
Ж = В + Г + Е = 3 + 2 + 3 = 8.
Найдем количество путей из города Ж в город Л (при этом Ж - исходный пункт):
Ж = 1
Н = К = Ж = 1
М = Ж + Н = 2
Л = К + Ж + М = 4.
Из города Л в город П есть только один путь.
Тогда количество путей из города А в город П, проходящих через город Л, = 8 · 4 · 1 = 32.
Ответ: 32.
Правильный ответ:
32
📚 Похожие разобранные задания по предмету:
ID 34255 • Задание №25
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включ...
ID 33714 • Задание №22
Ниже записана программа. Получив на вход число x , эта программа печатает два числа, L и M. Укажите наименьшее...
🔗 Другие задания линии №9 по предмету Информатика:
ID 140567
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дорог...
ID 140568
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двига...
ID 140569
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дорог...
ID 140570
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дорог...
ID 140571
На рисунке — схема дорог, связывающих города А, B, C, D, E, G, H, F. По каждой дороге можно дв...