Вопрос по информатике:
Между населенными пунктам A,B,C,D,E,F,Z построены дороги протяженность которых приведена в таблице(отсутствие числа в таблице означает, что прямой дороги между пунктами нет)
A B C D E F Z
A 7 57
B 7 5 7 27
C 5 3
D 7 3 2
E 27 2 2 8
F 2 3
Z 57 8 3
Определить длину кратчайшего пути между пунктами AиZ (при условии что передвигаться можно только по построенным дорогам)
1)21
2)24
3)42
4) 57
Пожалуйста с подробным решением
Трудности с пониманием предмета? Готовишься к экзаменам, ОГЭ или ЕГЭ?
Воспользуйся формой подбора репетитора и занимайся онлайн. Пробный урок - бесплатно!
- 10.08.2015 09:12
- Информатика
- remove_red_eye 583
- thumb_up 8
Ответы и объяснения 1
1) Из А только два пути - AB=7, AZ=57.
AZ слишком большой, для начала отбросим его.
Идём по AB=7.
2) Из B три пути: BC=5, BD=7, BE=27.
BE слишком большой, пока отбросим его.
2.1) Рассмотрим для BC=5 :
Из C есть только один путь, CD=3.
Рассмотрим для CD :
Из D есть DB, но нам незачем возвращаться; значит остаётся DE=2.
Рассмотрим для DE :
Из Е есть EB, но это возврат, есть EF=2 и EZ=8
2.1.1) Если мы идём по EF, то от F есть FZ=3
В итоге, получается: A-B-C-D-E-F-Z = 7+5+3+2+2+3 = 22
2.1.2) Если в предпоследнем шаге пойти по EZ=8, то получается A-B-C-D-E-Z = 7+5+3+2+8 = 25
2.2) Рассмотрим для BD=7
Этим шагом мы как бы перескочим B-C-D
Из D есть DC и DE, идти в С нет смысла, так что идём в DE=2
Из Е есть EF=2 и EZ=8
2.2.1) Для начала пойдём в EF=2, FZ=3
Получается A-B-D-E-F-Z = 7+7+2+2+3 = 21
2.2.2) Другой вариант, EZ=8
Получается A-B-D-E-Z = 7+7+2+8 =24
Ответ уже найдет, выделен жирным, но в других задачах иногда нужно просмотреть абсолютно все пути.
- 11.08.2015 00:04
- thumb_up 5
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.