Егэ информатика подсчет путей

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

Автор — Лада Борисовна Есакова.

Подсчет путей в ориентированном графе. ЗАДАЧА № 15.

В этой задаче требуется подсчитать количество путей, ведущих из одной вершины графа в другую. Обычно задачу решают преобразованием графа в дерево. Однако, при сложной структуре графа такое решение становится очень трудоемким. Велика вероятность ошибки.

Рассмотрим простой и эффективный способ решения.

В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

Пример:

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

Решение:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).

У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.

Индекс вершины Ж и будет ответом задачи.

Ответ: 11

Хотите готовиться со мной к ЕГЭ?
Пишите:  ydkras@mail.ru
Немного обо мне.

В задаче 13 ЕГЭ по информатике требуется подсчитать число путей из одного узла в другой.

Вот типичная задача (заимствована из демонстрационного варианта ФИПИ по информатике 2022 г.):

 

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

Как решать подобные задачи программным путем? Прежде всего надо уметь представлять информацию о графе в форме, удобной для компьютерной обработки. В языке Питон есть очень удобный тип данных для нашей цели: словарь или ассоциативный массив. Это совокупность пар «ключ-значение». 

Сначала подготовим исходные данные для заполнения словаря. Создадим текстовый файл, строки которого устроены следующим образом: первая буква строки — это один из городов, а следующие буквы — список городов, в которые можно попасть из данного города.

Для данного графа файл будет таким:

При составлении этого файла необходимо быть очень аккуратным, ничего не упустить и ничего не перепутать и, конечно, не употреблять латинские буквы вместо русских. Последняя строка говорит, что город М существует, но из него нет дорог. (Если мы опустим эту строку, то это может привести к ошибке выполнения в некоторых задачах.)

Напишем фрагмент программы, которая введет этот файл и создаст словарь. описывающий граф:

Вначале создается пустой словарь (словари заключаются в фигурные скобки). Затем файл с описанием графа читается построчно, и первый символ строки используется как ключ, а остальные — как значение, соответствующее данному ключу. Добавление в словарь — это просто присваивание элементу словаря с некоторым ключом значения. Если такой элемент уже существует, то значение будет перезаписано, в противном случае будет создан новый элемент. Метод strip удаляет пробелы и символы конца строки в начале строки и её конце — это нужно, чтобы убрать символы конца строки. Проверка len(s)>0 нужна, чтобы не обрабатывать пустые строки (если они окажутся в файле, это вызовет обибку выполнения). Первый символ каждой строки, т.е. s[0], используется как ключ в словаре, а хвост строки (все символы, кроме первого) — как значение, связанное с этим ключом.

Для контроля распечатаем словарь:

{‘А’: ‘БВГД’, ‘Б’: ‘ВЕ’, ‘В’: ‘ЖЗ’, ‘Г’: ‘ВЗ’, ‘Д’: ‘ГЗ’, ‘Е’: ‘ЖИ’, ‘Ж’: ‘И’, ‘З’: ‘ЖИ’, ‘И’: ‘КЛ’, ‘К’: ‘М’, ‘Л’: ‘М’, ‘М’: »}

Теперь всё готово для того, чтобы написать программу, которая ищет решение.

Простой случай — подсчёт количества путей

Сначала решим более протую задачу: подсчитаем число путей из А в М без каких-либо дополнительных ограничений. 

Для этого напишем рекурсивную функцию ways:

def ways(start,end,karta):
    if start==end: return 1
    r=0
    for i in range(len(karta[start])): r += ways(karta[start][i],end,karta)
    return r

Функция подсчитывает число путей из города start в город end. Граф дорог задается в параметре karta, который должен быть словарем с описанной выше структурой. 

Если значения start и end совпадают, то мы уже находимся в городе, в который должны попасть, и функция возвращает 1. Если же мы ещё не добрались до пункта назначения, то функция вызывает сама себя для каждого города, куда можно попасть из текущего города, и суммирует число путей из каждого города до конечного пункта. 

Число путей из города А в город М — это результат вычисления функции ways(‘А’,’М’,a). Разумеется, буквы ‘А’ и ‘М’ в параметрах функции должны быть русскими, а не латинскими.

Приведём программу полностью:

Ограничения на маршрут: запрещенные города и города, обязательные для посещения

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

Вначале решим задачу с городом, обязательным для посещения. Вспомним, что в задаче, приведенной в начале этой заметки, требуется, чтобы маршруты проходили через город В. 

Подсчитаем число маршрутов от А до В, а затем от В до М. Любой маршрут первого этапа можно комбинировать с маршрутом второго этапа, поэтому общее число маршрутов — это произведение числа маршрутов первого этапа на число маршрутов второго этапа. Таким образом, задача решается заменой последней строки в приведенной выше программе на строку

print(ways(‘А’,’В’,a)*ways(‘В’,’М’,a))

