Примеры заданий
Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого протяжённого пути из города А в город Л? Длиной пути считать количество дорог, составляющих этот путь.
Показать ответ
Решение.
- Длина пути — число дорог. Для каждого города L = 1 + максимум L по городам, откуда ведут стрелки; L(А) = 0.
- Б = 1 (из А); Г = 1 (из А); В = 1 + max(А, Б, Г) = 2; Д = 1 + Б = 2; Ж = 1 + max(Г, В) = 3; Е = 1 + max(Б, В, Д) = 3.
- И = 1 + max(Д, Е) = 4; К = 1 + max(Е, Ж) = 4; Л = 1 + max(Е, И, К) = 5.
- Например, А → Б → В → Е → И → Л или А → Г → В → Ж → К → Л — по 5 дорог; длиннее пути нет.
- Проверка программой:
roads = 'АБ АВ АГ БД БВ БЕ ГВ ГЖ ВЕ ВЖ ДИ ДЕ ЕИ ЕЛ ЕК ИЛ ЖК КЛ'.split() def longest(u): if u == 'Л': return 0 return max(1 + longest(r[1]) for r in roads if r[0] == u) print(longest('А')) # 5 - Ответ: 5.
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.
Показать ответ
Решение.
- Из Е выходят две дороги: Е → В и Е → Л. В Е входят дороги из Д, Г и Ж (а в Ж — из Г и К). Перебираем пути без повторов городов.
- Ветвь Е → В (13 путей): ЕВДЕ, ЕВДЛКЖЕ, ЕВДИЛКЖЕ; ЕВБДЕ, ЕВБДЛКЖЕ, ЕВБДИЛКЖЕ; ЕВАБДЕ, ЕВАБДЛКЖЕ, ЕВАБДИЛКЖЕ; ЕВГЕ, ЕВГЖЕ; ЕВАГЕ, ЕВАГЖЕ. Ветвь Е → Л (1 путь): ЕЛКЖЕ. Всего 13 + 1 = 14.
- Проверка программой (перебор в глубину):
roads = 'АБ АГ БД ВА ВБ ВД ВГ ДИ ДЕ ДЛ ЕВ ЕЛ ИЛ ЛК КЖ ГЖ ГЕ ЖЕ'.split() def count(u, seen): total = 0 for r in roads: if r[0] == u: if r[1] == 'Е': total += 1 elif r[1] not in seen: total += count(r[1], seen | {r[1]}) return total print(count('Е', {'Е'})) # 14 - Ответ: 14.
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.
Показать ответ
Решение.
- Из Е выходят две дороги: Е → В и Е → Л. В Е входят дороги из Д, Г и Ж (а в Ж — из Г, К и Л). Перебираем пути без повторов городов.
- Каждый путь, проходящий через Л → К → Ж, теперь имеет пару через Л → Ж. Ветвь Е → В: через Д (ВД, ВБД, ВАБД) — по 5 продолжений (ДЕ, ДЛКЖЕ, ДЛЖЕ, ДИЛКЖЕ, ДИЛЖЕ), итого 15; через Г — ЕВГЕ, ЕВГЖЕ, ЕВАГЕ, ЕВАГЖЕ — 4. Ветвь Е → Л: ЕЛКЖЕ, ЕЛЖЕ — 2. Всего 15 + 4 + 2 = 21.
- Проверка программой (перебор в глубину):
roads = 'АБ АГ БД ВА ВБ ВД ВГ ДИ ДЕ ДЛ ЕВ ЕЛ ИЛ ЛК КЖ ГЖ ГЕ ЖЕ ЛЖ'.split() def count(u, seen): total = 0 for r in roads: if r[0] == u: if r[1] == 'Е': total += 1 elif r[1] not in seen: total += count(r[1], seen | {r[1]}) return total print(count('Е', {'Е'})) # 21 - Ответ: 21.