Подготовка к ЕГЭ по информатике 2026: Полный курс

Теоретические основы: системы счисления, алгебра логики, графы и кодирование информации

Добро пожаловать в курс «Подготовка к ЕГЭ по информатике 2026». Мы начинаем наше путешествие не с написания кода, а с фундамента, на котором строится вся компьютерная наука. Без понимания того, как машина «думает» и хранит данные, невозможно решить значительную часть заданий экзамена (в частности, задания №1, 2, 4, 5, 7, 8, 11, 13 и 14).

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

Системы счисления

Компьютеры не понимают десятичную систему, к которой мы привыкли. Вся их работа основана на переключателях: ток есть (1) или тока нет (0). Поэтому основой всего является двоичная система счисления.

Позиционные системы

В ЕГЭ мы работаем с позиционными системами счисления. Это значит, что значение цифры зависит от её позиции (разряда) в числе. Например, в числе 11 первая единица означает десятку, а вторая — единицу.

Любое число в позиционной системе с основанием можно представить в развернутой форме:

Где:

— само число в системе счисления с основанием ;

— цифры числа (коэффициенты);

— основание системы счисления (например, 2, 8, 10, 16);

— количество разрядов в целой части числа;

степени () — это номера позиций цифр (справа налево, начиная с нуля для единиц).

Пример перевода из двоичной в десятичную: Возьмем число . Расставим индексы над цифрами справа налево: .

Где — исходное двоичное число, — основание системы, а — результат в десятичной системе.

Основные системы в ЕГЭ

Кроме двоичной, часто используются системы, основания которых являются степенями двойки. Это позволяет сокращать запись.

Двоичная (BIN): Алфавит {0, 1}.

Восьмеричная (OCT): Алфавит {0..7}. Одна цифра заменяет 3 бита ().

Шестнадцатеричная (HEX): Алфавит {0..9, A, B, C, D, E, F}, где A=10, F=15. Одна цифра заменяет 4 бита ().

!Схема взаимосвязи позиционных систем счисления

> Важно: В языке Python для перевода можно использовать функции bin(), oct(), hex() и int(string, base).

Алгебра логики (Булева алгебра)

Алгебра логики оперирует не числами, а высказываниями, которые могут быть либо Истинными (True, 1), либо Ложными (False, 0). Это основа задания №2 и №15.

Базовые операции

Инверсия (НЕ, , not): Меняет значение на противоположное.

- -

Конъюнкция (И, , and): Логическое умножение. Истинно только тогда, когда оба высказывания истинны.

- -

Дизъюнкция (ИЛИ, , or): Логическое сложение. Истинно, если хотя бы одно высказывание истинно.

- -

Импликация и Эквиваленция

Эти операции вызывают больше всего трудностей, но они критически важны.

Импликация (Следование, ): Формально: «Если А, то B». Ложна только в одном случае: когда из Истины следует Ложь.

Где — посылка (условие), — следствие, — отрицание посылки, — дизъюнкция.

| A | B | A B | |---|---|---| | 0 | 0 | 1 | | 0 | 1 | 1 | | 1 | 0 | 0 | | 1 | 1 | 1 |

Эквиваленция (Равносильность, или ): Истинна, когда значения А и B совпадают.

Где и — логические переменные, — конъюнкция, — дизъюнкция, — отрицание.

Приоритет операций

Если в выражении нет скобок, порядок действий следующий:

Инверсия (НЕ)

Конъюнкция (И)

Дизъюнкция (ИЛИ)

Импликация

Эквиваленция

Графы

Графы используются в заданиях №1 и №13 для моделирования дорог, сетей и связей.

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

Способы представления графа

Самый распространенный способ в экзамене — Матрица смежности (весовая матрица). Это таблица, где на пересечении строки и столбца стоит вес ребра, соединяющего соответствующие вершины.

!Граф и его представление в виде матрицы смежности

Основные понятия для задач

* Степень вершины: Количество ребер, выходящих из вершины. В таблице это количество заполненных ячеек в строке этой вершины. * Путь: Последовательность вершин, соединенных ребрами. * Дерево: Граф без циклов (замкнутых путей), где между любыми двумя вершинами существует ровно один путь.

