Дана схема городов и дорог, по каждой из которых можно ехать только по стрелке: нужно посчитать, сколько разных путей ведёт из одного города в другой. Часть 1, повышенный уровень, ответ — число в бланке № 1, 1 балл.
Часть
1
Ответ
число в бланке № 1
Баллы
1 балл
Проверяет
умение анализировать информацию, представленную в виде схемы
Сколько времени закладывать
около 4 минут по спецификации ФИПИ
Какие бывают подтипы
Все пути — Посчитать все различные пути по стрелкам из начального города в конечный.
Через указанный город — Учитываются только пути, которые проходят через заданный город.
Минуя город — Пути, которые заходят в запрещённый город, не считаются.
Через один из двух городов — Пути через первый или второй город; пути сразу через оба нельзя посчитать дважды.
Пример с полным разбором
Условие. На схеме — дороги между городами A, B, C, D, E, F; по каждой дороге можно ехать только в направлении стрелки. Сколько существует различных путей из города A в город F?
Припишем каждому городу число путей, которыми в него можно попасть из A. У самого A это 1.
В B ведёт только стрелка из A — 1 путь. В C ведут стрелки из A и из B: 1+1=2.
В D ведут стрелки из B и C: 1+2=3. В E — из C и D: 2+3=5.
В F ведут стрелки из D и E: 3+5=8.
Ответ: 8
Частые ошибки
Проходят по дороге против стрелки.
Считают город раньше, чем посчитаны все города, из которых в него ведут стрелки.
В задаче «минуя город» убирают сам город, но оставляют его стрелки.
В задаче «через город» складывают число путей до него и после него, а не умножают.
В задаче «через один из двух городов» дважды считают пути через оба.
Что нужно знать для задания 9
Оглавление курса «ОГЭ по информатике» под это задание. Содержание открывается после оплаты.
Один. Уровень у задания повышенный, но оценивается оно так же, как остальные задания части 1.
Нужно ли выписывать все пути?
Нет, в ответ идёт только их число. На большой схеме путей десятки, и при выписывании легко пропустить один, поэтому удобнее считать по городам, как в примере.