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

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

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

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

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

Источник

На уроке рассматривается решение 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:

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

✍ Решение:

Источник

Сегодня разберём одно из самых лёгких заданий из ЕГЭ по информатике — задание 13. Вы с похожим типом задач могли встретится на экзамене в 9 классе по информатике.

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

Задача (Стандартная)

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

Решение:

Нужно подсчитать количество путей от начальной точки А до конечной точки К.

Будем использовать специальную технику для решения 13 задания из ЕГЭ по информатике 2022

Техника:

Ставим 1 (единицу) возле начальной точки A. Далее, просматриваем ближайшие точки и анализируем, сколько входит стрелок в эти точки. В точку Б «перетекает» 1 из точки А. В точку Г тоже входит одна стрелка из точки А. Значит, тоже в эту точку «перетекает» 1 из А.

В точку В входят две стрелки. Значит, в точку В «втекает» сумма двух точек, из которых выходят эти стрелки! Получается 1 + 1 = 2.

И продолжаем в том же духе.

Число в конечной точке показывает правильный ответ!

Ответ: 17

Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)

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

Решение:

Отличие этой задачи от предыдущей заключается в том, что пути, которые будем засчитывать, обязательно должны проходить через пункт Ж. Чтобы выполнить это условие, зачеркнём стрелку из пункта Е в пункт И. Так же зачеркнём стрелку из пункта З в пункт И. По этим стрелкам ходить нельзя, т.к. если мы по ним пойдём, не будет пройден пункт Ж.

Основная техника же решения будет такой же, как и в прошлой задаче.

Ответ: 51

Продолжаем отработку 13 задания ЕГЭ по информатике 2022

Задача (Избегаемая вершина)

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

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

Решение:

Такая же задача, как и предыдущие две, только здесь, при построении путей, мы не должны проходить через точку E.

Зачеркнём те дороги, которые поведут наши пути через пункт E.

Далее, применим старый метод, который использовали ранее.

Получается ответ 27.

Ответ: 27

Рассмотрим задачу, которая была на реальном экзамене по информатике в этом году.

Задача (ЕГЭ по информатике, 2020, Москва)

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

Решение:

В этой задаче отличается вопрос от привычного нахождения количества путей. Здесь нужно найти наибольшую длину пути из начального пункта в конечный.

Возле начальной точки ставим число 0.

Смотрим сколько входит в узел стрелок. Выбираем стрелку, которая идёт из узла с наибольшим числом. При переходе по стрелочке добавляем 1.

Число, которое получится возле конечной точки и будет ответом. В этой задачке стрелок получилось 7, это и будет ответ.

Ответ: 7

Источник

ЕГЭ информатика 13 задание разбор, теория, как решать.

Поиск путей в графе, (П) — 1 балл

Е13.26 ненулевой длины, которые начинаются и заканчиваются в городе Е

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

Е13.25 из пункта А в пункт С, проходящих ровно через один из пунктов Ж и М

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

Е13.24 из города А в город Л, проходящих через город 3

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город 3? Ответ: Апробация ЕГЭ по информатике 19 февраля 2022 – задание …

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

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

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

Сколько существует различных путей из города Г в город Т, не проходящих через Л? На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ответ: Тренировочный вариант №1 от 13.09.2021 «ЕГЭ 100БАЛЛОВ»

Е13.21 Какова длина самого короткого пути из города А в город М

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

Е13.20 Какова длина самого длинного пути из города А в город М

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

Е13.19 Какова длина самого длинного пути из города А в город Л?

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

Е13.18 проходящих через пункт Г или через пункт Е, но не через оба этих пункта

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

Е13.17 различных путей пункта А в пункт Н, проходящих через пункт Е

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

Источник

За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: повышенный.
Средний процент выполнения: 60.5%
Ответом к заданию 13 по информатике может быть цифра (число) или слово.

Разбор сложных заданий в тг-канале

Задачи для практики

Задача 1

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

Решение

Построим таблицу. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину К. Затем те вершины, из которых в К ведёт прямой путь и из которых в вершину К можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:

