Информатика егэ как найти путь

Содержание:

• Объяснение заданий 1 ЕГЭ по информатике
  • Структурирование информации и информационные модели
  • Поиск кратчайшего пути (перебор)
• Решение заданий 1 ЕГЭ по информатике

1-я тема характеризуется, как:
— задания базового уровня сложности,
— требуется использование специализированного программного обеспечения — нет,
— время выполнения – примерно 3 минуты,
— максимальный балл — 1

  
Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)

Уровни в дереве

Граф, отображающий дороги между поселками

Связный граф

Дерево — связный граф без циклов

Весовая матрица

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

1_3: Решение 1 задания ЕГЭ по информатике:

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

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

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

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



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

Результат: 11

1_4: Решение 1 задания ЕГЭ по информатике:

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

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

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



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

Результат: 12

1_5: Решение 1 задания ЕГЭ по информатике:

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

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

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

• Для решения будем использовать дерево:



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

Результат: 6

1_2:

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

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

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

• Посчитаем сколько ребер у каждой вершины:

A -> 3 (В Г Д)
Б -> 1 (В)
В -> 4 (А Б Г Е)
Г -> 4 (А В Д К)
Д -> 2 (А Г)
Е -> 1 (В)
К -> 1 (Г)

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

Результат: 6

1_1:

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

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

• Рассмотрим граф и посчитаем количество ребер из каждой вершины:

А - > 2 ребра (Г, В)
В - > 4 ребра (А, Г, К, Д)
Г - > 4 ребра (А, В, К, Д)
Б - > 2 ребра (Г, К)
К - > 5 ребер (Б, Г, В, Д, Е)
Е - > 2 ребра (К, Д)
Д - > 3 ребра (В, К, Е)

• Мы выделили вершины, с уникальным числом ребер: 3 ребра соответствует только вершине Д, а 5 ребер соответствует только вершине К.
• Рассмотрим таблицу и найдем те строки или столбцы, в которых 5 значений и 3 значения: Это П2 и П4.
• Получаем П2 соответствует Д, а П4 соответствует К. На пересечении находится цифра 20.

Результат: 20

1_6: Разбор 1 задания ЕГЭ:

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

1 2 3 4 5 6 7 8 1 * * * 2 * * * 3 * * 4 * * * * * * 5 * * * 6 * * * 7 * * * 8 * * *

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

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

• Для начала найдем уникальные вершины — у которых уникальное число ребер: это 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. Поскольку не имеет значения, какой именно цифре должна соответствовать та или иная вершина, то в ответе просто запишем эти цифры в порядке возрастания.

Результат: 56