Решение ГИА по информатике 3 задание из демоверсии 2017 года. Задание на умение анализировать формальные описания реальных объектов и процессов.
Давайте познакомимся с условием поставленной задачи.
Какая тут проблема, которая возникает в процессе решения задачи. Во — первых, крайне неудобный формат представлена входная информация. Это табличный формат. Значит наша цель представить входную информацию в более наглядном виде. О каком виде я говорю? Во — первых, давайте посмотрим на данную таблицу что можно сказать у нас информация симметрична относительна главной диагонали. Пример: Из А в В два километра и из В в А тоже два километра. Это означает что у нас двустороннее движение т. е. таблица является симметричной. Надо построить пятиугольник потому что у нас пять городов и в нашем пятиугольнике каждая вершина будет соответствовать каждому городу. А ребра, которые соединяют данные вершины будут соответствовать наличие дороги между данными городами. Поэтому давайте сейчас проведем визуализацию данного пятиугольника.
Теперь заполним вершины нашего так называемого пятиугольника.
Далее следует провести дороги между вершинами в соответствии с той информацией которая указана в исходной таблице. Итак, соединяем населенные пункты.
Мы представили входную информацию в более наглядном виде. Из табличной структуры получили структуру в виде графов. Из полученного рисунка видно, что анализ будет проходить гораздо лучше. Мы должны найти кратчайший путь между пунктом А и Е. Для этого просто переберем все данные маршруты.
1) А — В — С — Е = 2 + 1 + 2 = 5 км.
2) А — С — Е = 5 + 2 = 7 км.
3) А — D — C — Е = 1 + 3 + 2 = 6 км.
Всего возможно три различных маршрута. Наименьшее расстояние между городами лежит на маршруте номер 1, а именно 5 км.
Ответ: 2