К	З	И	Ж	Е	В	Б	Д	Г	А

Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей P_x(K) из просматриваемой вершины x в K. Если из вершины x выходит несколько путей, например, в вершины x₁, x₂, и x₃, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x₁, x₂, и x₃ в К.

То есть P_x(K) = P_x1 (K) + P_x2 (K) + P_x3 (K).

Для вершины К в таблицу заносим значение P_К(K) = 1.

Следующей идёт вершина З. Из этой вершины выходит путь только в одну вершину К. P_З(K) = P_К(K) = 1.

Из вершины И выходят два пути в вершины З и К.

P_И(K) = P_З(K) + P_К(K) = 1 + 1 = 2.

Из вершины Ж выходит путь только в одну вершину К.

P_Ж(K) = P_К(K) = 1.

Из вершины Е выходят два пути в вершины Ж и К.

P_Е(K) = P_Ж(K) + P_К(K) = 1 + 1 = 2.

Из вершины В выходит путь только в одну вершину З.

P_В(K) = P_З(K) = 1.

Из вершины Б выходят пути в вершины Е, Ж и В. Следовательно, P_Б(K) = P_Е(K) + P_Ж(K) + P_В(K) = 2 + 1 + 1 = 4.

Из вершины Д выходит путь только в одну вершину И.

P_Д(K) = P_И(K) = 2.

Из вершины Г выходят два пути в вершины И и Д.

P_Г(K) = P_Д(K) + P_И(K) = 2 + 2 = 4.

Из вершины А выходят пути в вершины Б, В, Г и Д. Следовательно, P_А(K) = P_Б(K) + P_В(K) + P_Г(K) + P_Д(K) = 4 + 1 + 4 + 2 = 11.

Получим:

К	З	И	Ж	Е	В	Б	Д	Г	А
1	1	2	1	2	1	4	2	4	11

Ответ: 11

Задача 2

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

Решение

Построим таблицу. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину Л. Затем те вершины, из которых в Л ведёт прямой путь и из которых в вершину Л можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:

Л	К	Ж	Е	И	Д	Г	В	Б	А

Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px(Л) из просматриваемой вершины x в Л, не проходящих через пункт Ж. Если из вершины x выходит несколько путей, например, в вершины x₁, x₂, и x₃, то количество путей, ведущих из этой вершины в Л, не проходящих через пункт Ж, будет равно сумме путей, ведущих из x₁, x₂, и x₃ в Л.

То есть P_x(Л) = P_x1(Л) + P_x2 (Л) + P_x3(Л).

Для вершины Л в таблицу заносим значение P_Л(Л) = 1.

Следующей идёт вершина К. Из этой вершины выходит путь только в одну вершину Л. P_К(Л) = P_Л(Л) = 1.

Следующей в таблице идёт вершина Ж. Так как мы ищем пути, не проходящие через эту вершину, то P_Ж(Л) = 0.

Из вершины Е выходят два пути в вершины Ж и К.

P_Е(Л) = P_К(Л) + P_Ж(Л) = 1 + 0 = 1.

Из вершины И выходят два пути в вершины Л и Ж.

P_И(Л) = P_Ж(Л) + P_Л(Л) = 0 + 1 = 1.

Из вершины Д выходит путь только в одну вершину И.

P_Д(Л) = P_И(Л) = 1.

Из вершины Г выходит путь только в вершину Е. P_Г(Л) = P_Е(Л) = 1.

Из вершины В выходят пути в вершины Д, Ж, Е и Г. Следовательно, P_В(Л) = P_Д(Л) + P_Ж(Л) + P_Е(Л) + P_Г(Л) = 1 + 0 + 1 + 1 = 3.

Из вершины Б выходят два пути в вершины Д и В.

P_Б(Л) = P_Д(Л) + P_В(Л) = 1 + 3 = 4.

Из вершины А выходят два пути в вершины Б и Г.

P_А(Л) = P_Б(Л) + P_Г(Л) = 4 + 1 = 5.

Получим:

Л	К	Ж	Е	И	Д	Г	В	Б	А
1	1	0	1	1	1	1	3	4	5

Ответ: 5

Задача 3

