Сколько путей из А в М не проходят через город Г
Условие
Дороги с односторонним движением связывают пункты А, Б, В, Г, Д, Е, Ж и М: А→Б, А→В, Б→Г, Б→Д, В→Г, В→Д, Г→Е, Г→Ж, Д→Е, Д→Ж, Е→М, Ж→М. Сколько существует путей из А в М, которые НЕ проходят через пункт Г?
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Шаг 1. Два правила, на которых держится решение
Задачи «через заданный пункт» и «мимо заданного пункта» решают одной парой приёмов:
- правило умножения: любой путь через Г — это путь из А в Г, продолженный путём из Г в М, поэтому число путей через Г равно (число путей А→Г) (число путей Г→М);
- правило вычитания: путей мимо Г ровно столько, сколько всего путей, минус пути через Г.
Значит, план такой: посчитать все пути, потом пути через Г, потом вычесть.
Шаг 2. Считаем общее число путей из А в М
Обозначим — число путей из А в , и будем складывать значения предшественников. Порядок обработки: А, Б, В, Г, Д, Е, Ж, М — все дороги в нём ведут только вперёд.
; ; ;
; ;
; ;
. Всего 8 путей.
Осталось ещё 3 шага
Шаг 3. Считаем пути через Г
Шаг 4. Вычитаем и получаем ответ
Шаг 5. Проверка другим способом
Бесплатно · займёт минуту
Частые ошибки
- ✗
Вычитают из общего числа путей только количество путей из А в Г (то есть 2) и получают 6 — вычитать надо все пути, проходящие через Г, а их .
- ✗
Убирают вершину Г, но забывают убрать её дороги — и в пересчёте в Е и Ж по-прежнему «въезжают» через несуществующий пункт.
- ✗
Считают, что «не проходит через Г» значит «не начинается и не кончается в Г», и отвечают 8.
- ✗
Теряют дорогу Г→Ж, насчитывают только 2 пути через Г и получают 6 вместо 4.