9 задание ОГЭ по информатике: как найти количество путей — инструкция и примеры

Экзамен по предмету информатика включает важное задание, связанное с анализом графов и подсчётом количества путей между вершинами. Чтобы успешно выполнить это задание и получить высокий балл, важно не только знать теорию, но и понимать, как правильно решать подобные задачи. 

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

В ОГЭ по информатике задание 9 делится на несколько видов:

1. Поиск количества путей без усложнения
2. Поиск количества путей с обязательной для прохождения точкой
3. Поиск количество путей с обязательной для обхода точкой (ее нужно не пройти)

Тем, кто готовится к экзамену по направлению информатика ОГЭ, важно заранее разобраться с алгоритмами, типами задач и частыми ошибками, изучить задание. 

Как решать задание 9?

1. Начальную вершину ставим равной единице

2. Если в вершину входит одна стрелка, тогда переносим значение с этой стрелки с уже известной вершины.

3. Если в вершину входит несколько стрелок, тогда суммируем значения со всех этих стрелок

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

Хочешь, чтобы эксперт разобрал именно твои задачи и ошибки? Получи бесплатную консультацию, переходи по ссылке: 

Самая главная ошибка при решении 9 задания по предмету информатика: невнимательное прочтения задания, при котором школьники не замечают, что необходимо пройти или не пройти какую-то точку! Рассмотрим классическое решение задания 9, в котором нет дополнительных условий — только схема и подсчёт маршрутов от точки А до К.

Поиск количества путей без усложнения

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

Решение: 

Начальную точку А, с которой мы начинаем движение, ставим равной 1.  Почему именно единица? Потому что таким образом мы обозначаем начало маршрута, откуда мы стартуем. Далее начинаем смотреть следующие близкие к А точки, если в пункт идет одна стрелка, то переносим значение из того пункта откуда мы идем в наш текущий пункт. 
 Если в точку входит несколько стрелок, то складываем значения со стрелок в текущую точку.

Ставим изначальную точку А = 1, далее смотрим дальнейшие точки и видим, что в точку Б ведет всего одна стрелка из точки А, поэтому мы просто переносим значения с А на Б и ставим его равным Б = 1. Аналогично делаем с точкой Г и ставим Г = 1. 

В точку В идет две стрелки из Б и из Г, поэтому точка В = Б + Г = 2, то есть она берет значения из Б и Г и складывает. 

Пункт Д = Б + В = 1 + 2 = 3, складываем количество с Б и В. В точку И будет перенос значения с пункта Д, так как в И ведет одна стрелка И = 3.

Аналогичная ситуация, как в пункте Д, в пункте  Е = В + Г = 2 + 1 = 3 и тогда сразу пункт З равен тоже 3, там переносится значение. 

Пункт Ж объединяет три пункта Д,В и Е, поэтому Ж = Д + В + Е = 3 + 2 + 3 = 8. 

И тогда финальный ответ будет получен после подсчета точки К = Ж + И + З = 8 + 3 + 3 = 14. 

Ответ: 14

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

Поиск количества путей с обязательной для прохождения точкой

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

Возьмем рисунок из прошлой задачи и подумаем, какие пути будут мешать нам пройти через нужный пункт Ж. 

При анализе картинки можно заметить, что можно пропустить нужную точку если прийти в финальную вершину через точку И или З, поэтому эти точки можно смело убирать с картинки. 

Совет: закрашивай или зачеркивай лишние пути на самой картинке, чтобы не путаться!

Если мы убираем стрелки ИК и ЗК, тогда пункты З и И вообще не имеют никакого смысла, так как из них мы никуда не пойдем, поэтому эти пункты и все пути выходы из них можно смело удалять и тогда итоговая картинка выглядит следующим образом: 

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

Начальную точку ставим равно 1. Если в точку идет одна дорога, то переносим значение с нее. Если в точку входит несколько дорог, то складываем значения со стрелок в текущую точку.

А = 1 -> Б = Г = 1

В = Б + Г = 2

Д = Б + В = 1 + 2 = 3

Е = В + Г = 2 + 1 = 3

Ж = Д + В + Е = 3 + 2 + 3 = 8

К = Ж = 8 

Ответ: 8

Многие ошибки в 9 задании ОГЭ информатика связаны с невнимательностью к условиям: ученики пропускают важные формулировки или не учитывают нужную точку в графе.

Поиск количество путей с обязательной для обхода точкой (ее нужно не пройти)

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

Продолжим изучение 9 задания с той же картинкой и подумаем, как не пройти через пункт В.

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

Совет: закрашивай или зачеркивай лишние пути на самой картинке, чтобы не путаться!

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

Начальную точку ставим равно 1. Если в точку идет одна дорога, то переносим значение с нее. 
 Если в точку входит несколько дорог, то складываем значения со стрелок в текущую точку.

А = 1 -> Б = Г = 1

В = Б + Г = 2

Д = Б = 1

Е = В = 1

Ж = Д + Е = 1 + 1 = 2

И = Д = 1

З = Е = 1

К = Ж + З + И  = 4

Ответ: 4 

Как не ошибиться на экзамене

ОГЭ по информатике проверяет не только знание алгоритмов, но и внимательность к формулировкам. Даже, на первый взгляд, несложное задание может привести к потере баллов из-за невнимательного прочтения.

Чтобы избежать ошибок:

• Читайте условие дважды. Особенно внимательно отнеситесь к фразам «проходящих через город» и «не проходящих».
• Работайте с изображением. Помечайте стрелки, вычёркивайте лишние, чтобы не запутаться.
• Следуйте алгоритму. Ставьте 1 в начальной точке, переносите или складывайте значения.
• Не забудьте пересчитать всё заново при изменении схемы. Даже одна удалённая стрелка может изменить структуру маршрутов.
• Практикуйтесь. Чем больше заданий решено — тем выше скорость и уверенность.

Узнай, как получить полезные материалы бесплатно - запишись на консультацию с экспертом по ссылке.

Решение задания 9 требует не только понимания алгоритма, но и практического опыта. Уверенность в решении приходит с регулярной работой и внимательным подходом к каждому примеру. А грамотная стратегия подготовки поможет получить высокий балл по ОГЭ и заложить основу в изучении информатики.