9 задание ОГЭ информатика
Количество путей в графе
1 балл ≈ 4 мин уровень П Анализ информации, представленной схемой: количество путей
Задание 9 – схема дорог между городами, по каждой дороге можно ехать только по стрелке. Нужно найти, сколько существует различных путей из города A в последний город (иногда – «проходящих через город X» или «не проходящих через X»). 1 балл, ответ – число.
Главное правило
Число путей в город = сумма чисел путей во все города, из которых в него ведёт стрелка.
У стартового города пишем 1 (один способ – «никуда не ехать»).
Алгоритм
- Поставь у A число 1.
- Найди город, в который стрелки идут только из уже посчитанных городов. Сложи их числа – запиши результат у этого города.
- Повторяй, пока не дойдёшь до конечного города.
- Число у конечного города – ответ.
Разобранный пример. Дороги: A→B, A→C, B→C, B→D, C→D, C→E, D→E. Сколько путей из A в E?
| Город | Откуда входят стрелки | Путей |
|---|---|---|
| A | старт | 1 |
| B | A | 1 |
| C | A, B | 1 + 1 = 2 |
| D | B, C | 1 + 2 = 3 |
| E | C, D | 2 + 3 = 5 |
Ответ: 5. Проверка перебором: ABCDE, ABCE, ABDE, ACDE, ACE – действительно 5.
Дополнительные условия
- Путь обязательно проходит через X: посчитай пути из A в X, затем начни заново с X (поставь у X число 1) и посчитай пути из X в конец. Перемножь.
- Путь не проходит через X: вычеркни город X и все его стрелки, затем считай как обычно (у X считай 0).
- Через X, но не через Y – совмещай оба приёма.
Ловушки
- Начал считать город, у которого не все «входящие» города уже готовы – получишь заниженное число. Считай строго по порядку.
- Пропустил стрелку на рисунке. Перед ответом пересчитай стрелки, входящие в каждый город.
- Стрелки «назад» (против общего направления) тоже бывают – смотри на наконечник, а не на расположение городов.
- Складывают пути, а не количество стрелок.
- Подписывай числа прямо у кружков на схеме, двигаясь слева направо.
- Для каждого города называй вслух: «в C входят из A и B» – так не пропустишь стрелку.
- «Через X» – умножаешь, «не через X» – обнуляешь X.
Разобранные задания 9 из открытого банка ФИПИ
Пример 1 · код ФИПИ F1E6B6
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Показать ответ и решение
Ответ: 7
Для каждого города считаем число путей из начального: оно равно сумме чисел путей у городов, из которых в него ведут стрелки. Идём по схеме слева направо.
Для конечного города получается 7.
Пример 2 · код ФИПИ 2A88cF
На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?
Показать ответ и решение
Ответ: 7
Для каждого города считаем число путей из начального: оно равно сумме чисел путей у городов, из которых в него ведут стрелки. Идём по схеме слева направо.
Для конечного города получается 7.
Пример 3 · код ФИПИ 4759eA
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
Показать ответ и решение
Ответ: 8
Для каждого города считаем число путей из начального: оно равно сумме чисел путей у городов, из которых в него ведут стрелки. Идём по схеме слева направо.
Для конечного города получается 8.
Частые вопросы о задании 9
Сколько баллов даёт задание 9 ОГЭ по информатике?
Максимум – 1 первичный балл. Норма времени на экзамене – около 4 мин. Уровень сложности – П.
Что проверяет задание 9?
Задание 9 – схема дорог между городами, по каждой дороге можно ехать только по стрелке. Нужно найти, сколько существует различных путей из города A в последний город (иногда – «проходящих через город X» или «не проходящих через X»). 1 балл, ответ – число.
Как подготовиться к заданию 9?
Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.