Разбираем задачу №15 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
Задание 15 - повышенного уровня сложности на умение преобразовывать вид информации. Реально имеет двоякую сложность из-за навыка смыслового чтения. Тем, кто этим навыком обладает, такие задания кажутся простыми и "вообще, зачем такое легкое в ЕГЭ?". Тем, кто не обладает, задание может показаться невероятно трудным, выполнимым только "если повезет"
Облегчает жизнь то, что в задании требуется лишь использовать готовые модели. Это всегда проще, чем создавать модель самому или анализировать результаты моделирования.
Та часть теории, которая входит в школьную программу
Её совсем немного, и часть я уже описывал в третьем задании. И это только определения.
Граф - (рисунок) множество точек, соединённых линиями. Множество в математическом смысле, а не в смысле "много". Точки называются вершинами графа, а линии, их соединяющие - рёбрами.
Каждому ребру и вершине может быть назначено число, обозначающее какую-то числовую характеристику этих рёбер и вершин. Число называется весом ребра или весом вершины.
И вот с весом вершин мы и будем работать сейчас. В нашем случае число, вес вершины, будет отвечать на вопрос: "сколькими путями можно попасть в эту вершину?"
Разбор задания
Я предлагаю универсальный способ решения этой задачи, основанный на теории графов. Основная часть этой теории находится за пределами школьной программы, поэтому в школе изучают лишь некоторые её аспекты. И один из них я опишу здесь.
Способ подойдёт всем - и тем, кто умеет читать, и тем, кто этому к 11му классу не научился.
На что обращать внимание в первую очередь: в вопросе задания есть уточнение "проходящих через город Ж"
Уточнение может касаться чего угодно, но направлено оно всегда на то, что рисунок (граф) требуется немного изменить. Перерисую его. Для этого мне придётся убрать все стрелки, которые не подходят под уточнение. Двигаясь по каким стрелкам мы никогда не попадём в город Ж? Это стрелки ЕИ и ЗИ.
Этот шаг сделан, видимо, для того, чтобы добавить элемент смыслового чтения в абсолютно алгоритмизуемое задание. Потому что теперь:
Алгоритм решения
У каждого города проставим число - количество способов, которыми можно в него попасть. Это будет гораздо легче сделать, если учитывать ближайших соседей "сверху", то есть те города, из которых можно попасть в этот напрямую. Например. в город З можно попасть напрямую из Д, Г и В. Тогда количество маршрутов до З будет суммой путей в Д, Г и В.
Итак:
- Возле начального города ставим (1).
- Возле каждого следующего ставим число =
а) выбираем все города, из которых можно попасть в данный напрямую.
б) складываем все их числа.
Начинать будем с А, потому что в него мы попадаем одним способом - с него начинаем:
По алфавиту следующий город - Б, но с ним проблема - для того, чтобы написать там число, надо сложить А (1) и В (?). А число В(?) мы не знаем, для него надо знать Г. А для Г - Д. И вот только Д - мы можем посчитать, потому что все входящие для Д известны:
И вот теперь можно вычислить количество путей в город Г: это один способ из города А и один через город Д.
В город В можно попасть одним способом из А и ещё двумя через город Г:
Теперь можно посчитать, сколько путей в города З и Е - как суммы всех входящих.
Таким образом можно заполнить весь граф:
Теперь рядом с каждой вершиной (городом) написано, сколькими путями можно попасть в него, стартуя из города А.
Ответ: 51.
Другие способы
Прямой перебор вариантов
А почему бы и нет? Просто сидеть и выписывать их
АБЕЖИКМ
АБЕЖИМ
АБЕЖИЛМ
АБЖИКМ
АБЖИМ
АБЖИЛМ
...
Долго, но, набравшись опыта, можно и за три минуты успеть. Более того, этот способ гораздо универсальнее, потому что можно работать с первоначальным графом, а потом вычеркнуть те, в которых нет буквы Ж (не подходит по критерию).
Конечно, тут требуется оптимизация. Обратили внимание, в каком порядке я выписывал маршруты? Сначала верхний, потом следующий вниз и так далее:
"Развернуть" граф в дерево
Способ тоже требует серьёзной концентрации. Нужно делить и дублировать вершины так, чтобы получилось дерево. Кроме того, потребуется ещё очень много места на бумаге.
Пересчитать все листья дерева.
Мне этот способ кажется самым нерациональным (хотя и довольно точным, вероятность ошибки тут маленькая), поэтому я не буду доводить его до конца, а оставлю только как пример.
Заключение
Этот способ очень быстрый, но не единственный. Основан он на накоплении веса однонаправленного графа. Работает только с такими графами, в которых нельзя по одному ребру пройти дважды.
С практической точки зрения, конечно, это задание довольно бесполезно - вряд ли кто-то на самом деле будет считать количество маршрутов, разве что для моделирования логистических карт. Но вот если немного абстрагироваться от движения по дорогам, то любая комбинаторная задача на перебор вариантов может быть решена подобным способом. Для вычисления вероятности того или иного исхода нужно знать количество всех исходов. Кстати, на этом может быть основано и решение задания 22.