На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н.
Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт В?
[рис.]
Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт В?
[рис.]
💡 Пошаговый разбор и решение:
Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.
При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1.
Б = А = 1.
Г = А = 1.
Д = Б = 1.
Е = Д = 1 (В не учитываем, поскольку путь не должен проходить через город В).
Ж = Д = 1.
И = Г + Е = 2.
К = Ж + Е + И + Д = 5.
Л = К = М = 5.
Н = Л + М + К = 15.
Примечание. Необходимо найти количество различных путей из города А в город Н, не проходящих через город В.
Ответ: 15.
При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1.
Б = А = 1.
Г = А = 1.
Д = Б = 1.
Е = Д = 1 (В не учитываем, поскольку путь не должен проходить через город В).
Ж = Д = 1.
И = Г + Е = 2.
К = Ж + Е + И + Д = 5.
Л = К = М = 5.
Н = Л + М + К = 15.
Примечание. Необходимо найти количество различных путей из города А в город Н, не проходящих через город В.
Ответ: 15.
Правильный ответ:
15
📚 Похожие разобранные задания по предмету:
ID 30060 • Задание №5
исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 5.
Выполняя перв...
ID 30023 • Задание №5
У исполнителя Квадр две команды, которым присвоены номера:
1. прибавь 1,
2. возведи в квадрат.
Первая из э...
🔗 Другие задания линии №13 по предмету Информатика:
ID 31876
Маской подсети называется 32-разрядное двоичное число, которое определяет, какая часть IP-адр...
ID 31877
В терминологии сетей TCP/IP маской подсети называется 32-разрядное двоичное число, определяющ...
ID 31878
В терминологии сетей TCP/IP маской подсети называется 32-разрядное двоичное число, определяющ...
ID 31879
Если маска подсети 255.255.252.0 и IP-адрес компьютера в сети 226.185.90.162, то номер компьют...
ID 31880
В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть I...