Информатика ЕГЭ 3 задание разбор

3-е задание: «Структурирование информации и поиск кратчайшего пути»
Уровень сложности — базовый,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.

Решение 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.

Подобные задания для тренировки

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

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

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

Результат: 11

📹 Видео


Решение 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 при условии, что передвигаться можно только по указанным в таблице дорогам.

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

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

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

Результат: 12


Решение 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 — Алгебра логики

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

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

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

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

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

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

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

Подобные задания для тренировки

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

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

Результат: 6

📹 Видео


ЕГЭ по информатике 2017, задание из сборника Ушакова Д.М, 1 вариант:

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

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

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населенных пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова длина дороги из пункта Д в пункт К. В ответе запишите целое число — так, как оно указано в таблице.

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

  • Рассмотрим граф и посчитаем количество ребер из каждой вершины:
  • А - > 2 ребра (Г, В)
    В - > 4 ребра (А, Г, К, Д)
    Г - > 4 ребра (А, В, К, Д)
    Б - > 2 ребра (Г, К)
    К - > 5 ребер (Б, Г, В, Д, Е)
    Е - > 2 ребра (К, Д)
    Д - > 3 ребра (В, К, Е)
    
  • Мы выделили вершины, с уникальным числом ребер: 3 ребра соответствует только вершине Д, а 5 ребер соответствует только вершине К.
  • Рассмотрим таблицу и найдем те строки или столбцы, в которых 5 значений и 3 значения: Это П2 и П4.
  • Получаем П2 соответствует Д, а П4 соответствует К. На пересечении находится цифра 20.

Результат: 20

📹 Видео


Разбор 3 задания ЕГЭ вариант № 1, 2019 Информатика и ИКТ Типовые экзаменационные варианты (10 вариантов), С.С. Крылов, Т.Е. Чуркина:

На рисунке изображена схема дорог Н-ского района, в таблице звездочкой обозначено наличие дороги из одного населенного пункта в другой, отсутствие звездочки означает, что такой дороги нет. Каждому населенному пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер.

разбор 3 задания Крылов 2019
1 2 3 4 5 6 7 8
1 * * *
2 * * *
3 * *
4 * * * * * *
5 * * *
6 * * *
7 * * *
8 * * *

Определите, какие номера населенных пунктов в таблице могут соответствовать населенным пунктам D и E на схеме? В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Подобные задания для тренировки

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

  • Для начала найдем уникальные вершины — у которых уникальное число ребер: это A (2 ребра) и H (6 ребер). В таблице им соответствуют номера 3 и 4:
  • 1 2 A H 5 6 7 8
    1 * * *
    2 * * *
    A * *
    H * * * * * *
    5 * * *
    6 * * *
    7 * * *
    8 * * *
  • По схеме находим, что смежными вершинами для A являются B и G. В таблице определяем соответствующие им цифры — 1 и 2. Поскольку по заданию они нас не интересуют, обозначим их вместе:
  • B,G B,G A H 5 6 7 8
    B,G * * *
    B,G * * *
    A * *
    H * * * * * *
    5 * * *
    6 * * *
    7 * * *
    8 * * *
  • У обеих вершин B и G смежными являются уже известные A и H и, кроме того, вершины F и C. По первому столбцу или первой строке находим, что F или C будет соответствовать цифра 7, а по второй строке — цифра 8. Обозначим их в таблице:
  • B,G B,G A H 5 6 F,C F,C
    B,G * * *
    B,G * * *
    A * *
    H * * * * * *
    5 * * *
    6 * * *
    F,C * * *
    F,C * * *
  • В результате получаем, что искомым вершинам — D и E — соответствуют цифры 5 и 6. Поскольку не имеет значения, какой именно цифре должна соответствовать та или иная вершина, то в ответе просто запишем эти цифры в порядке возрастания.

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

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