Для решения задания №1 часто нужно сопоставить нарисованный граф и таблицу, опираясь на степени вершин (например, найти единственную вершину с 5 дорогами).

Кодирование информации

Этот раздел охватывает задания №4, 7, 8 и 11. Главная идея: любая информация (текст, звук, изображение) должна быть превращена в биты.

Формула Хартли

Основная формула, связывающая количество возможных вариантов (мощность алфавита) и количество бит, необходимых для их кодирования:

Где:

— количество равновероятных событий или мощность алфавита (сколько всего уникальных символов/цветов/уровней звука мы хотим закодировать);

— информационный вес одного символа (в битах).

> Если не является точной степенью двойки, то округляется в большую сторону до ближайшего целого. Например, чтобы закодировать 5 букв, нужно 3 бита ().

Объем информации

Общий объем сообщения вычисляется просто:

Где:

— информационный объем сообщения (в битах);

— количество символов в сообщении (или пикселей в изображении, или отсчетов в звуке);

— глубина кодирования (вес одного символа/пикселя).

Условие Фано

В задании №4 используется неравномерное кодирование (разные символы имеют коды разной длины). Чтобы такое сообщение можно было однозначно декодировать, должно выполняться Условие Фано:

> Никакое кодовое слово не может быть началом (префиксом) другого кодового слова.

Пример:

Коды 0 и 01 — нарушают условие Фано (так как 0 — начало 01). Мы не поймем, где закончился первый символ.

Коды 1, 01, 00 — соблюдают условие Фано.

Для проверки условия Фано удобно строить бинарное дерево.

!Бинарное дерево для проверки условия Фано

Заключение

Мы рассмотрели теоретический базис. Системы счисления позволяют нам понимать данные, логика учит строить условия, графы помогают находить пути, а формулы кодирования — рассчитывать объемы памяти. В следующих статьях мы начнем применять эти знания на практике для решения конкретных номеров ЕГЭ.

Теперь перейдем к домашнему заданию, чтобы закрепить материал.

Обработка данных и офисное ПО: электронные таблицы, базы данных и поиск информации

В предыдущей статье мы заложили теоретический фундамент: разобрались с битами, графами и логикой. Теперь пришло время перейти к инструментам, с которыми вы будете работать непосредственно на экзамене. Значительная часть заданий ЕГЭ (№3, 9, 10, 18 и частично 22) решается не программированием на Python, а с помощью офисного пакета: текстового редактора и электронных таблиц (Microsoft Office или LibreOffice).

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

Поиск информации в текстовых документах (Задание №10)

Задание №10 проверяет ваше умение пользоваться средствами поиска в операционной системе или текстовом редакторе. Обычно вам дается файл (Word, PDF или текстовый документ) и требуется найти, сколько раз встречается определенное слово, или найти информацию о конкретном персонаже.

Основные принципы поиска

Главный инструмент здесь — диалоговое окно «Найти» (вызывается сочетанием клавиш Ctrl + F или Ctrl + H для расширенного поиска).

При поиске важно учитывать два параметра:

Регистр (Case Sensitivity): Различает ли поиск «Дом» и «дом». В заданиях ЕГЭ часто просят найти слово с маленькой буквы или в любом регистре.

Только слово целиком (Whole words only): Это критически важная настройка. Если вы ищете слово «он», компьютер без этой галочки найдет его и в словах «оно», «слон», «пончик». Если в задании требуется найти местоимение «он», обязательно включайте опцию «Только слово целиком».

> Внимательно читайте условие: нужно ли считать сноски? Нужно ли учитывать падежные окончания? От этого зависит стратегия поиска.

Электронные таблицы (Задания №9 и №18)

Электронные таблицы (Excel, Calc) — мощнейший инструмент для анализа данных. В ЕГЭ они используются для обработки числовых последовательностей (№9) и динамического программирования (№18).

Адресация ячеек

