Новая Школа - онлайн-школа подготовки к ЕГЭ
Информатика · 11 класс Задача №3825968
А
Аноним
7 часов назад · публичный вопрос
А
Аноним

вся теория для 1 задания ЕГЭ по информатике

Ответ нейросети
7 часов назад

Краткий ответ

Задание 1 ЕГЭ по информатике — это подсчёт количества путей в ориентированном графе («схема дорог, по каждой дороге можно двигаться только в одном направлении, указанном стрелкой»). Универсальный способ решения — динамическое программирование по вершинам: у стартовой вершины число путей равно 1, у каждой следующей — сумма чисел путей всех вершин, из которых в неё входят стрелки. Дополнительные условия («через город X», «не проходя через Y») учитываются тем же аппаратом.


1. Понятия, которые нужно держать в голове

  • Граф — набор вершин (городов, пунктов) и рёбер (дорог) между ними.
  • Ориентированный граф (орграф) — у каждого ребра есть направление, это дуга. На схеме показывается стрелкой.
  • Путь из A в B — последовательность вершин \(A = v_0, v_1, \dots, v_k = B\), в которой каждая соседняя пара соединена дугой в нужном направлении.
  • Длина пути — количество дуг в нём (а не количество путей!).
  • Различные пути различаются порядком вершин, даже если длина у них одинаковая.

В задании 1 граф почти всегда без циклов: стрелки идут «в одну сторону», поэтому путей конечное число и их можно честно посчитать.

Иногда граф дан не рисунком, а таблицей (матрицей смежности): если в строке \(i\) и столбце \(j\) стоит 1, значит есть дуга из \(i\) в \(j\).


2. Главная идея: динамическое программирование

Пусть \(f(v)\) — число путей из стартовой вершины \(A\) в вершину \(v\). Тогда:

\[ f(A) = 1, \qquad f(v) = \sum_{u \to v} f(u) \ \text{ для всех } v \neq A, \]

где суммирование идёт по всем вершинам \(u\), из которых есть дуга \(u \to v\).

Смысл простой: чтобы попасть в \(v\), путь должен последним шагом прийти из какого-то «входа» \(u\); каждый путь в \(u\) даёт ровно один путь в \(v\).

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


3. Порядок действий (алгоритм)

  1. Выписать все дуги графа (или все единицы матрицы).
  2. Упорядочить вершины так, чтобы все стрелки шли «вперёд». Если все стрелки на схеме идут слева направо по столбцам — просто идём по столбцам.
  3. Завести таблицу \(f\), положить \(f(A) = 1\).
  4. Идти по вершинам в выбранном порядке и для каждой считать сумму по входящим дугам.
  5. Ответ — \(f(B)\), где \(B\) — конечная вершина.

4. Пример с полной проверкой

Города А, Б, В, Г, Д, Е. Дороги (со стрелками): А→Б, А→В, Б→В, Б→Г, В→Г, В→Д, Г→Е, Д→Е. Сколько путей из А в Е?

Порядок: А, Б, В, Г, Д, Е.

Вершина Входящие дуги Расчёт \(f\)
А — старт 1
Б А→Б 1 1
В А→В, Б→В 1 + 1 2
Г Б→Г, В→Г 1 + 2 3
Д В→Д 2 2
Е Г→Е, Д→Е 3 + 2 5

Ответ: 5 путей.

Проверка «с конца»: пусть \(g(v)\) — число путей из \(v\) в Е.

\[ g(\text{Е}) = 1,\quad g(\text{Д}) = 1,\quad g(\text{Г}) = 1, \] \[ g(\text{В}) = g(\text{Г}) + g(\text{Д}) = 2,\quad g(\text{Б}) = g(\text{В}) + g(\text{Г}) = 3, \] \[ g(\text{А}) = g(\text{Б}) + g(\text{В}) = 5. \]

Совпало — 5. Такая обратная проверка ловит почти все ошибки в подсчёте.


5. Дополнительные условия в задании 1

«Путь проходит через город C». Считаем дважды: \[ N = f(C) \cdot g(C), \] где \(f(C)\) — число путей из А в C, \(g(C)\) — число путей из C в B. В примере выше через Г: \(3 \cdot 1 = 3\).

«Путь не проходит через C». Удалить вершину C вместе со всеми её дугами и посчитать заново (или из общего числа вычесть пути через C).

«Проходит ровно через один из городов C или D». Считать отдельно «через C» и «через D», а пути, идущие через оба, посчитать отдельно и не забыть, что они попали в оба слагаемых — аккуратно вычесть.

Запрещённая вершина как промежуточная. В таблице ставим \(f = 0\) для неё (но только если она не старт и не финиш).

Если в графе есть цикл — ДП «в лоб» не работает, нужен перебор или другой подход. В реальных вариантах задания 1 циклов не бывает.


6. Типичные ошибки

  • Забыли, что \(f(A) = 1\), а не 0.
  • Пропустили входящую дугу при суммировании (особенно «длинную», перечёркивающую схему).
  • Посчитали вершину раньше, чем все её входы (нарушили порядок).
  • Перепутали количество путей с длиной пути.
  • В условии «через C» умножили, но взяли \(f\) и \(g\) не от той вершины.
  • Сложили вместо умножения (или наоборот) при подсчёте «через вершину».

7. Что ещё полезно помнить

  • Для взвешенного графа (у дорог указаны длины) задача «кратчайший путь» решается алгоритмом Дейкстры или перебором — это другой тип задачи, в актуальном задании 1 его нет, но путать формулировки не стоит.
  • Число путей растёт быстро: если ответ получился «подозрительно маленьким» при ветвистом графе — перепроверьте таблицу.
  • Время на задание 1 — 2–4 минуты; аккуратная таблица \(f\) быстрее, чем перебор путей «руками».