Паша — ученик школы «Будущее» На переменах он общается с друзьями
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Паша — ученик школы «Будущее». На переменах он общается с друзьями, перекусывает или играет в настольный теннис. Чтобы осталось побольше времени на эти приятные занятия, Паша решил на перемене пройти кратчайшим путем в кабинет, где пройдет следующий урок, и отнести туда свой портфель. У Паши есть умные часы с шагомером. Он измерил расстояния между соседними кабинетами и записал их в матрицу смежности, которой с успехом пользуется вторую неделю.
Сегодня ему предстоит составить маршрут посложнее. Сколько шагов надо пройти Паше от кабинета информатики до кабинета английского языка, если он хочет зайти в столовую попить воды, но не хочет проходить мимо кабинета завуча по воспитательной работе?
Решение
Используя матрицу смежности, представим маршруты графом (сетью), где начальной вершиной будет кабинет информатики, конечной вершиной – кабинет английского языка.
И
Р
С
З
Г
Б
М
А
20
30
40
40
10
25
30
35
20
И
Р
С
З
Г
Б
М
А
20
30
40
40
10
25
30
35
20
Получается, что Паше придётся пройти самый длинный путь от кабинета информатики до кабинета английского языка, если он хочет зайти в столовую попить воды, но не хочет проходить мимо кабинета завуча по воспитательной работе:
T = 20 + 30 + 40 + 30 + 35 = 155 шагов.
Ответ: 155