Информатика. ЕГЭ
Задание 3
Разбор типовых задач:
№1
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.
Задача решается преобразованием табличной модели в дерево:
Рассмотрим первую строку (столбец) таблицы. Очевидно, что из точки А мы можем попасть в точки В, С, D, F. Получим следующую схему:
Рассмотрим вторую строку (столбец) таблицы: из пункта В можно попасть в пункт А (путь АВ уже нанесен на схему и повторно рисовать его нет необходимости, т.к. это дорога «назад» и такой маршрут не будет кратчайшим). Таким образом, на схему необходимо нанести одну дорогу(из В в D, длиной 5).
Анализируя 3 строку (столбец) таблицы, добавляем на схему еще одну дорогу: из С в D длиной 2.
Анализ 4 строки (столбца) таблицы добавляет на нашу схему еще две дороги (из D в E и F), так как дороги BD, CD, AD уже присутствуют на схеме. Так как точка D на схеме нарисована 3 раза, то от каждой точки D проведем два пути: DE и DF. Получим схему
Согласно 5 строке (столбца) таблицы нанесем на схему дорогу EF:
По схеме выпишем маршруты из А в F и посчитаем их протяженность:
AF – 14
ADF – 7+8=15
ADEF – 7+5+1=13
ACDF – 4+2 +8 =14
ACDEF – 4+2+5+1 = 12
ABDF – 3+5+8 = 16
ABDEF – 3+5+5+1 = 14
Кратчайший путь равен 12.
№2
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Сколько существует таких маршрутов из А в F, которые проходят через пять и более населённых пунктов? Пункты А и F при подсчёте учитывайте. Два раза проходить через один пункт нельзя.
Строим древовидную схему аналогично №1. Отличие от предыдущего задания заключается в том, что нас не интересует длина маршрутов и на схему мы будем наносить все пункты, в которые можно попасть из данного пункта не нанесенные нами по данной ветке ранее:
А
F
В
С
D
ВВ
D
D
СВ
Е
Е
F
F
F
СВ
Е
В
F
F
F
Четыре маршрута (обозначены на схеме синим цветом) оказались тупиком, так дальнейшее движение по ним ведет к повторному посещению пунктов А или D. Выписываем маршруты, приводящие в пункт F (на схеме обозначены красным) и подсчитываем количество населенных пунктов, через которые проходит каждый маршрут:
AF – 2
ADF –3
ADEF – 4
ACDF – 4
ACDEF – 5
ABDF – 4
АBDEF – 5
Количество маршрутов, отвечающих условию задачи – 2.
№3
В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.
1)
2)
3)
4)
Анализируя таблицу по строкам (по столбикам) получаем: на схеме должны присутствовать 4 дороги: АВ(4), АD(5), BC(3), BD(6). Из четырех схем только одна схема (последняя) удовлетворяет этому условию. Ответ: 4 схема.
№4
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 |
П1 | | 45 | | 10 | | | |
П2 | 45 | | | 40 | | 55 | |
П3 | | | | | 15 | 60 | |
П4 | 10 | 40 | | | | 20 | 35 |
П5 | | | 15 | | | 55 | |
П6 | | 55 | 60 | 20 | 55 | | 45 |
П7 | | | | 35 | | 45 | |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.
Задание заключается в установлении соответствия нумерации населенных пунктов на графе и в таблице.
Проанализируем граф: согласно схеме в пункты А, Б, Д и К ведет по 2 пути, в пункт Г – 3 пути, В – 5 путей, Е - 4 пути. Сопоставляя с таблицей, получим: Г – это П2 в таблице, В – П6, Е – П4. Заменим заголовки строк и столбцов в таблице на соответствующие буквы:
| П1 | Г | П3 | Е | П5 | В | П7 |
П1 | | 45 | | 10 | | | |
Г | 45 | | | 40 | | 55 | |
П3 | | | | | 15 | 60 | |
Е | 10 | 40 | | | | 20 | 35 |
П5 | | | 15 | | | 55 | |
В | | 55 | 60 | 20 | 55 | | 45 |
П7 | | | | 35 | | 45 | |
Задачу можно считать решенной, так как чтобы ответить на вопрос достаточно посмотреть, какое число стоит на пересечении строки В и столбца Е (либо наоборот строки Е и столбца В): 20.