ЕГЭОГЭ
РУҚА
ОГЭ · информатика · тақырып бойынша шешімдер

ФИПИ тапсырмаларының шешімдері ОГЭ по информатикаға: «Графы и пути» — жауаптарымен

ФИПИ ашық банкінен тақырыптың әрбір есебі — жауабымен және алғашқы қадамдарымен талдау. Толық қадамдық шешім және ресми кілт – карточкадағы сілтемелер бойынша.

Шешімсіз тапсырмалар
171
жауаптары бар шешімдер
1 546
пәндегі есептер
9
тізім беттері
161ФИПИ e3B49c№ 9Күрделі

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

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

  1. 1
    Начинаем с города А: число путей в него равно 1.
  2. 2
    По стрелкам находим количество путей в промежуточные города: в Б — 1, в В — 2, в Г — 2, в Д — 1, в Е — 1.

Ещё 4 қадам — толық шешімде

Шешім полностьюЖауапШешу самому6 қадам в разборе
162ФИПИ e41B11№ 9Күрделі

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

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

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

Ещё 2 қадам — толық шешімде

Шешім полностьюЖауапШешу самому4 қадам в разборе
163ФИПИ e5c61c№ 9Күрделі

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

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

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

Ещё 3 қадам — толық шешімде

Шешім полностьюЖауапШешу самому5 қадам в разборе
164ФИПИ E6ED27№ 9Күрделі

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

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

  1. 1
    Обозначим количество путей из А в каждую вершину. До Б и Д ведёт по одному пути: из А.
  2. 2
    До В ведут пути непосредственно из А и через Б, поэтому количество путей равно $1 + 1 = 2$.

Ещё 4 қадам — толық шешімде

Шешім полностьюЖауапШешу самому6 қадам в разборе
165ФИПИ e8FD7c№ 9Күрделі

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

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

  1. 1
    В город A ведёт один начальный путь: считаем количество путей из A в каждую вершину.$$N_A=1$$
  2. 2
    В город D можно попасть непосредственно из A или по маршруту $A\to C\to D$.$$N_D=N_A+N_C=1+1=2$$

Ещё 3 қадам — толық шешімде

Шешім полностьюЖауапШешу самому5 қадам в разборе
166ФИПИ EA32B6№ 9Күрделі

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

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

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

Ещё 3 қадам — толық шешімде

Шешім полностьюЖауапШешу самому5 қадам в разборе
167ФИПИ ecF85e№ 9Күрделі

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

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

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

Ещё 1 қадам — толық шешімде

Шешім полностьюЖауапШешу самому3 қадам в разборе
168ФИПИ EDBA0C№ 9Күрделі

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

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

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

Ещё 2 қадам — толық шешімде

Шешім полностьюЖауапШешу самому4 қадам в разборе
169ФИПИ F1E6B6№ 9Күрделі

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

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

  1. 1
    Перечислим пути, начинающиеся с перехода из А в Б: А–Б–Д–К, А–Б–К, А–Б–В–К.
  2. 2
    Путь через В без промежуточных городов: А–В–К.

Ещё 2 қадам — толық шешімде

Шешім полностьюЖауапШешу самому4 қадам в разборе
170ФИПИ FE2246№ 9Күрделі

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

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

  1. 1
    Рассмотрим все пути из города А по первой выбранной дороге.
  2. 2
    Через город Б можно попасть в К напрямую, через В или через Д: всего 3 пути.$$Б \to К;\quad Б \to В \to К;\quad Б \to Д \to К$$

Ещё 3 қадам — толық шешімде

Шешім полностьюЖауапШешу самому5 қадам в разборе
171ФИПИ FF4696№ 9Күрделі

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

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

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

Ещё 2 қадам — толық шешімде

Шешім полностьюЖауапШешу самому4 қадам в разборе

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