ОГЭ по информатике: задание 9 — тренажёр

Теория по заданию 9: Подсчёт количества путей в графе

Задание 9 — схема дорог со стрелками (ориентированный граф). Нужно посчитать число различных путей из одного пункта в другой, иногда проходящих через заданный пункт.

Ключевые идеи

  • Каждой вершине приписывают число путей из начала в неё.
  • Число путей в вершину равно сумме чисел во всех вершинах, из которых в неё ведёт стрелка.
  • Путь «через пункт X» = (число путей из начала в X) × (число путей из X в конец).

Типовой алгоритм решения

  1. Начальной вершине припишите 1.
  2. Двигаясь по направлению стрелок, считайте число путей для каждой вершины как сумму входящих.
  3. Число у конечной вершины и есть ответ.

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

  • Считают вершины не по порядку (до того, как известны все входящие).
  • Игнорируют направление стрелок.
  • В задаче «через пункт» складывают вместо умножения.

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

Задание 9. В банке задач: 30. Сейчас показывается 10 задач(и) на странице.

Показать по:
Страница:

Задача 1 (легкая)

ID: 9-001
На рисунке — схема дорог, связывающих города А, Б, В, Г. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Г?
А Б В Г

Задача 2 (легкая)

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

Задача 3 (легкая)

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

Задача 4 (легкая)

ID: 9-004
На рисунке — схема дорог, связывающих города А, Б, В, Г. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Г?
А Б В Г

Задача 5 (легкая)

ID: 9-005
На рисунке — схема дорог, связывающих города А, Б, В, Г. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Г?
А Б В Г

Задача 6 (легкая)

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

Задача 7 (легкая)

ID: 9-007
На рисунке — схема дорог, связывающих населённые пункты A, B, C, D. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из населённого пункта A в населённый пункт D?
A B C D

Задача 8 (легкая)

ID: 9-008
На рисунке — схема дорог, связывающих населённые пункты A, B, C, D, E. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из населённого пункта A в населённый пункт E?
A B C D E

Задача 9 (легкая)

ID: 9-009
На рисунке — схема дорог, связывающих населённые пункты A, B, C, D. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из населённого пункта A в населённый пункт D?
A B C D

Задача 10 (легкая)

ID: 9-010
На рисунке — схема дорог, связывающих населённые пункты A, B, C, D. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из населённого пункта A в населённый пункт D?
A B C D
Показать по:
Страница: