Учебная статья

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

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

Зачем на экзамене

Задания 24, 25 и 26 проверяют умение превратить условие в работающую программу. В одном случае обрабатывается длинная строка, в другом исследуются целые числа, в третьем требуется выбрать или распределить объекты по правилам. Надежное решение начинается с точного описания проверяемого объекта и только затем превращается в цикл, условие и структуру данных.

Что нужно уметь

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

База

От условия к инварианту

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

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

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

Строки и последовательности

Для задания 24 полезны три основных схемы. Текущая серия подходит, когда допустимый фрагмент сбрасывается одним запрещенным символом. Скользящее окно используют, когда нужно найти самый длинный фрагмент с ограниченным количеством событий. Позиции вхождений удобны, когда условие связано с конкретной подстрокой или расстояниями между ее появлениями.

Формулировка	Обычно подходит	Что хранить
максимальная серия допустимых символов	один проход со сбросом	текущую и максимальную длину
не более k запрещенных символов	скользящее окно	левую границу и счетчик нарушений
ровно k вхождений образца	окно или список позиций	границы между соседними вхождениями
замена повторяется до остановки	цикл по правилу задачи	текущую строку и условие продолжения

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

Целые числа

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

Для поиска делителей достаточно проверять кандидаты от 1 до целой части квадратного корня. Если d делит n, то второй делитель равен n / d. Квадратный корень полного квадрата нужно добавить один раз.

d \mid n \Longrightarrow n=d\cdot\frac{n}{d}

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

Сортировка и жадный выбор

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

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

Задача	Возможная структура	Типичная сложность
один проход по строке	счетчики и границы	`O(n)`
поиск всех делителей одного числа	список или множество	`O(sqrt(n))`
упорядочивание записей	массив и сортировка	`O(n log n)`
частоты значений	словарь	в среднем `O(n)`

Чтение данных и границы

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

Границы циклов выводятся из определения кандидата. Для соседних пар из n элементов есть n - 1 начальных позиций. Для окна длины m: n - m + 1 окон. Пустой диапазон должен давать осмысленный результат, а не случайное начальное значение максимума.

Как решать

Строковая задача

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

Задача на целые числа

Запиши диапазон и признаки подходящего числа.
Раздели дешевые и дорогие проверки. Сначала применяй делимость, диапазон и простые ограничения.
Для делителей перебирай пары до квадратного корня и исключай дубли.
Сохраняй только те характеристики, которые требуются в ответе.
Проверь граничные числа, полные квадраты и отсутствие результата.

Обработка набора данных

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

Частые ошибки

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

Проверь себя

Сколько окон длины 4 есть в строке длины 10?
До какой границы достаточно перебирать делители числа?
Какая сложность у обычной сортировки n записей?
Почему нельзя удалять все пробелы по краям строки без проверки формата?

Ответы: 1) 7; 2) до целой части квадратного корня; 3) O(n log n); 4) пробел может быть значимым входным символом.

Связь с заданиями

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