Первое задание в ЕГЭ по информатике является одним из самых простых заданий и наиболее часто ошибки совершаются обучающимися из-за невнимательности или спешки, поэтому давайте разберем это задание и раз и навсегда избавимся от возможных проблем при его решении!
Для начала, немного теории:
Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. Тогда можно использовать графы:
Граф – это набор вершин и связей между ними, называющихся рёбрами:
матрица и список смежности:
Связный граф – это граф, между любыми вершинами которого существует путь.
Дерево – это связный граф без циклов (замкнутых участков)
- Взвешенные графы и весовая матрица
У взвешенных графов указан «вес ребра»:
Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.
ПОИСК КРАТЧАЙШЕГО ПУТИ (ПЕРЕБОР)
В заданиях ЕГЭ этой темы чаще всего используются две информационные модели — таблицы и схемы.
Информация в таблице строится по следующим правилам: на пересечении строки и столбца находится информация, характеризующая комбинацию этой строки и столбца.
На схеме информация строится по следующему правилу: если между объектами схемы имеется связь, то она отображается линией, соединяющей названия этих объектов на схеме.
Давайте перейдем к заданиям из ЕГЭ прошлых лет
Задание:
Решение:
Для решения задачи используем построение дерева с подсчетом значений для каждой ветви (протяженности дорог).
При движении от корня дерева (А) вниз будем иметь в виду, что:
рассматривать вершины, которые уже есть в текущей «ветви», — не нужно,
если получаемое число (суммарная протяженность дорог) превышает какое-либо из найденных вариантов от A до F, то дальше эту ветвь можно не рассматривать.
В итоге получим дерево:
Ответ: 11
Давайте рассмотрим еще одну разновидность этой задачи:
Задание:
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.
Решение:
Для начала посчитаем сколько ребер у каждой вершины:
A -> 3 (В Г Д)
Б -> 1 (В)
В -> 4 (А Б Г Е)
Г -> 4 (А В Д К)
Д -> 2 (А Г)
Е -> 1 (В)
К -> 1 (Г)
Три ребра имеет только одна вершина — А, поэтому только А может соответствовать П3.
Уникальное значение количества ребер имеет также вершина Д, — два ребра. В таблице вершине Д будет соответствовать П4.
Вершины Г и В имеют по 4 ребра. Рассмотрим матрицу, в ней 4 числа соответствуют пунктам П2 и П5.
С пунктом Д пересекается только вершина Г (Г -> 4 (А В Д К)). В весовой матрице с вершиной Д пресекается П5. Значит вершина Г соответствует П5.
В П5 на пересечении с П3 находится число 6.
Ответ: 6
Все остальные вариации этой задачи являются аналоговыми и решаются по той же логике, как видно задачи действительно не являются чем-то сверх трудным, достаточно просто не торопиться и быть внимательным при решении или составлении дерева, времени на экзамене более чем достаточно, так что дерзайте! На этом у нас все, увидимся в следующих статьях!
Предыдущая статья:
Следующая статья:
#егэ #информатика #егэ по информатике #программирование