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.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

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

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

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

*
*

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