На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Г?
[рис.]
Сколько существует различных путей из города А в город М, проходящих через город Г?
[рис.]
💡 Пошаговый разбор и решение:
Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.
При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1.
Д = А = 1.
Г = А + Д = 2.
В = Г = 2. (А и Б не учитываем, поскольку путь должен проходить через Г)
Е = В = 2. (Б не учитываем, поскольку путь должен проходить через Г)
З = В + Г = 4. (Д не учитываем, поскольку путь должен проходить через Г)
Ж = В + Е + З = 8.
И = Е + Ж + З = 14.
К = И = 14.
Л = И + К = 28.
М = Л + К = 42.
Примечание. Необходимо найти количество различных путей из города А в город М, проходящих через город Г.
Ответ: 42.
При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1.
Д = А = 1.
Г = А + Д = 2.
В = Г = 2. (А и Б не учитываем, поскольку путь должен проходить через Г)
Е = В = 2. (Б не учитываем, поскольку путь должен проходить через Г)
З = В + Г = 4. (Д не учитываем, поскольку путь должен проходить через Г)
Ж = В + Е + З = 8.
И = Е + Ж + З = 14.
К = И = 14.
Л = И + К = 28.
М = Л + К = 42.
Примечание. Необходимо найти количество различных путей из города А в город М, проходящих через город Г.
Ответ: 42.
Правильный ответ:
42
📚 Похожие разобранные задания по предмету:
ID 34115 • Задание №24
Требовалось написать программу, при выполнении которой с клавиатуры считывается натуральное число N, не превос...
ID 31050 • Задание №9
Откройте файл электронной таблицы, содержащей в каждой строке три натуральных числа.
Задание 9
Выясните, как...
🔗 Другие задания линии №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...