ОГЭ · краткий ответ

Задание 9 ОГЭ по информатике — подсчёт количества путей в графе

Что проверяет номер, типичные ошибки, пример с решением на Python и 10 заданий с ответами под спойлером.

85заданий в банке
с ответамикак в КИМ
1 кликзадание на доске

Что проверяет задание 9 ОГЭ

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

ОГЭ, задание 985 заданий в банке ИнфДоски

Типичные ошибки

  • Считают пути «на глаз» и пропускают часть.
  • Двигаются против стрелок.
  • Складывают пути не в той вершине, из которой идёт дорога.
  • Не исключают пути через запрещённый город.

Пример с решением

Условие

Дороги (только в указанном направлении): А→Б, А→В, Б→Г, В→Г, Б→Д, Г→Д, В→Е, Г→Е, Д→К, Е→К. Сколько существует различных путей из А в К?

Решение

Пути: Б — 1, В — 1, Г = Б + В = 2, Д = Б + Г = 3, Е = В + Г = 3, К = Д + Е = 6.

from functools import lru_cache
roads = [('А', 'Б'), ('А', 'В'), ('Б', 'Г'), ('В', 'Г'), ('Б', 'Д'),
         ('Г', 'Д'), ('В', 'Е'), ('Г', 'Е'), ('Д', 'К'), ('Е', 'К')]

@lru_cache(None)
def paths(v):
    return 1 if v == 'К' else sum(paths(b) for a, b in roads if a == v)

print(paths('А'))
Код на Python 3 — его можно запустить прямо на ИнфДоске.
Ответ: 6

Задания из банка

В банке ИнфДоски 85 заданий этого номера. Ниже — 10 из них, ответ спрятан под спойлером. Кнопка «Открыть на доске» ставит задание на вашу ИнфДоску.

Задание 1 Пути в графе Открыть на доске →

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

Ответ
12
Задание 2 Пути в графе Открыть на доске →

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

Ответ
7
Задание 3 Пути в графе Открыть на доске →

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

Ответ
6
Задание 4 Пути в графе Открыть на доске →

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

Ответ
13
Задание 5 Пути в графе Открыть на доске →

На рисунке – схема дорог, связывающих города A, B, C, D, E, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город F?

Ответ
9
Задание 6 Пути в графе Открыть на доске →

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

Ответ
15
Задание 7 Пути в графе Открыть на доске →

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

Ответ
9
Задание 8 Пути в графе Открыть на доске →

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

Ответ
30
Задание 9 Пути в графе Открыть на доске →

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

Ответ
7
Задание 10 Пути в графе Открыть на доске →

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

Ответ
23
ИнфДоска

Разбирайте задание 9 ОГЭ на онлайн-доске

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

Другие задания ОГЭ