Если какой-то город запрещен для посещения, то можно найти сперва общее число маршрутов от начального пункта до конечного, затем — число маршрутов, которые проходят через данный город. Число маршрутов, которые не проходят через этот город, равно разности общего числа маршрутов и числа маршрутов, проходящих через данный город.

Так, найти число маршрутов, которые не проходят через город В в приведенной выше задаче, можно с помощью выражения

print(ways(‘А’,’М’,a) — ways(‘А’,’В’,a)*ways(‘В’,’М’,a))

Другой способ рещения задачи с избегаемым городом — доработать нашу функцию ways, добавив в неё возможность исключать из рассмотрения определённые города.

Функция может выглядеть, например, так:

def ways(start,end,karta,zapret):
    if start in zapret: return 0
    if start==end: return 1
    r=0
    for i in range(len(karta[start])): r += ways(karta[start][i],end,karta,zapret)
    return r

В нее добавлен новый параметр zapret — это символьная строка, содержащая города, маршруты через которые не учитываются. Если символ start содержится в этой строке, то функция возвращает 0. Строка zapret может состоять более чем из одного символа: в этом случае будут учтены только те маршруты, которые не проходят через любой из городов, перечисленных в этой строке.

Число маршрутов из А в М, не проходящих через город В, можно найти так:

Можно также пользоваться этой функцией, чтобы найти число маршрутов, проходящих через город В. Для этого вычтем из общего числа маршрутов число таких, которые через этот город не проходят:

print(ways(‘А’,’М’,a,»)-ways(‘А’,’М’,a,’В’))

(Если параметр zapret — это пустая строка, то ограничений на подсчет маршрутов нет.)

Обязательный и избегаемый города

Если требуется, чтобы маршрут обязательно проходил через какой-либо город и не проходил через другой, то можно решить задачу, разбив путь на два этапа, как было описано ранее. На каждом этапе мы задаем запрещенный город в параметре zapret.

Можно также вычесть из числа маршрутов, которые не проходят через «запрещённый» город, число маршрутов, которые не проходят как через «запрещённый», так и через «обязательный» город.

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

Ещё один вариант ограничения — найти число маршрутов, которые проходят либо через пункт В, либо через пункт З, но не через оба этих пункта одновременно.  Можно сложить число маршрутов, проходящих через В и не проходящих через З, с числом маршрутов, проходящих через З и не проходящих через В. Можно также найти число маршрутов, проходящих дибо через В, либо через З, либо через В и З, а потом вычесть из него число маршрутов, проходящих как через В, так и через З.

Ограничения на длину маршрута

В некоторых задачах требуется, чтобы определенным ограничениям удовлетворяла и длина маршрута (т.е. количество городов, через которые проходит маршрут).

Так, вопрос может быть таким: «Сколько существует маршрутов из А в М, проходящих ровно через семь городов, считая А и М?»

Доработаем нашу функцию ways с тем, чтобы она хранила текущий маршрут. Дополним её новым параметром trassa, в котором будем хранить маршрут. Когда мы достигнем города назначения, то проверим длину маршрута. Если она такая, какая требуется, то мы засчитываем рашение (возвращаем 1), в противном случае — нет (возвращаем 0). 

Вот полная программа, решающая эту задачу:

Так как нам требовалась только длина маршрута, то можно было бы обойтись не строкой, а целой переменной. Но строка, хранящая маршрут, дает большую гибкость: можно, анализировать эту строку и, например, принимать только те маршруты, которые проходят по участку В-Ж. (if ‘ВЖ’ in trassa).

Самый длинный или самый короткий путь

Иногда требуется выяснить, какова длина самого длинного или самого короткого пути. Задачу можно решить, фиксируя длину пути в момент достижения пункта назначения. 

Решим задачу нахождения длины самого длинного и самого короткого пути:

Команда global l,L в функции ways дает доступ к внешним переменным l и L, в которых вычисляется минимальная и blog/loadingмаксимальная длина пути.

Нужно обращать внимание на формулировку вопроса в задачах о длине пути. Данная программа вычисляет число городов, через который проходит путь, включая начальный и конечный города. Если же требуется найти число дорог, по которым надо проехать, то оно, очевидно, на единицу меньше числа городов. Так, данная программа дает ответ, что самый короткий путь содержит 6 городов, а самый длинный — 9. Соответственно, минимальное число дорог — это 5, а максимальное — 8.

Стоит ли овчинка выделки?

У дочитавших до этого места может возникнуть вопрос: а нужно ли всё это? Ведь такие задачи можно решать на листке бумаги. Автор не берется ответить на этот вопрос. Попробуйте найти ответ сами. Решите одну и ту же задачу вручную и на компьютере — и определите, какой способ будет для вас проще и быстрее. Удачи вам!

(c) Ю.Д.Красильников, 2022 г

Характеристика задания

1. Тип ответа: числовой.

2. Структура содержания задания: дана текстовая задача и схема к ней, нужно определить количество путей из начальной точки до конечной по схеме.

