Задание №11 ОГЭ. Анализ информации, представленной в виде схем
Формализация описания реальных объектов и процессов относится к содержательным элементам, проверяемым в задании №11 основного государственного экзамена по информатике и ИКТ.
В задаче, относящейся к базовому уровню сложности, проверяются умения учащихся подсчитывать количество путей в графе.
Для подготовки к ОГЭ рассмотрим варианты одиннадцатого задания, которые встречались в тренировочных и демонстрационных работах по информатике и ИКТ прошлых лет.
Задание №11. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение.
Поскольку граф может быть достаточно большим, то обычный перебор всех путей становится крайне громоздким и, с большой долей вероятности, приведет к ошибкам. Для решения задачи воспользуемся методами динамического программирования: будем использовать на каждом следующем шаге результаты предыдущих значений.
Пусть существует некоторая базовая «стоимость» исходной вершины А, равная 1, тогда:
- в вершину Б можно попасть только по одному пути, значить стоимость Б равна 1;
- в вершину В можно попасть из А (стоимость 1) и из Б (стоимость 1), значит, стоимость В рана 2 (А + Б) и т. д.
Последовательно будем подписывать около каждой следующей вершины полученные значения стоимостей (смотрите рис. 1). В результате получим:
Ответ. 12