Упр.3.41 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)
Босова, Аквилянов
7 класс
Класс
7
Предмет
Информатика
Автор
Босова, Аквилянов
Упр.3.41 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)
Задача
- Шесть торговых точек А, Б, В, Г, Д, Е соединены дорогами с односторонним движением (направление движения указано стрелками, протяжённость дорог в км — числами). Необходимо перевезти груз из точки А в точку Е. Ответьте на вопросы:
1) Сколько существует различных вариантов маршрута?
2) Какой маршрут самый короткий?
3) Какой маршрут следует выбрать, чтобы по пути посетить все торговые точки?
Для решения задачи постройте и проанализируйте дерево.
Подробный ответ
Из точки А можно попасть в Е четырьмя различными маршрутами:
- $$A \to Г \to Д \to В \to Е$$
- $$A \to Б \to В \to Е$$
- $$A \to Б \to Д \to В \to Е$$
- $$A \to Б \to Г \to Д \to В \to Е$$
Найдём длину каждого маршрута:
- $$A \to Г \to Д \to В \to Е: \; 3+5+5+7=20$$
- $$A \to Б \to В \to Е: \; 5+7+7=19$$
- $$A \to Б \to Д \to В \to Е: \; 5+3+5+7=20$$
- $$A \to Б \to Г \to Д \to В \to Е: \; 5+6+5+5+7=28$$
Самый короткий маршрут — $$A \to Б \to В \to Е$$, его длина равна $$19$$ км.
Чтобы по пути посетить все торговые точки, нужно выбрать маршрут:
$$A \to Б \to Г \to Д \to В \to Е$$
Ответ: 1) 4 маршрута; 2) $$A \to Б \to В \to Е$$; 3) $$A \to Б \to Г \to Д \to В \to Е$$.
Другие учебники
Другие предметы