Объяснение и решение задания 11 с графами ОГЭ информатика

На уроке рассмотрен материал для подготовки к ОГЭ по информатике, рассмотрены примеры того, как решать 11 задание. Дан теоретический материал по теме «Анализирование информации, представленной в виде схем и поиск количества путей».

К оглавлению

Содержание:

ОГЭ по информатике 11 задания объяснение
- Поиск количества путей
11 задание как решать

ОГЭ по информатике 11 задания объяснение

11-е задание: «Анализирование информации, представленной в виде схем».
Уровень сложности — базовый,
Максимальный балл — 1,
Примерное время выполнения — 4 минуты.

Поиск количества путей

Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:

N_R = N_X + N_Y + N_Z

где N_R — это количество путей из вершины A в вершину R
Число путей не бесконечно, исключением является только схема, в которой есть циклы – замкнутые пути.
Часто подобные задания целесообразней решать с конца (рассмотрим пример ниже).

11 задание как решать

Рассмотрено 3 задачи. Перемотайте видеоурок на решение нужной задачи.

Решение задания 11.1:

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

Типовые задания для тренировки

✍ Решение:

Решим задание с конца. Т.е. так как траектория поиска путей от А до Н, то мы будем рассматривать сначала город Н.
В город Н можно попасть из трех городов — C, D и G; запишем это так:

H = C + D + G

Теперь аналогично рассмотрим города C, D и G:

C = D + A
D = A + E
G = D + E + F

Далее, рассмотрим каждый город, дойдя до первого — города А. Для него существует только одни путь. Также, для городов, выходящих только из города А, тоже существует только 1 путь. Таким образом имеем:

H = C + D + G

C = D + A
D = A + E
G = D + E + F
-----
D = Е + A 
A = 1 
E = A + B
F = B
B = 1

Теперь возвращаемся, подставляя найденные значения: ↑
F = B = 1
E = A + B = 1 + 1 = 2
D = Е + A = 2 + 1 = 3
G = D + E + F = 3 + 2 + 1 = 6     
D = A + E = 1 + 2 = 3 
C = D + A = 3 + 1 = 4

H = C + D + G = 4 + 3 + 6 = 13

Ответ: 13

Решение задания 11.2. Сборник Ушакова Д.М., 2018 г. ВАРИАНТ 2:

На карту нанесены 4 города (A, B, C и D).
Известно, что:
между городами A и C — три дороги,
между городами C и B — две дороги,
между городами A и B — две дороги,
между городами C и D — две дороги,
между городами B и D — четыре дороги.
По каждой из этих дорог можно ехать в обе стороны.

Сколькими различными способами можно проехать из A в D, посещая каждый город не более одного раза?

Типовые задания для тренировки

✍ Решение:

Построим все возможные ветви для движения из города A. Будем выполнять произведение количества дорог для каждой ветви, так как движение возможно в обе стороны:

A * B * C * D = 2 * 2 * 2 = 8  (A и B - две дороги, C и B - две дороги, C и D - две дороги)
A * B * D = 2 * 4 = 8          (A и B - две дороги, B и D - четыре дороги)
A * C * D = 3 * 2 = 6          (A и C - три дороги, C и D - две дороги)
A * C * B * D = 3 * 2 * 4 = 24 (A и C - три дороги, C и B - две дороги, B и D - четыре дороги)

Полученные результаты для каждого способа движения из города A в город D следует сложить:

8 + 8 + 6 + 24 = 46

Ответ: 46

Решение задания 11.3. Демонстрационный вариант перспективной модели, ФИПИ, 2019 г.:

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

Сколько существует различных путей из города А в город К, проходящих через город В?
решение 11 задания ОГЭ по информатике

✍ Решение:

✎ 1 способ (дерево):

Поскольку нас интересуют пути, проходящие через город В, то вычеркнет те дороги, которые минуют город В:

Как видим, таких дорог получилось две — Б->Д и А->Г. Учтем это при дальнейших расчетах.
Решим задание с конца. Т.е. так как траектория поиска путей — от А до K, то мы будем рассматривать сначала город K.
В город K можно попасть из трех городов — Д, E и Ж; запишем это так:

K = Д + Е + Ж

Теперь аналогично рассмотрим города Д, Е и Ж:

Д = В (Б -> Д не учитываем)
Е = Д + В
Ж = В + Г

Далее, рассмотрим каждый город, дойдя до первого — города А. Для него существует только одни путь. Также, для городов, выходящих только из города А, тоже существует только 1 путь. Таким образом имеем:

К = Д + Е + Ж

Д = В 
Е = Д + В
Ж = В + Г
-----
Б = А = 1
  A = 1 
В = Б + А 
Д = B
Ж = B + Г
  Г = В  (А - Г не учитываем)


Теперь возвращаемся, подставляя найденные значения: ↑
В = Б + А = 2
Г = В = 2
Д = В = 2
Ж = B + Г = 2 + 2 = 4
Е = Д + В = 2 + 2 = 4

Поскольку нас интересуют пути, проходящие через город В, то вычеркнет те дороги, которые минуют город В:

К = Д + Е + Ж = 2 + 4 + 4 = 10

✎ 2 способ (дерево):

Построим дерево, расположив его для удобства горизонтально:

                К
           Д -  Е  -  К
          --------------
                      Е   -  К
                Д  -  К
     Б -   В -  Е  -  К
                Ж  -  К
                Г  -  Ж - К
А           ----------------
           Д -  К
                Е  -  К
     В -   Е -  К
           Ж -  К
           Г -  Ж  - К
           ----------------
     Г -   Ж -  К

Уберем пути, в которых отсутствует город В:

                К
           Д -  Е  -  К
          --------------
                      Е   -  К
                Д  -  К
     Б -   В -  Е  -  К
                Ж  -  К
                Г  -  Ж - К
А           ----------------
           Д -  К
                Е  -  К
     В -   Е -  К
           Ж -  К
           Г -  Ж  - К
           ----------------
     Г -   Ж -  К

Подсчитаем количество оставшихся путей следования до города К, их 10.

Ответ: 10

К оглавлению

11 задание ОГЭ информатика

ОГЭ по информатике 11 задания объяснение

Поиск количества путей

11 задание как решать

Один комментарий

анна

Добавить комментарий Отменить ответ