Подготовка к OГЭ: Задание 11

Задача 11

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

Решение задач типа 11 ГИА по информатике

Данный тип задач нацелен на проверку умения анализировать информацию, представленную в виде схем. При решении есть вероятность запутаться в большом количестве вариантов.

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

Итак, начнем решение с конца, т. е. с города К. Как мы видим, в город К можно приехать из городов Е, В, Г, Ж. Отобразим это графически

Задача 11 ГИА по информатике. Шаг 1

Далее, на втором шаге определим, откуда можно добраться в города Е, В, Г, Ж. К примеру,

• в город Е можно добраться только из города Б,

• в город В - из городов А и Б,

• в город Г из городов А, В и Д,

• в город Ж из городов Г и Д.

Графически это будет выглядеть таким образом:

Задача 11 ГИА по информатике. Шаг 2

Таким образом, мы будем продолжать до тех пор, пока каждая ветка не приведет к городу А. В итоге получится такая диаграмма - дерево:

Задача 11 ГИА по информатике. Шаг 3

Здесь зеленым цветом я выделил конечные пункты - город А. Осталось только посчитать их количество - это и будет правильный ответ. В нашем случае их 12. Правильный ответ: 12.