3. Уровень сложности: повышенный.

4. Примерное время выполнения: (3) минуты.

5. Количество баллов: (1).

6. Требуется специальное программное обеспечение: нет.

7. Задание проверяет умение представлять и считывать данные в разных типах информационных моделей.

Основной способ решения задания разобран в предыдущей теории. С (2022) года появилось задание, которое вызвало затруднение на экзамене, хотя способ решения остался тот же: нужно подсчитать количество путей, но ограничения другие. Разберём это задание.

ЕГЭ-(2022). На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определи количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.

Рис. (1). Схема к заданию (2022)

Решение: из точки Е ведут только три дороги: в сторону В, И и К.

Рис. (2). Варианты движения

Рассмотрим их в отдельности.

Направление ЕВ.

Рис. (3). Количества маршрутов в направлении ЕВ

В (=) Е (= 1),

А (=) В (=1),

Г (=) А (+) В (=2),

Б (=) А (=1),

Д (=) Б (+) В (=2+1=3),

З (=) Д (=3),

К (=) Д (+) З (=3+3=6),

И (=) К (=6),

Ж (=) Г (+) И (+) В (=2+6+1=9),

Е (=) Ж (+) Д (=12).

Итого (12) маршрутов.

Теперь рассмотрим направление ЕК.

Рис. (4). Количества маршрутов в направлении ЕК

Е (=1),

К (=) Е (=1),

И (=) К (=1),

Ж (=) И (=1),

Е (=) Ж (=1).

Всего (1) маршрут.

Также в направлении ЕИ — тоже (1) маршрут.

Складываем (12+1+1=14).

Ответ: (14).

В Демоверсии (2023) года вариант аналогичный.

Рассмотрим ещё один тип заданий.

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

Длиной пути считать количество дорог, составляющих этот путь.

Рис. (5). Схема к заданию

Можно сказать, что вес каждого ребра равен единице, и поэтому, проходя по ребру, мы добавляем к предыдущему значению (1).

Начало отсчёта — в точке А, окончание пути — в точке М.

Просчитаем маршруты от точки А до Ж.

Помним, что маршрут должен быть максимальный, поэтому рассмотрим варианты:

в вершину В можно прийти:

А—В (=1),

А—Б—В (=2),

А—Г—В (=2),

А—Д—Г—В (=3).

Выберем А—Д—Г—В.

В вершину Е:

А—Д—Г—В—Е (=4), с учётом предыдущего выбора, все остальные пути короче.

Поэтому в вершину Ж будет путь А—Д—Г—В—Е—Ж(=5), самый длинный.

И (=5)(Ж) (+) (1=6),

К (=6)(И) (+) (1=7),

М (=7)(К) (+) (1=8).

Ответ: (8).

ЕГЭ-2015 задание 15.

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

Теория

Если в город S можно приехать только из городов X, Y, и Z, то число различных путей из города A в город S равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть

N_S = N_X + N_Y + N_Z ,

где N_M обозначает число путей из вершины A в некоторую вершину M

Число путей конечно, если в графе нет циклов — замкнутых путей

Задача

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

Решение

Будем обозначать через N_X количество различных путей из города А в город X. Для города А есть только один маршрут – никуда не двигаться, поэтому N_A = 1. Для любого города X количество маршрутов N_X можно вычислить как

N_X = N_Y + … + N_Z

где сумма взята по всем вершинам, из которых есть прямой путь в вершину X; например, 

N_Л = N_Д + N_И + N_Ж + N_К

Составим таблицу, в которой около каждого города будем записывать количество прямых путей в этот город. Начнем считать количество путей с начала маршрута – с города А: 

В пункты Б и В ведут единственные дороги из А. В пункт В можно попасть из пунктов А, Б, и Г, т.е. N_В = N_А + N_Б + N_Г = 3.

А	Б	В	Г	Д	Е	Ж	И	К	Л
1	1	3	1

В пункт Е можно попасть только из Г, количество путей равно количеству путей в пункт Г. В пункт Ж ведут прямые пути из пунктов Е и В, т.е. N_Ж = N_В + N_Е = 4. В пункт Д ведут прямые пути из пунктов Б и В, т.е. N_Д = N_В + N_Б = 4.

А	Б	В	Г	Д	Е	Ж	И	К	Л
1	1	3	1	4	1	4

В пункт И можно попасть только из Д, количество путей равно количеству путей в пункт Д = 4. В пункт К ведет путь только из пункта Е, т.е. N_К = N_Е = 1. В пункт Л ведут прямые пути из пунктов Д, И, Ж и К, т.е. N_Л = N_Д + N_И + N_Ж + N_К = 13.

А	Б	В	Г	Д	Е	Ж	И	К	Л
1	1	3	1	4	1	4	4	1	13

Ответ

13

Public user contributions licensed under
cc-wiki license with attribution required