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

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

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

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

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

  • Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:
  • NR = NX + NY + NZ
  • где NR — это количество путей из вершины A в вершину R
  • Число путей не бесконечно, исключением является только схема, в которой есть циклы – замкнутые пути.
  • Часто подобные задания целесообразней решать с конца (рассмотрим пример ниже).

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

    Подробный видеоразбор по ОГЭ 11 задания:

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


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


✍ Решение:
 

  • Решим задание с конца. Т.е. так как траектория поиска путей от А до Н, то мы будем рассматривать сначала город Н.
  • В город Н можно попасть из трех городов — 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

Поделитесь уроком с коллегами и друзьями:
One Comment

    анна

    Отличный сайт)
    Все обьяснено очень понятно, вопросов не остается))
    спасибо))

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*


Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить