Информатика ОГЭ — решения заданий ФИПИ с ответами

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

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

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

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

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

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

1. 1
   В город Б ведёт один путь из А, поэтому число путей в Б равно 1.
2. 2
   В город В ведут пути из А и Б: 1 + 1 = 2.

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

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

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

1. 1
   Из города А есть один путь в город Б и один путь в город Г.$$N(А)=1$$
2. 2
   В город Б ведут пути из городов А и Г, а в город В — путь из города Г.$$N(Б)=N(А)+N(Г)=2, N(В)=N(Г)=1$$

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

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

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

1. 1
   В город A можно попасть одним способом — начав путь в городе A.$$N_A=1$$
2. 2
   В город B ведёт одна дорога из A, поэтому количество путей равно одному.$$N_B=1$$

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

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

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

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

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

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

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

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

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

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

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

1. 1
   Из города A можно попасть в B или F.
2. 2
   Из B в D существует только путь B → C → D, то есть 1 путь.

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

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

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

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

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

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

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

1. 1
   Последовательно вычислим количество путей из города А в каждую вершину графа.$$N_{Б}=1,\quad N_{В}=N_{А}+N_{Б}=2,\quad N_{Г}=N_{А}+N_{В}=3,\quad N_{Д}=1$$
2. 2
   Для следующих вершин получаем:$$N_{Е}=N_{Б}+N_{В}=3,\quad N_{Ж}=N_{Г}+N_{Д}=4,\quad N_{И}=N_{Е}=3$$

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

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

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

1. 1
   Начинаем с города А: число путей в него считаем равным 1. Последовательно подсчитываем пути в остальные вершины по стрелкам.$$N(А)=1$$
2. 2
   Для вершин первого участка графа получаем:$$N(Б)=1,\quad N(В)=N(А)+N(Б)=2,\quad N(Д)=1$$

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

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

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

1. 1
   В город A ведёт начальный путь, поэтому считаем количество путей из A к каждой вершине.$$N_A = 1$$
2. 2
   В город B ведёт один путь из A, а в город C — один путь из A.$$N_B = 1,\quad N_C = 1$$

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

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

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

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

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

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

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

1. 1
   Считаем начальную вершину A источником: в неё ведёт один начальный путь, поэтому $N_A=1$.$$N_A=1$$
2. 2
   В вершины B, C и D ведут пути непосредственно из A, поэтому $N_B=N_C=N_D=1$.

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

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

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

1. 1
   Перечислим пути, начинающиеся с перехода A → B: A–B–E–G, A–B–G, A–B–C–G и A–B–C–D–F–G. Всего 4 пути.$$4$$
2. 2
   Пути, начинающиеся с перехода A → C: A–C–G и A–C–D–F–G. Всего 2 пути.$$2$$

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

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

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

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

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

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

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

1. 1
   Из города А начинаются пути через города Б, В и Г. Перечислим все маршруты, которые заканчиваются в городе К.
2. 2
   После учёта направлений стрелок и исключения повторных маршрутов получаем шесть различных путей из А в К.

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

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

1. 1
   Из города A есть один начальный путь: $N_A=1$. В город E ведёт один путь из A, поэтому $N_E=1$.
2. 2
   В город D можно попасть из A или E: $N_D=N_A+N_E=1+1=2$.

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

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

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

1. 1
   Начинаем с города А: в него входит начальная точка одного пути, поэтому число путей в А равно 1.$$N_A=1$$
2. 2
   Последовательно вычисляем число путей в остальных городах по направлениям стрелок.$$N_{Б}=1, N_{В}=N_A+N_{Б}=2, N_{Г}=N_A+N_{В}=3$$

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

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

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

1. 1
   Обозначим количество путей из А до каждой вершины. Для городов Б, В и Д существует по одному пути из А.$$N_{Б}=1,\quad N_{В}=1,\quad N_{Д}=1$$
2. 2
   В город Е ведут дороги из Б и В, поэтому количество путей до Е равно двум.$$N_{Е}=N_{Б}+N_{В}=1+1=2$$

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

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

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

1. 1
   Начинаем с города А: существует один путь, который начинается в А.$$N(А)=1$$
2. 2
   В город Б ведёт одна дорога из А, поэтому число путей равно 1. В город В ведут дороги из А и Б, поэтому число путей равно 2.$$N(Б)=1,\quad N(В)=N(А)+N(Б)=1+1=2$$

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