Question

пож. помогите с задачей.....почтальон печкин должен выйти из почты обойти четыре дома и вернуться на почту.расстояние указано на чертеже. 1)Выберите различные маршруты почтальона и найдите длину каждого из них. 2) Найдите самый короткий и самый длинный маршрут. 3) Сколько всего есть различных маршрутов?( Один дом почтальон посещает один раз; два маршрута ,различающиеся только направлением обхода,считаются одинаковыми.)

Answer 1

Так как дано 4 дома,то количество вариантов маршрутов вычисляется так:
1*2*3*4 = 24 варианта

Answer 2

Для решения этой задачи можно использовать метод перебора. Мы можем перебирать все возможные комбинации маршрутов поочередно и находить длину каждого маршрута, а затем выбирать самый короткий и самый длинный. 1) Чтобы найти все различные маршруты почтальона, нужно составить все возможные комбинации из обхода 4-х домов. Всего возможно 4! = 4*3*2*1 = 24 комбинации. 2) Для нахождения самого короткого и самого длинного маршрутов, необходимо посчитать длину каждого из 24 маршрутов и сравнить их. Для этого нужно сложить расстояния между каждой парой домов на маршруте. Пусть на чертеже указаны расстояния между домами следующим образом: а --- b = 10 а --- с = 5 b --- c = 8 b --- d = 6 с --- d = 7 Теперь применим метод перебора и найдем длины всех 24 маршрутов: 1-2-3-4: 10 + 8 + 7 + 6 = 31 1-2-4-3: 10 + 6 + 7 + 8 = 31 1-3-2-4: 5 + 8 + 6 + 7 = 26 1-3-4-2: 5 + 7 + 6 + 8 = 26 1-4-2-3: 10 + 6 + 8 + 7 = 31 1-4-3-2: 10 + 7 + 8 + 6 = 31 2-1-3-4: 10 + 5 + 7 + 6 = 28 2-1-4-3: 10 + 5 + 6 + 7 = 28 2-3-1-4: 8 + 5 + 7 + 6 = 26 2-3-4-1: 8 + 7 + 6 + 5 = 26 2-4-1-3: 6 + 5 + 7 + 8 = 26 2-4-3-1: 6 + 7 + 8 + 5 = 26 3-1-2-4: 5 + 10 + 8 + 7 = 30 3-1-4-2: 5 + 10 + 7 + 8 = 30 3-2-1-4: 8 + 10 + 7 + 6 = 31 3-2-4-1: 8 + 7 + 6 + 10 = 31 3-4-1-2: 7 + 10 + 8 + 6 = 31 3-4-2-1: 7 + 8 + 6 + 10 = 31 4-1-2-3: 10 + 5 + 8 + 7 = 30 4-1-3-2: 10 + 5 + 7 + 8 = 30 4-2-1-3: 6 + 5 + 8 + 7 = 26 4-2-3-1: 6 + 7 + 8 + 5 = 26 4-3-1-2: 7 + 5 + 8 + 6 = 26 4-3-2-1: 7 + 8 + 6 + 5 = 26 Самый короткий маршрут имеет длину 26, а самый длинный - 31. 3) Всего различных маршрутов имеется 6. Это можно увидеть из перебора, где все маршруты, отличающиеся только направлением обхода, считаются одинаковыми.