Ячейка — это основной элемент таблицы, имеющий адрес (например, A1, B5). Адресация бывает двух типов:

Относительная (A1): При копировании формулы ссылка меняется. Если в ячейке B1 записана формула =A12, то при копировании её вниз в B2, формула автоматически превратится в =A22.

Абсолютная (1): Ссылка фиксируется знаком доллара A1 фиксирует столбец, а Aa, b, ca, b, c\land>S_{i,j}(i, j)C_{i,j}(i, j)S_{i-1,j}S_{i,j-1}\max$ — функция выбора максимального значения (выбираем лучший путь).

В Excel это реализуется буквально за минуту копированием одной формулы на весь диапазон.

Базы данных (Задание №3)

Задание №3 проверяет понимание реляционных баз данных. Вам обычно предоставляется файл Excel с несколькими листами (таблицами), связанными между собой.

Реляционная модель данных

Реляционная база данных — это набор таблиц, связанных друг с другом через ключевые поля.

* Первичный ключ (Primary Key, ID): Уникальный идентификатор записи в таблице (например, ID товара или ID магазина). Он не может повторяться. * Внешний ключ (Foreign Key): Поле, которое ссылается на первичный ключ другой таблицы. Именно так создаются связи.

!Схема реляционной базы данных: связь таблиц через ключевые поля.

Решение задания №3 средствами Excel

Чаще всего задача звучит так: «Используя информацию из приведённой базы данных, определите общую выручку от продажи товара X в магазинах района Y».

У нас есть три таблицы:

Движение товаров (Дата, ID магазина, Артикул, Количество, Тип операции, Цена).

Товары (Артикул, Название, Отдел, Поставщик).

Магазины (ID магазина, Район, Адрес).

Чтобы решить задачу, нам нужно собрать данные в одну таблицу. Для этого используется функция ВПР (VLOOKUP).

Синтаксис функции: =ВПР(искомое_значение; таблица; номер_столбца; интервальный_просмотр)

Искомое значение: ID, по которому ищем (например, Артикул из первой таблицы).

Таблица: Диапазон второй таблицы, где хранится информация (например, таблица Товары).

Номер столбца: Порядковый номер столбца во второй таблице, откуда нужно забрать данные (например, название района).

