СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задания Д3 № 1009

В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не соединены автомагистралями. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 5». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом любой населенный пункт должен встречаться на маршруте не более одного раза.

 

1. 2. 3. 4.

Решение.

Вычислим максимальные длины маршрутов.

 

Схема 1. A-B-D-C (2 + 3 + 3 = 8).

Схема 2. A-B-D-C (2 + 1 + 3 = 6).

Схема 3. A-D-B-C (2 + 2 + 2 = 6).

Схема 4. A-B-С (3 + 2 = 5), A-D-C (1 + 1 = 2).

 

Максимальная протяженность маршрута не превышает 5 только на схеме 4.

 

Примечание. Необходимо найти путь максимальной протяженности в каждой схеме, который не превышает 5.

 

Ответ: 4.

Спрятать решение · ·
Сергей Гетман 24.03.2016 18:10

На схеме 1 A-D-C (2+3=5)

Никита Горохов

Да, но нас интересует длина самого длинного пути, а это A-B-D-C с длиной 8.