Задание 3 ЕГЭ по информатике 2018

Задание 3. Структурирование информации и поиск кратчайшего пути: Демонстрационный вариант ЕГЭ по информатике 2018; государственный выпускной экзамен 2018; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2018

*** КАНАЛ ЮТЬЮБ ***
 
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 3
 

3 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

демоверсия егэ 2018 информатика задание 3 егэ по информатике 2017

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.

📹 Видеоразбор

✍ Показать решение:

  • Посчитаем сколько ребер у каждой вершины:
  • A -> 3 (В Г Д)
    Б -> 1 (В)
    В -> 4 (А Б Г Е)
    Г -> 4 (А В Д К)
    Д -> 2 (А Г)
    Е -> 1 (В)
    К -> 1 (Г)
    
  • Три ребра имеет только одна вершина — А, поэтому только А может соответствовать П3.
  • Уникальное значение количества ребер имеет также вершина Д, — два ребра. В таблице вершине Д будет соответствовать П4.
  • Вершины Г и В имеют по 4 ребра. Рассмотрим матрицу, в ней 4 числа соответствуют пунктам П2 и П5.
  • С пунктом Д пересекается только вершина Г (Г -> 4 (А В Д К)). В весовой матрице с вершиной Д пресекается П5. Значит вершина Г соответствует П5.
  • В П5 на пересечении с П3 находится число 6.

Результат: 6

Решение 3 задания ЕГЭ по информатике (11 вариант ГВЭ по информатике 2018 года):

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

A B C D E F
A 3 7 6
B 3 4 4
C 7 5 9
D 4 5 5
E 6 4 8
F 9 5 8

Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.

✍ Показать решение:

  • Решим задание при помощи построения дерева, вершиной которого является отправной пункт — A. На ребрах дерева будем записывать числа — результат протяженности пути до конкретной вершины.
  • 11 вариант ГВЭ по информатике 2018

  • Кратчайший путь: A -> B -> D -> F = 12

Результат: 12

Решение 3 задания ЕГЭ по информатике (контрольный вариант № 1 экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков):

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

A B C D E F
A 7 3
B 7 2 4 1
C 3 2 7 5 9
D 4 7 2 3
E 1 5 2 7
F 9 3 7

Определите длину кратчайшего пути между пунктами A и F.

📹 Видеоразбор

✍ Показать решение:

  • Для решения задачи используем построение дерева с подсчетом значений для каждой ветви (протяженности дорог).
  • При движении от корня дерева (А) вниз будем иметь в виду, что:
  • рассматривать вершины, которые уже есть в текущей «ветви», — не нужно,
  • если получаемое число (суммарная протяженность дорог) превышает какое-либо из найденных вариантов от A до F, то дальше эту ветвь можно не рассматривать.
  • В итоге получим дерево:
  • решение 3 задания егэ, дерево

  • Самый короткий путь: A -> C -> B -> E -> D -> F = 11

Результат: 11

Решение 2* задания ЕГЭ по информатике 2018, вариант 10 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», С.С. Крылов, Т.Е. Чуркина):

Между населенными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяженность каждой дороги (отсутствие числа в таблице означает, что прямой дороги между пунктами нет).

A B C D E F Z
A 3 5 14
B 2 8
C 2 7
D 1 4 4
E 1 5
F 12 1 9
Z

Сколько существует таких маршрутов из A в Z, которые проходят через пять и более населенных пунктов? Пункты A и Z при подсчете учитывайте. Два раза проходить через один пункт нельзя.

* в новых учебниках задания 2 и 3 поменяли местами: теперь 2 — Поиск кратчайшего пути, а 3 — Алгебра логики

✍ Показать решение:

  • Для решения будем использовать дерево:
  • егэ информатика крылов чуркина решение 2 задания 2018

  • Розовым отмечены неподходящие маршруты, а голубым — подходящие.
  • Заметим, что после 4-го уровня сверху, все варианты будут подходить.

Результат: 6

ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 3

Поделитесь уроком с коллегами и друзьями:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*


Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить