Егэ графы задачи с решениями - Помощь в подготовке к экзаменам и поступлению

Пройти тестирование по 10 заданиям
Пройти тестирование по всем заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

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

	П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

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

Источник: Демонстрационная версия ЕГЭ—2016 по информатике.

	П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

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

	П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

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

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

	П1	П2	П3	П4	П5	П6	П7
П1		40		15
П2	40			35		50
П3					10	65	8
П4	15	35				22	33
П5			10			50
П6		50	65	22	50		40
П7			8	33		40

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

	П1	П2	П3	П4	П5	П6	П7
П1		40		15
П2	40			35		48
П3					10	65	11
П4	15	35				22	33
П5			10			50
П6		48	65	22	50		40
П7			11	33		40

Пройти тестирование по этим заданиям

Источник

На уроке рассматривается решение 13 задания ЕГЭ по информатике

Содержание:

Объяснение заданий 13 ЕГЭ по информатике
- Графы. Поиск количества путей
Решение заданий 13 ЕГЭ по информатике

13-е задание: «Информационные модели»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 3 минуты.

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

До ЕГЭ 2021 года — это было задание № 15 и № _ ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«Игнорирование указаний в условии задания, что путь должен включать (или не включать) заданные промежуточные вершины»

ФГБНУ «Федеральный институт педагогических измерений»

Графы. Поиск количества путей

Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:

N_R = N_X + N_Y + N_Z

где N_R — это количество путей из вершины A в вершину R
Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути.
Часто задачи с графами целесообразней решать с конца.

Решение заданий 13 ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube:

Задание демонстрационного варианта 2022 года ФИПИ

13_1:

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?

✍ Решение:

Удалим ребра, которые проходят «мимо» вершины Г или до которых от пункта А можно дойти, минуя вершину Г:

1_1

Вершина В удалена, т.к. возможны только следующие траектории движения через этот пункт (которые НЕ проходят через пункт Г):
1. А — Б — В — И — М
2. А — Б — В — Е — И — М
3. А — Б — В — Е — М
4. А — Б — В — Е — К — М
Теперь посчитаем результаты по оставшимся вершинам:

М = И + Е + К 
-----
 И = Е 
   Е = Г + Ж 
    Г = Б + А + Д = 1 + 1 + 1 = 3 
    Ж = Г = 3
 К = Е + Ж

Теперь возвращаемся, подставляя найденные значения: ↑
   Е = Г + Ж = 3 + 3 = 6 
    Ж = Г = 3
 И = Е = 6 (получили из последующих шагов)
 К = Е + Ж = 6 + 3 = 9       
М = И + Е + К = 6 + 6 + 9 = 21

Результат: 21

