ЕГЭОГЭЕНТ
РУҚА
ОГЭ · информатика · номер 9 · решения с ответами

Задание 9 ОГЭ по информатике: решения ФИПИ с ответами по шагам

Все задачи задания 9 из открытого банка ФИПИ с готовым ответом и началом разбора. Полное решение по шагам и официальный ключ — по ссылкам в карточке.

Задания без решений
83
решений с ответами
1
тем в номере
5
страниц списка
41ФИПИ 53c12A№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из вершины F в G ведёт один путь, поэтому количество путей из F равно 1.$$N_F = 1$$
  2. 2
    Из E можно сразу попасть в G или пройти через F.$$N_E = 1 + N_F = 2$$

Ещё 4 шага — в полном решении

Решение полностьюОтветРешать самому6 шагов в разборе
42ФИПИ 55Bc98№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Так как граф ориентированный и не содержит циклов, количество путей в каждой вершине находим слева направо: число путей в вершине равно сумме чисел путей в вершинах, из которых в неё ведут стрелки.$$N(v)=\sum_{u\to v}N(u)$$
  2. 2
    Начинаем с города А: ему соответствует один начальный путь. Далее по схеме последовательно вычисляем количества путей для всех городов.

Ещё 1 шаг — в полном решении

Решение полностьюОтветРешать самому3 шага в разборе
43ФИПИ 569918№ 9ПовышеннаяГрафы и пути

Подсчёт путей в графе

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

  1. 1
    Начинаем с города А: существует один начальный путь, поэтому число путей к А равно 1.$$N(А)=1$$
  2. 2
    Для каждой следующей вершины складываем количества путей, ведущих в неё из предыдущих вершин.

Ещё 1 шаг — в полном решении

Решение полностьюОтветРешать самому3 шага в разборе
44ФИПИ 56A882№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города А начинаются три группы путей: через города Б, В и Г.
  2. 2
    Через Б можно попасть в К напрямую или через Д: 2 пути.

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
45ФИПИ 584324№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Граф ориентированный и не содержит циклов, поэтому вершины можно рассматривать слева направо, начиная с города А.
  2. 2
    Для каждой вершины подсчитываем число путей из А: если в вершину ведут несколько стрелок, складываем числа путей до вершин, из которых они выходят.

Ещё 1 шаг — в полном решении

Решение полностьюОтветРешать самому3 шага в разборе
46ФИПИ 5AD0eF№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города А непосредственно можно попасть в города Б, В и Г.$$N_{А}=1,\quad N_{Б}=1,\quad N_{В}=1,\quad N_{Г}=1$$
  2. 2
    В город Б ведут дороги из А и В, поэтому количество путей в него равно двум.$$N_{Б}=N_{А}+N_{В}=1+1=2$$

Ещё 4 шага — в полном решении

Решение полностьюОтветРешать самому6 шагов в разборе
47ФИПИ 5B1431№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города A в города B и C ведёт по одному пути.$$N_B = 1,\quad N_C = 1$$
  2. 2
    В город D можно попасть только из B, а в город E — из B и C.$$N_D = N_B = 1,\quad N_E = N_B + N_C = 2$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
48ФИПИ 5ED954№ 9ПовышеннаяГрафы и пути

Пути между городами

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

  1. 1
    Обозначим через $N(X)$ количество путей из города А в город $X$. Для города А имеем $N(А)=1$. По схеме: $N(Б)=1$, $N(Д)=1$.
  2. 2
    В город В ведут дороги из А и Б, поэтому количество путей равно:$$N(В)=N(А)+N(Б)=1+1=2$$

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
49ФИПИ 5eeBFA№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города A можно попасть либо в B, либо в F.
  2. 2
    Пути через B: A–B–C–D, A–B–C–E–D и A–B–E–D. Всего 3 пути.

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
50ФИПИ 61E423№ 9ПовышеннаяГрафы и пути

Подсчёт путей в графе

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

  1. 1
    Обозначим через $N(X)$ число путей из города А в город $X$. Для начального города $А$ имеем $N(А)=1$.
  2. 2
    Подсчитаем число путей к вершинам первого уровня: $N(Б)=1$, $N(Д)=1$.

Ещё 5 шагов — в полном решении

