Вопрос по информатике:
Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам) III вариант IV вариант
- 09.11.2017 05:41
- Информатика
- remove_red_eye 16051
- thumb_up 40
Ответы и объяснения 2
В F можно попасть непосредственно из А или из Е.
Путь А-Е имеет длину 5. Осталось найти путь, если он есть, из А в Е с длиной не более 5-1-1=3. Почему столько? одна единица - это путь E-F, а вторая - это чтобы путь был короче A-F=5.
Как попасть в Е? Можно из А (длина 5 и это много) или D (длина 1).
Поищем вариант A-D диной не более 3-1=2. И он есть, и именно 2.
Поэтому кратчайший путь - это A-D-E-F с длиной 2+1+1=4
Вариант IV.
В F ведут пути из B, C, D ,Е. Это много. Посмотрим тогда куда можно попасть из А.
А-С длина 2, A-D длина 1.
D-F имеет длину 4 и путь A-F длины 4+1=5 мы уже нашли. Нет ли короче, хотя бы 4?
Вернемся к F. Чтобы получить путь не больше 4, из F должен быть путь в D не более 3 или в С не более 2. Таких путей нет., следовательно кратчайший путь A-D-F длины 1+4=5
- 01.01.1970 00:00
- thumb_up 24
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.