Решение

Построим граф, соответствующий данной схеме дорог. На графе будем для каждого города отмечать все возможные перемещения в города, связанные с ним исходящими дорогами.

Согласно условию задачи, требуется определить количество путей, проходящих через город В.

По графу определяем, что существует всего 10 различных путей, проходящих через город В.

Ответ: 10

Задача 4

Решение

К	И	Е	З	Ж	Б	В	Г	Д	А

То есть P_x(K) = P_x1(K) + P_x2(K) + P_x3(K).

Например, из вершины Ж выходят пути в вершины Е, З и К. Следовательно, P_Ж(K) = P_Е(K) + P_З(K) + P_К(K) = 1 + 2 + 1 = 4. Получим:

К	И	Е	З	Ж	Б	В	Г	Д	А
1	1	1	2	4	1	6	6	7	‘20

Ответ: 20

Задача 5

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

Решение

Заметим, что количество путей из города А в город О, проходящих через город В равно произведению количества путей из города А в город В на количество путей из города В в город О. Разобъём заданный граф на два: один из которых будет содержать только города и соответствующие дороги, ведущие из А в В, а другой — только города и соответствующие дороги из В в О.

Построим таблицу, соответствующую каждой из полученных схем. В первую строку таблицы запишем наименование всех вершин в следующем порядке.

Для первой схемы сначала запишем вершину В. Затем те вершины, из которых в В ведёт прямой путь и из которых в вершину В можно попасть только через уже просмотренные вершины. Получим:

Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей P_x (B) из просматриваемой вершины x в B. Если из вершины x выходит несколько путей, например, в вершины x₁, x₂, и x₃, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x₁, x₂, и x₃ в К.

То есть P_x (B) = P_x1 (B) + P_x2 (B) + P_x3 (B). Получим:

Количество путей из А в В равно 3.

Для определения количества путей из города В в О аналогично построим таблицу, соответствующую второй схеме.

О	Н	М	З	И	Л	К	Д	Ж	Е	В
1	1	1	3	3	3	6	9	9	18	36

Количество путей из В в О равно 36.

Следовательно, количество путей из города А в город О, проходящих через город В, равно 3 · 36 = 108.

Ответ: 108

Задача 6

Решение

Построим таблицу, соответствующую заданной схеме. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину О. Затем те вершины, из которых в О ведёт прямой путь и из которых в вершину О можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:

Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей P_x (O) из просматриваемой вершины x в O. Если из вершины x выходит несколько путей, например, в вершины x₁, x₂, и x₃, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x₁, x₂, и x₃ в К.

То есть P_x (O) = P_x1 (O) + P_x2 (O) + P_x3 (O). Получим:

О	Н	М	З	И	Л	К	Д	Ж	Е	В	Б	Г	А
1	1	1	3	3	3	6	9	9	18	36	45	54	135

Ответ: 135

Задача 7

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

Задача 8

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

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

Задача 9

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

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

Задача 10

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

Задача 11

Задача 12

Задача 13

Задача 14

Задача 15

Задача 16

Задача 17

Задача 18

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

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

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

Е13.26 ненулевой длины, которые начинаются и заканчиваются в городе Е

Е13.25 из пункта А в пункт С, проходящих ровно через один из пунктов Ж и М

Е13.24 из города А в город Л, проходящих через город 3

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

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

Е13.21 Какова длина самого короткого пути из города А в город М

Е13.20 Какова длина самого длинного пути из города А в город М

Е13.19 Какова длина самого длинного пути из города А в город Л?

Е13.18 проходящих через пункт Г или через пункт Е, но не через оба этих пункта

Е13.17 различных путей пункта А в пункт Н, проходящих через пункт Е

Задачи для практики

Задача 1

Решение

Задача 2

Решение

Задача 3

Решение

Задача 4

Решение

Задача 5

Решение

Задача 6

Решение

Задача 7

Задача 8

Задача 9

Задача 10

Задача 11

Задача 12

Задача 13

Задача 14

Задача 15

Задача 16

Задача 17

Задача 18

Задача 19

Задача 20

Рекомендуемые курсы подготовки