Раздел A • Категория A2 (демонстрационный вариант-2012)

 
 
 

Условие задачи

 ABCDEF
A 24   
B2 1 7 
C41 34 
D  3 3 
E 743 2
F    2 

Дано:
между населенными пунктами А, B, C, D, E, F построены дороги, протяжность которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет).

 

Вопрос:
определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

 

Варианты ответа:
1) 9           2) 10          3) 11          4) 12

 

 

Методические указания

Решение данной задачи будет проводить с использованием специализированной структуры данных - объектный граф.

Объектный граф - это совокупность ребер и узлов, соединяющих данные узлы.

В качестве узлов графа выступают населенные пункты, а в качестве ребер графа выступают дороги, между населенными пунктами.

 

Решение

Схематично отобразим дороги между населенными пунктами в виде объектного графа.


В качестве вершин объектного графа выступают названия населенных пунктов: A, B, C, D, E, F.

В качестве ребер объектного графа выступают дороги между населенными пунктами с указанием протяженности.

Пример №1: рассмотрим населенные пункты B и E. Как видно из заданной таблицы, между данными пунктами существует дорога, следовательно, и на графе между данными вершинами будет существовать ребро. Протяженность дороги составляет 7 единиц.

Пример №2: рассмотрим населенные пункты A и D. Как видно из заданной таблицы, между данными пунктами нет дороги, следовательно, и на объектном графе между данными узлами нет соединительного ребра.

 


 

 

Рассмотрим первый вариант пути из пункта А в пункт F:


Маршрут имеет вид: A -> B -> C -> D -> E -> F.

A -> B = 2
B -> C = 1
C -> D = 3
D -> E = 3
E -> F = 2

Просуммируем выписанные значения:
A -> F = 2 + 1 + 3 +3 + 2 = 11 [ед].

Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 11 [ед].


 

 

 

Рассмотрим второй вариант пути из пункта А в пункт F:


Маршрут имеет вид: A -> B -> C -> E -> F.

A -> B = 2
B -> C = 1
C -> E = 4
E -> F = 2

Просуммируем выписанные значения:
A -> F = 2 + 1 + 4 + 2 = 9 [ед].

Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 9 [ед].




 

 

 

Рассмотрим третий вариант пути из пункта А в пункт F:


Маршрут имеет вид: A -> B -> E -> F.

A -> B = 2
B -> E = 7
E -> F = 2

Просуммируем выписанные значения:
A -> F = 2 + 7 + 2 = 11 [ед].

Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 11 [ед].




 

 

 

Рассмотрим четвертый вариант пути из пункта А в пункт F:


Маршрут имеет вид: A -> C -> D -> E -> F.

A -> C = 4
C -> D = 3

D -> E = 3
E -> F = 2

Просуммируем выписанные значения:
A -> F = 4 + 3 + 3 + 2 = 12 [ед].

Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 12 [ед].



 

 

 

Рассмотрим пятый вариант пути из пункта А в пункт F:


Маршрут имеет вид: A -> C -> E -> F.

A -> C = 4
C -> E = 4

E -> F = 2

Просуммируем выписанные значения:
A -> F = 4 + 4 + 2 = 10 [ед].

Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 10 [ед].




 

 

 

Консолидируем проверенные маршруты и выберем тот, имеющий минимальную протяженность:

  1. A -> B -> C -> D -> E -> F: 11

  2. A -> B -> C -> E -> F     :  9

  3. A -> B -> E -> F          : 11

  4. A -> C -> D -> E -> F     : 12

  5. A -> C -> E -> F          : 10

Очевидно, что минимальная протяженность составила 9 [ед].

 

Вывод:

длина кратчайшего пути между пунктами A и F составила 9 [ед].
Среди предложенных вариантов ответа вариант под номер 1 имеет абсолютно идентичное значение

Резюме

  1. A -> B -> C -> D -> E -> F: 11

  2. A -> B -> C -> E -> F     :  9

  3. A -> B -> E -> F          : 11

  4. A -> C -> D -> E -> F     : 12

  5. A -> C -> E -> F          : 10

 

Ответ:

1

 
Рейтинг:
 
Проголосовало: 2
Количество просмотров: 2667
 
 
 

Раздел A • Категория A2 (демонстрационный вариант-2012)

 

Комментарии

Для комментирования или зарегистрируйтесь
 
 
© 2011-2019 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?