Разбор 15 задания ЕГЭ информатика

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

Объяснение заданий 15 ЕГЭ по информатике

15 тема — «Графы и поиск количества путей» — характеризуется, как задания повышенного уровня сложности, время выполнения – примерно 3 минуты, максимальный балл — 1

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

  • Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:
  • NR = NX + NY + NZ
  • где NR — это количество путей из вершины A в вершину R
  • Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути.
  • Часто задачи с графами целесообразней решать с конца.

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


ЕГЭ по информатике 2017 задание 15 ФИПИ вариант 15 (Крылов С.С., Чуркина Т.Е.):

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

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


✍ Решение:

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

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

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

Результат: 21

Видео ЕГЭ по информатике 2017, подробное решение данного 15 задания:


ЕГЭ по информатике 2017 задание 15 ФИПИ вариант 14 (Крылов С.С., Чуркина Т.Е.):

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

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


✍ Решение:

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

  • Теперь посчитаем результаты по оставшимся вершинам:
М = И + Е + К
-----
И = В + Е
  В = 1
  Е = В + Ж
     Ж = 1

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

Результат: 7

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


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

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

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


✍ Решение:

Результат: 20

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

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

    Александр

    Не сходится с ответом мое решение задания 15 из типовых тестовых заданий В.Р. Лещинер Вариант 1 у меня получается 24 а в ответе 18 почему?????

    Александр

    я не знаю как вам прислать сканир файл с моим решением.

      admin

      Здравствуйте! напишите полностью задание или подпишитесь на группу в ВК https://vk.com/programming_labs и там задайте свой вопрос

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

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

*
*


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