Видео ЕГЭ по информатике (аналитическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

13_2:

Сколько существует различных путей, ведущих из города А в город М и не проходящих через город Г?

✍ Решение:

Удалим ребра, которые проходят через вершину Г:

Теперь посчитаем результаты по оставшимся вершинам:

М = И + Е + К
-----
И = В + Е
  В = 1
  Е = В + Ж
     Ж = 1

Теперь возвращаемся, подставляя найденные значения: ↑
  Е = В + Ж = 1 + 1 = 2
И = В + Е = 1 + 2 = 3 
К = Е = 2 
М = И + Е + К = 3 + 2 + 2 = 7

Результат: 7

Подробное решение данного 13 задания в видеоуроке:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

13 задание. Демоверсия ЕГЭ 2018 информатика:

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город М, проходящих через город Ж?

✍ Решение:

Результат: 20

Подробное решение 13 задания демоверсии ЕГЭ 2018 года смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

13_4:

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город М?
Длиной пути считать количество дорог, составляющих этот путь.

✍ Решение:

Источник

Использование теории графов для решения заданий ЕГЭ

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

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

Решение:
В этом задании исходные данные представлены в виде таблицы, которую можно рассматривать как матрицу неориентированного взвешенного графа. Вершинами данного графа являются населенные пункты A,B,C,D,E,F. Элементы данной матрицы показывают, какие населенные пункты связаны дорогами и какова их длина.
Для более наглядного представления изобразим данные таблицы в виде графа. Для этого в произвольном порядке изображаем вершины, затем соединяем их ребрами и указываем вес каждого ребра. Нам надо указать длину кратчайшего пути из пункта А в пункт F. Нарисуем этот путь с конца.

Сначала изобразим конечный пункт F. В этот пункт можно попасть только из пункта Е. Соединяем пункты Е и F дугой и указываем вес этой дуги. Он равен двум, то есть расстоянию между пунктами Е и F. Соответственно по графу можно увидеть, что в пункт Е можно попасть из пунктов B, C и D. В пункт В можно попасть из А. В пункт С – из В и А. В пункт D – из С. В пункт В попадаем из А. В пункт С – из В и А. И в пункт В из А.

Данную схему можно рассматривать как ориентированный взвешенный граф, который наглядно показывает, что есть 5 путей из пункта А в пункт F. Подсчитываем длину каждого пути
1 путь: 2+7+2=11;
2 путь: 2+1+4+2=9;
3 путь: 4+4+2=10;
4 путь2+1+3+3+2=11;
5 путь: 4+3+3+2=12.
Так как нам надо определить длину кратчайшего пути, то выбираем второй путь, длина которого равна 9. Данный ответ находится под цифрой 1. Поэтому в ответе надо поставить крестик в клеточке, соответствующей первому ответу.

2. У исполнителя Утроитель две команды, которым присвоены номера
1. Прибавь 1;
2. Умножь на 3.
Запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд.
Решение:
Для решения данного задания используем метод от обратного, то есть будем преобразовывать число 22 в 1. Соответственно команды исполнителя заменим командами антагонистами, то есть команду «Прибавь 1» заменим командой «Вычти 1», а «Умножь на 3» заменим командой «Раздели на 3». Ход выполнения команд можно изобразить в виде дерева, каждая вершина которого имеет две ветки, соответствующие командам 1 и 2. Корнем этого дерева является число 22. Это дерево будет иметь 5 ярусов, так как программа должна содержать не более 5 команд. Но здесь нужно учесть один момент. Если число делится на 3, то вершина будет иметь 2 потомка, а если нет, то одного (то есть делить на 3 мы не можем, а можем только вычитать 1). Получаем следующее дерево.

Инвертируем теперь команды и преобразуем число 1 в 22.
1+1*3+1*3+1=22.
Учитывая номера команд, записываем программу решения данной задачи в виде последовательности соответствующих команд. Ответ: 12121

Решение: (1 способ)
Условие данного задания представлено в виде ориентированного графа, вершинами которого являются названия городов, а дороги, соединяющие эти города, являются дугами графа. Для того, чтобы решить данную задачу, построим еще один ориентированный граф, но с учетом того, по каким дорогам можно будет попасть в пункт Л.

По графу легко подсчитать количество дорог, ведущих из города А в город Л.

3.У Исполнителя Кузнечик 2 команды:
1. Прибавь 3;
2. Вычти 2.
Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд.
Решение:
Оформим решение данной задачи в виде дерева, вершинами которого будут являться числа, соответствующие промежуточным значениям. Данное дерево будет иметь корень, равный 1 и 5 ярусов, так как у нас должно быть ровно 5 команд.

4. У исполнителя Устроитель две команды, которым присвоены номера:
1. Прибавь 1;
2. Умножь на 3.
Программа для Устроителя – это последовательность команд.
Сколько есть программ, которые преобразуют 1 в число 29?

При решении данной задачи следует учитывать, что если число больше 9, то умножать на 3 мы не можем, так как получится число, большее 29, следовательно, вершины с числами большими 9 будут иметь только одну ветвь, соответствующую команде +1.

5.Даны три кучи камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой-нибудь куче, или добавить по 2 камня в каждую из всех трех куч. Выигрывает тот, после чьего хода в какой-нибудь куче становится больше или равно 15 камней или во всех трех кучах суммарно становится больше либо равно 25 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок?
Решение: В разумной партии каждый игрок должен стараться следовать общему правилу – всегда оставлять противнику проигрышную позицию. В ходе решения задач можно заметить, что в одной партии в Камешки только один из игроков может следовать этому правилу – тот, кто первым может занять выигрышную позицию (имеет выигрышную стратегию). Если он будет ей следовать, а, значит, делать только разумные ходы и оставлять противнику только проигрышные позиции, то выиграет при любой игре противника. Если начальная позиция выигрышная, то выигрышную стратегию имеет Первый, если проигрышная – Второй.
Изобразим решение данной задачи в виде графа.

Ответ: при правильной стратегии игры выигрывает первый игрок. При этом первый его ход должен быть 2, 3, 4 4, 5, 6.

Литература:
ФИПИ (открытый банк данных)
Материалы демонстрационных вариантов ЕГЭ по информатике 2016, 2015 года
Материалы диагностической работы 2015 года.

Источник

	П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

	П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

	П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

	П1	П2	П3	П4	П5	П6	П7
П1		40		15
П2	40			35		50
П3					10	65	8
П4	15	35				22	33
П5			10			50
П6		50	65	22	50		40
П7			8	33		40

	П1	П2	П3	П4	П5	П6	П7
П1		40		15
П2	40			35		48
П3					10	65	11
П4	15	35				22	33
П5			10			50
П6		48	65	22	50		40
П7			11	33		40

	П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

	П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

	П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

	П1	П2	П3	П4	П5	П6	П7
П1		40		15
П2	40			35		50
П3					10	65	8
П4	15	35				22	33
П5			10			50
П6		50	65	22	50		40
П7			8	33		40

	П1	П2	П3	П4	П5	П6	П7
П1		40		15
П2	40			35		48
П3					10	65	11
П4	15	35				22	33
П5			10			50
П6		48	65	22	50		40
П7			11	33		40

Графы. Поиск количества путей

Решение заданий 13 ЕГЭ по информатике

Новое и интересное на сайте:

	П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

	П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

	П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

	П1	П2	П3	П4	П5	П6	П7
П1		40		15
П2	40			35		50
П3					10	65	8
П4	15	35				22	33
П5			10			50
П6		50	65	22	50		40
П7			8	33		40

	П1	П2	П3	П4	П5	П6	П7
П1		40		15
П2	40			35		48
П3					10	65	11
П4	15	35				22	33
П5			10			50
П6		48	65	22	50		40
П7			11	33		40