555 подписчиков

Информатика ОГЭ №9

31 мая 202231 мая 2022

2805

2 мин

Добрый день, сегодня попробуем разобраться с заданием №9 ОГЭ по информатике. Для этого нужно знать базовую информацию по теме “графы”. Граф — структура данных, благодаря которой видно взаимосвязи между объектами (в данном случае между населёнными пунктами). В данной задаче используется ориентированный граф. Ориентированный граф — это такой граф, который имеет лишь одно направление движения (по стрелке), идти в обратном направлении нельзя. Попробуем разобрать несколько задач с разным условием Существует несколько видов решения. Первый вариант решения - переписать все возможные пути из города А в город П, которые обязательно проходят через город Е. И потом посчитать количество данных путей. Данный способ занимает большое количество времени, долго расписывать и имеет большой шанс ошибиться. Второй вариант решения - подписывать сумму (веса) предыдущих путей. Этим способом и будем решать данный тип задания. Задача №1 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М,

Оглавление

Задача №1
Решение
Задача №2

Добрый день, сегодня попробуем разобраться с заданием №9 ОГЭ по информатике. Для этого нужно знать базовую информацию по теме “графы”. Граф — структура данных, благодаря которой видно взаимосвязи между объектами (в данном случае между населёнными пунктами). В данной задаче используется ориентированный граф.

Ориентированный граф — это такой граф, который имеет лишь одно направление движения (по стрелке), идти в обратном направлении нельзя.

Попробуем разобрать несколько задач с разным условием

Существует несколько видов решения. Первый вариант решения - переписать все возможные пути из города А в город П, которые обязательно проходят через город Е. И потом посчитать количество данных путей. Данный способ занимает большое количество времени, долго расписывать и имеет большой шанс ошибиться. Второй вариант решения - подписывать сумму (веса) предыдущих путей. Этим способом и будем решать данный тип задания.

Задача №1

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

Решение

Для начала отметим через какой населённый пункт нужно ОБЯЗАТЕЛЬНО пройти и через какие населённый пункты нам идти не нужно (т.к. они не проходят через нужный населённый пункт)

Отметили обязательное прохождение через город Е

Далее будем наносить веса для каждого населенного пункта.

Вес с входящих городов складывается (в город Е).

Вес с городов сохраняется, даже если в дальнейшем он расходится по другим населённым пунктам (из города Ж в К,Н). Далее поочерёдно суммируем веса. Сначала в город “М”, а потом в город “Л”.

После этого останется лишь просуммировать веса для города “П” и получить ответ.

Достаточно быстро получили правильный ответ — 21 (количество путей из города А в город П через населённый пункт Е). Если выписывали все возможные пути, то это заняло бы больше времени и, возможно, допустили ошибку.

Задача №2

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

Решение

Для начала опять же отметим, через какие города мы не должны проходить и зачеркнём их. Поскольку нам НЕЛЬЗЯ проходить через город “В”, то зачеркнём все пути ведущие из него (можно ещё и зачеркнуть, которые ведут в него).

Отмечаем через какие дороги НЕЛЬЗЯ проходить

Далее немного пропишем веса у населённых пунктов.

Осталось просуммировать окончательный вес в городе “К” и записать ответ.

Достаточно просто и легко получили наш ответ — 5

Понравилась статья? Хочешь разбираться в информатике, программировании и уметь работать в разных программах? Тогда ставь лайк, подпишись на канал и поделись статьей с друзьями!