Решение полностьюОтветРешать самому7 шагов в разборе
51ФИПИ 6BD9AB№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города А можно попасть в Б, В и Г непосредственно. Поэтому количество путей до этих вершин равно 1, 1 и 1 соответственно.$$N(Б)=1,\quad N(В)=1,\quad N(Г)=1$$
  2. 2
    В город В ведут дороги из А, Б и Г. Поэтому количество путей до В равно 3.$$N(В)=1+1+1=3$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
52ФИПИ 706F4C№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Обозначим через $N_X$ количество путей из А в вершину $X$. Для непосредственно достижимых из А городов получаем:$$N_{\text{Б}}=N_{\text{В}}=N_{\text{Д}}=1$$
  2. 2
    В город Г ведут дороги из А, В и Д:$$N_{\text{Г}}=1+1+1=3$$

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
53ФИПИ 741380№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Считаем количество путей из города А в каждую вершину, начиная с исходной вершины.$$N(А)=1$$
  2. 2
    В город Б ведёт один путь из А, а в город В — пути из А и Б.$$N(Б)=1,\quad N(В)=N(А)+N(Б)=1+1=2$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
54ФИПИ 7DCCC3№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    До городов Б и Г из города А существует по одному пути, а до города В ведут три пути: непосредственно из А, через Б и через Г.$$N(Б)=1,\quad N(Г)=1,\quad N(В)=1+1+1=3$$
  2. 2
    До города Д ведут пути из Б и В, а до города Е — пути из Г и В.$$N(Д)=N(Б)+N(В)=1+3=4,\quad N(Е)=N(Г)+N(В)=1+3=4$$

Ещё 1 шаг — в полном решении

Решение полностьюОтветРешать самому3 шага в разборе
55ФИПИ 82DBA4№ 9ПовышеннаяГрафы и пути

Подсчёт путей в графе

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

  1. 1
    Рассмотрим пути, начинающиеся переходом из города А в город Б.$$4$$
  2. 2
    Из города Б можно попасть в К напрямую, через В, через Д. Через В возможны два продолжения: сразу в К или через Е в К. Итого из Б в К ведут 4 пути.$$1 + 1 + 1 + 1 = 4$$

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
56ФИПИ 8D5169№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города А можно сразу попасть в Б, В и Г, поэтому количество путей до каждой из этих вершин: до Б — 1, до В — 1, до Г — 1.
  2. 2
    В город В также можно попасть через Г, поэтому всего путей до В: $1 + 1 = 2$.

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
57ФИПИ 937DB7№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города А непосредственно можно попасть в Б, В и Г, поэтому в каждую из этих вершин ведёт по одному пути.$$N_{Б}=1,\quad N_{В}=1,\quad N_{Г}=1$$
  2. 2
    В город В ведут дороги из А, Б и Г. Поэтому количество путей в В равно трём.$$N_{В}=1+N_{Б}+N_{Г}=1+1+1=3$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
58ФИПИ B0C254№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города А непосредственно ведут дороги в города Б, В и Г. Поэтому для Б и Г число путей равно 1.$$N_{Б}=1,\quad N_{Г}=1$$
  2. 2
    В город В ведут дороги из А, Б и Г. Следовательно, число путей до В равно сумме путей до этих городов.$$N_{В}=1+1+1=3$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
59ФИПИ B137FD№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города А непосредственно можно попасть в города Б, В и Г. Число путей до них: в Б — 1, в Г — 1, в В — 2 (напрямую из А и через Г).$$N_{Б}=1,\quad N_{Г}=1,\quad N_{В}=1+N_{Г}=2$$
  2. 2
    В город Д можно попасть только из Б, поэтому число путей до Д равно 1.$$N_{Д}=N_{Б}=1$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
60ФИПИ B3506E№ 9ПовышеннаяГрафы и пути

Количество путей в графе

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

  1. 1
    Из города А можно попасть непосредственно в города Б, В и Г, поэтому количество путей в них равно соответственно 1, 2 и 1: в В ведут пути из А и Б.$$N_{Б}=1,\quad N_{В}=N_{А}+N_{Б}=2,\quad N_{Г}=1$$
  2. 2
    В город И ведут дороги из В и Г, в город Д — из В, а в город Е — из Г.$$N_{И}=N_{В}+N_{Г}=3,\quad N_{Д}=N_{В}=2,\quad N_{Е}=N_{Г}=1$$

Ещё 1 шаг — в полном решении

Решение полностьюОтветРешать самому3 шага в разборе

Те же задачи без решений, с фильтрами по сложности и типу ответа, — список заданий. Другой предмет — в каталоге.