Дана схема городов и дорог, по каждой из которых можно ехать только по стрелке: нужно посчитать, сколько разных путей ведёт из одного города в другой. Часть 1, повышенный уровень, ответ — число в бланке № 1, 1 балл.
| Часть | 1 |
|---|---|
| Ответ | число в бланке № 1 |
| Баллы | 1 балл |
| Проверяет | умение анализировать информацию, представленную в виде схемы |
| Сколько времени закладывать | около 4 минут по спецификации ФИПИ |
Условие. На схеме — дороги между городами A, B, C, D, E, F; по каждой дороге можно ехать только в направлении стрелки. Сколько существует различных путей из города A в город F?
Ответ: 8
Условие.
Дана схема дорог, соединяющих города А, Б, В, Г, Д, Е, Ж, З, И (дороги перечислены списком ниже). По каждой дороге можно двигаться только в одном направлении (направление показано стрелкой «→» в списке).
Список рёбер:
Сколько различных путей ведёт из города А в город И?
Решение.
Идём по вершинам в порядке от А до И и считаем, сколькими способами можно дойти до каждой.
В вершину А есть один путь — «никуда не идти». Дальше для каждой вершины складываем числа путей всех её «предков».
| Вершина | Путей до неё |
|---|---|
| А | 1 |
| Б | 1 |
| В | 0 |
| Г | 1 |
| Д | 0 |
| Е | 1 |
| Ж | 2 |
| З | 2 |
| И | 5 |
Ответ — число в строке И: 5.
Ответ: 5
Условие.
Дана схема дорог, соединяющих города А, Б, В, Г, Д, Е, Ж, З, И, К (дороги перечислены списком ниже). По каждой дороге можно двигаться только в одном направлении (направление показано стрелкой «→» в списке).
Список рёбер:
Сколько различных путей ведёт из города А в город К, проходящих через город З?
Решение.
Идём по вершинам в порядке от А до К и считаем, сколькими способами можно дойти до каждой.
В вершину А есть один путь — «никуда не идти». Дальше для каждой вершины складываем числа путей всех её «предков».
| Вершина | Путей до неё |
|---|---|
| А | 1 |
| Б | 0 |
| В | 0 |
| Г | 1 |
| Д | 1 |
| Е | 3 |
| Ж | 1 |
| З | 5 |
| И | 6 |
| К | 11 |
Через З: путей до З — 5, путей из З до К — 2. Произведение: 10.
Ответ: 10
Условие.
Дана схема дорог, соединяющих города А, Б, В, Г, Д, Е, Ж, З, И, К (дороги перечислены списком ниже). По каждой дороге можно двигаться только в одном направлении (направление показано стрелкой «→» в списке).
Список рёбер:
Сколько различных путей ведёт из города А в город К, не проходящих через город Е?
Решение.
Идём по вершинам в порядке от А до К и считаем, сколькими способами можно дойти до каждой.
В вершину А есть один путь — «никуда не идти». Дальше для каждой вершины складываем числа путей всех её «предков».
| Вершина | Путей до неё |
|---|---|
| А | 1 |
| Б | 1 |
| В | 1 |
| Г | 1 |
| Д | 0 |
| Е | 0 |
| Ж | 1 |
| З | 3 |
| И | 1 |
| К | 3 |
В таблице учтены только маршруты, не проходящие через Е.
Ответ — 3.
Ответ: 3
Оглавление курса «ОГЭ по информатике» под это задание. Содержание открывается после оплаты.