Интервальный просмотр: Всегда ставим 0 (или ЛОЖЬ`) для точного совпадения.

После того как мы «подтянули» Район и Название товара в главную таблицу с помощью ВПР, остаётся только воспользоваться Фильтром (Данные -> Фильтр), чтобы выбрать нужный район и товар, а затем просуммировать значения.

Сортировка и Фильтрация

Эти инструменты полезны как в №3, так и в №9.

* Сортировка: Упорядочивание данных по возрастанию или убыванию. Помогает быстро найти минимум/максимум или сгруппировать данные. * Фильтр: Отображение только тех строк, которые соответствуют критерию (например, «Цена > 1000»).

Заключение

Офисное ПО в ЕГЭ — это не про красивое оформление документов, а про аналитику. Электронные таблицы позволяют решать задачи, которые вручную заняли бы часы, за несколько минут. Главное — понимать логику адресации и уметь связывать данные из разных источников.

В следующей статье мы перейдем к самому объемному блоку курса — программированию на Python, начав с базового синтаксиса и типов данных.

Алгоритмизация и программирование: базовые конструкции, работа со строками и массивами

Мы переходим к самому обширному и важному блоку курса — программированию. Если теоретические основы (системы счисления, логика) и офисное ПО дают около 30-40% баллов на ЕГЭ, то умение программировать открывает доступ к решению заданий №5, 6, 12, 14, 15, 16, 17, 23, 24, 25, 26 и 27. Это «тяжелая артиллерия» экзамена.

В качестве основного языка мы будем использовать Python. Это стандарт де-факто для ЕГЭ благодаря лаконичному синтаксису и мощной стандартной библиотеке. В этой статье мы разберем фундамент: переменные, условия, циклы и структуры данных.

Переменные и типы данных

В Python не нужно заранее объявлять тип переменной (это называется динамической типизацией). Тип определяется в момент присваивания значения.

Основные типы данных для ЕГЭ

Целые числа (int): Числа без дробной части. В Python они имеют неограниченную длину (можно хранить хоть 1000-значное число), что критически важно для заданий №14 и №25.

Вещественные числа (float): Числа с плавающей точкой. Разделитель — точка (например, 3.14).

Логический тип (bool): Принимает всего два значения: True (Истина) и False (Ложь). Результат работы логических операций.

Строки (str): Последовательности символов в кавычках.

Ввод и вывод данных

Для вывода информации на экран используется функция print(), а для ввода — input().

> Важно: Функция input() всегда возвращает строку. Если вам нужно работать с числом, результат ввода необходимо явно преобразовать с помощью int() или float().

Арифметика и целочисленное деление

Стандартные операции: + (сложение), - (вычитание), * (умножение), / (обычное деление, всегда возвращает float).

Однако в ЕГЭ (особенно в заданиях №5, 12, 14) королями являются две другие операции:

Целочисленное деление (//): Отбрасывает дробную часть.

Остаток от деления (%): Возвращает остаток.

Математически это записывается так:

Где:

— делимое;

— делитель;

— неполное частное (результат операции //);

— остаток (результат операции %).

Пример:

С помощью этих операций мы можем «разбирать» числа на цифры. Например, x % 10 — это последняя цифра числа, а x // 10 — отсечение последней цифры.

Условные конструкции

Условия позволяют программе принимать решения. Синтаксис в Python опирается на отступы (обычно 4 пробела).

Логические связки

Здесь нам пригодятся знания из статьи про алгебру логики: * and — логическое И (конъюнкция); * or — логическое ИЛИ (дизъюнкция); * not — логическое НЕ (инверсия).

Пример проверки попадания в диапазон :

Циклы

Циклы позволяют выполнять блок кода многократно. Это основа перебора вариантов в заданиях №2, 8, 15, 25.

Цикл while

Выполняется, пока условие истинно. Используется, когда мы не знаем точное количество итераций заранее (например, пока число не станет равно нулю).

Цикл for

Используется для перебора последовательностей или выполнения кода заданное число раз. Работает в связке с функцией range().

Синтаксис range(start, stop, step):

start — начало (включительно, по умолчанию 0);

stop — конец (не включительно);

step — шаг (по умолчанию 1).

Работа со строками

Строки в Python — это неизменяемые последовательности символов. Это значит, что нельзя изменить конкретный символ по индексу, можно только создать новую строку.

Индексация и срезы

Каждый символ имеет индекс. Нумерация начинается с нуля. Отрицательные индексы позволяют обращаться с конца строки (-1 — последний символ).

!Визуализация прямой и обратной индексации в строках.

Срезы (Slicing) позволяют извлекать подстроки. Формат: строка[start:stop:step].

Методы строк для ЕГЭ

Для задания №12 (Исполнитель Редактор) и №24 (Обработка строк) критически важны следующие методы:

s.count(sub) — считает количество вхождений подстроки sub.

s.replace(old, new, count) — заменяет вхождения old на new. Параметр count (сколько раз заменить) необязателен, но в задании №12 часто нужно заменять только первое вхождение (count=1).

s.find(sub) — возвращает индекс первого вхождения или -1, если не найдено.

Пример (аналог задания №12):

Списки (Массивы)

Список (list) — это упорядоченная изменяемая коллекция объектов. В отличие от массивов в Pascal или C++, список в Python может содержать данные разных типов и динамически менять размер.

Создание и доступ

Генераторы списков (List Comprehensions)

Мощный инструмент для создания списков в одну строку. Часто используется для считывания данных из файла в задании №17.

Методы списков

append(x) — добавляет элемент x в конец списка.

sort() — сортирует список по возрастанию. Важно для поиска медианы или наибольших элементов.

len(lst) — возвращает длину списка (количество элементов).

sum(lst), min(lst), max(lst) — сумма, минимум и максимум списка.

Пример решения задачи (прототип №17)

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

Заключение

Мы рассмотрели базовый синтаксис Python. Эти конструкции — кирпичики, из которых строятся решения сложных задач. Переменные хранят состояние, условия управляют потоком, циклы выполняют рутинную работу, а списки и строки организуют данные.

В следующей статье мы углубимся в тему функций и работы с файлами, что необходимо для решения заданий №17, 24, 26 и 27, где данные берутся не из ввода, а из текстовых документов.

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

В предыдущей статье мы освоили базовый синтаксис Python: переменные, циклы и списки. Теперь мы готовы применить эти инструменты для решения одного из самых интересных и «дорогих» блоков ЕГЭ — заданий №19, 20 и 21, посвященных теории игр, а также задания №16 на рекурсию.

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

Что такое рекурсия?

Прежде чем переходить к играм, разберем инструмент, который лежит в основе их анализа — рекурсию. Это понятие необходимо для задания №16 и является ключом к решению задач теории игр.

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

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

Структура рекурсивной функции

Любая правильная рекурсивная функция состоит из двух частей:

Базовый случай (условие остановки): Ситуация, когда функция выдает результат сразу, без повторного вызова самой себя.

Рекурсивный шаг: Вызов функцией самой себя с измененными аргументами, приближающими нас к базовому случаю.

Рассмотрим классический пример — вычисление факториала числа . Математически это записывается так:

Где:

— факториал числа (произведение всех чисел от 1 до );

— результат для базового случая;

— рекурсивный шаг.

Реализация на Python:

В ЕГЭ задание №16 часто требует просто переписать математическую формулу в код. Однако, если глубина рекурсии слишком велика (например, ), обычный вызов приведет к ошибке. Здесь на помощь приходит мемоизация (запоминание результатов), о которой мы поговорим чуть позже.

Основы теории игр в ЕГЭ

Задания №19, 20 и 21 объединены одним сюжетом. Обычно это игра с камнями для двух игроков. Назовем их Петя (ходит первым) и Ваня (ходит вторым).

Правила игры

Есть одна или две кучи камней.

Игроки ходят по очереди.

За один ход игрок может изменить количество камней (например, добавить 1 камень или увеличить количество в 2 раза).

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

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

Дерево игры

Чтобы проанализировать все возможные исходы, строят дерево игры. Это граф, где вершинами являются состояния (количество камней), а ребрами — возможные ходы.

!Графическое представление возможных ходов из начальной позиции 5 при условии победы >= 12.

Выигрышные и проигрышные позиции

Это фундаментальные понятия для решения задач.

* Выигрышная позиция: Позиция, из которой существует хотя бы один ход, ведущий в проигрышную позицию для соперника. Игрок, находящийся в выигрышной позиции, владеет выигрышной стратегией. * Проигрышная позиция: Позиция, из которой все возможные ходы ведут в выигрышные позиции для соперника. То есть, как бы игрок ни старался, он своим ходом лишь «подставится» под удар.

Формализуем это с помощью логики:

* Позиция выигрышная, если . * Позиция проигрышная, если .

Где:

— текущая позиция (количество камней);

— множество возможных ходов из позиции ;

— статус позиции, в которую мы попадаем после хода ;

— квантор существования («существует»);

— квантор всеобщности («для всех»).

Программное решение задач №19-21

Ручное построение дерева занимает много времени и чревато ошибками. Python позволяет решить эти задачи за считанные минуты, используя рекурсию.

Мы напишем функцию, которая будет моделировать игру. Пусть у нас есть одна куча, ходы +1 и *2, победа при .

Универсальная функция игры

Однако такой подход может быть сложен для понимания новичками. Существует более простой метод для ЕГЭ, основанный на определении победителя для каждой позиции.

Метод «Кто выигрывает?»

Давайте напишем функцию solve(s, p), где s — количество камней, а p — счетчик ходов. Функция будет возвращать True, если игрок, который должен сделать ход p, выигрывает при правильной игре.

Но для ЕГЭ удобнее проверять конкретные условия задач. Рассмотрим шаблонное решение для трех типов заданий.

Условие примера: Куча камней. Ходы +1, *2. Победа: . Игра завершается. Петя — 1-й ход, Ваня — 2-й ход, Петя — 3-й, Ваня — 4-й.

Теперь адаптируем это под конкретные вопросы.

Задание №19: Ваня выигрывает первым ходом

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

Это значит:

Петя делает ход (любой).

После хода Пети камней становится столько, что Ваня одним ходом достигает .

В терминах ходов: Победа происходит на шаге 2 (ход Вани).

Задание №20: Петя выигрывает вторым ходом

Условие: «Петя не может выиграть за 1 ход, но выигрывает своим вторым ходом (независимо от того, как сходит Ваня)». То есть победа на шаге 3.

Логика:

Петя (ход 1) делает выигрышный ход (существует такой ход — any).

Ваня (ход 2) делает любой ход (все ходы проигрышные — all).

Петя (ход 3) побеждает.

Задание №21: Ваня выигрывает 1-м или 2-м ходом

Условие: «У Вани есть стратегия, позволяющая выиграть первым или вторым ходом, но нет гарантии выиграть первым». Победа на шаге 2 или 4.

Здесь логика сложнее. Если Ваня может выиграть сразу (шаг 2) — отлично. Если нет, он должен свести игру к ситуации, где он выиграет на шаге 4, как бы ни сопротивлялся Петя.

> Важно: В задании 21 часто просят найти минимальное или максимальное значение. Иногда нужно исключить те значения, которые подходят под условие «Ваня выигрывает гарантированно первым ходом» (то есть решение задачи 19), если формулировка задачи это подразумевает.

Динамическое программирование и Мемоизация

При решении задач с двумя кучами камней дерево игры разрастается экспоненциально. Обычная рекурсия может работать медленно, так как она многократно вычисляет одно и то же состояние (например, позиция (10, 15) может быть достигнута разными путями).

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

В Python это делается очень просто с помощью декоратора @lru_cache из модуля functools.

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

Заключение

Мы разобрали, как с помощью рекурсии моделировать игровые процессы. Главный секрет успеха в заданиях 19-21 — внимательно читать условие (кто ходит, какие ходы, условие победы) и правильно расставлять кванторы any (существует ход) и all (для любого хода) в зависимости от того, чей сейчас ход и чью победу мы моделируем.

В следующей статье мы перейдем к работе с целочисленной арифметикой и алгоритмам теории чисел, которые понадобятся для задания №25.

Задачи высокого уровня сложности: эффективные алгоритмы обработки больших данных и перебор

Мы подошли к кульминации нашего курса. Если предыдущие темы обеспечивали вам надежную базу и около 70-80 баллов, то материал этой статьи — это ключ к 90+ и 100 баллам. Речь пойдет о заданиях №26 и №27, а также о сложных вариациях задания №24.

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

Понятие сложности алгоритма

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

Это записывается с помощью «О-большого» — .

Почему перебор не всегда работает?

Представьте, что в задании №27 вам дано чисел, и нужно найти пару чисел с определенными свойствами. Самое простое решение — перебрать все возможные пары (первое число со вторым, первое с третьим и т.д.).

Количество пар вычисляется по формуле сочетаний, но грубо говоря, это вложенный цикл:

Сложность такого алгоритма — квадратичная, или .

Где:

— количество элементов;

— количество операций в квадратичном алгоритме.

Python выполняет примерно операций в секунду. Для программа отработает за пару секунд. Но в файле B задания №27 обычно или даже больше. Тогда операций, что займет несколько часов или дней. Такой алгоритм не подходит.

Нам нужны линейные алгоритмы со сложностью , которые делают один проход по данным.

!Сравнение роста времени выполнения для линейного и квадратичного алгоритмов.

Задание №26: Сортировка и жадные алгоритмы

Задание №26 обычно моделирует ситуацию, где нужно оптимально распределить ресурсы: заполнить диск файлами, рассадить людей в кинотеатре или выбрать товары на складе.

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

Пример задачи (Архив данных)

Условие: Есть диск объемом и пользователей, которые хотят сохранить свои файлы. Известен размер каждого файла. Нужно сохранить файлы максимального количества пользователей. При равенстве количества — выбрать вариант, где самый большой файл имеет максимальный размер.

Логика решения: Чтобы уместить как можно больше файлов, нужно брать самые маленькие. Если мы возьмем один большой файл на 100 ГБ, мы займем место, где могли бы лежать сто файлов по 1 ГБ.

Алгоритм:

Считать все числа в список.

Отсортировать список по возрастанию.

Брать файлы по порядку, пока сумма не превысит .

> Важно: Вторая часть задания (максимизировать размер самого большого файла) требует небольшой модификации: когда место почти кончилось, мы пробуем заменить последний взятый файл на более крупный, который тоже влезает в остаток места.

Задание №27: Эффективная обработка потока данных

Это самое сложное задание экзамена. Обычно оно формулируется так: дана последовательность чисел, нужно найти пару (или тройку, или подпоследовательность), сумма которой делится на , или максимальна, или удовлетворяет другим условиям.

Главный принцип решения: не хранить все данные, а хранить только то, что влияет на ответ.

Метод остатков

Допустим, нам нужно найти пару чисел , сумма которых делится на 14, а сама сумма максимальна.

Математическое свойство делимости суммы:

Где:

— слагаемые;

— делитель;

— знак сравнения по модулю (равенство остатков);

— операция взятия остатка от деления на .

Это значит, что нам важны не сами числа, а их остатки от деления на . Если число дает остаток 5 при делении на 14, то ему в пару нужно число , которое дает остаток . Только тогда , что делится на 14.

Алгоритм:

Создадим массив remains длиной (в нашем примере 14), где будем хранить максимальное число, которое мы встретили с соответствующим остатком.

Читаем числа по одному.

Для каждого числа вычисляем его остаток .

Ищем пару: нам нужно число с остатком . Если такое число уже есть в массиве remains, проверяем сумму.

Обновляем массив remains: если текущее число больше того, что уже лежит в ячейке remains[r], заменяем его.

Таким образом, мы делаем всего один проход по данным. Сложность .

!Визуализация метода накопления данных по остаткам для задачи №27.

Префиксные суммы

Если задача требует найти непрерывную подпоследовательность с определенной суммой, используется метод префиксных сумм.

Префиксная сумма — это сумма всех элементов от начала последовательности до индекса .

Где:

— сумма элементов подпоследовательности с индекса по ;

— префиксная сумма до конца подпоследовательности;

— префиксная сумма до начала подпоследовательности.

Если нам нужно, чтобы сумма на отрезке делилась на , то:

То есть, нам нужно найти два таких префикса, которые имеют одинаковый остаток от деления на . Задача сводится к подсчету количества префиксов с каждым остатком.

Задание №24: Обработка символьных строк

В задании №24 часто требуется найти самую длинную цепочку символов, удовлетворяющую условию (например, нет двух одинаковых букв подряд).

Здесь также используется линейный проход ().

Пример: Найти длину самой длинной подстроки, состоящей только из символов 'A'.

Если условие сложнее (например, запрещены пары "AB"), логика else меняется, но принцип "один проход — один счетчик" остается.

Работа с файлами большого объема

В задачах 24, 26, 27 данные берутся из файлов. Важно уметь правильно их читать.

f.read() — считывает весь файл в одну строку. Удобно для №24.

f.readlines() — считывает все строки в список. Удобно для №26, если данных не критически много.

Итерация по файлу (for line in f:) — самый экономный способ памяти. Мы считываем строку, обрабатываем её и тут же забываем. Идеально для №27 (файл B).

Заключение

Задачи высокого уровня сложности требуют смены мышления. Вместо вопроса «Как мне перебрать все варианты?» вы должны задавать вопрос «Какую закономерность я могу использовать, чтобы не делать лишнюю работу?». Сортировка, жадные алгоритмы, анализ остатков и префиксные суммы — это инструменты, превращающие часы вычислений в миллисекунды.

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