ОП.04 · основы алгоритмизации и программирования · раздел 2 · массивы и последовательные техники
6 модулей
Техники, которые спрашивают
на алгоритмической секции
Раздел 2 курса — массивы, строки и последовательные техники: два указателя, скользящее окно, префиксные суммы, интервалы. Каждая тема раздела — отдельный модуль этой книги. Занятие 7 о массиве, индексах и границах уже есть в виде презентации, книга начинается с модуля 8.
Модули устроены одинаково. Сначала — где технику спрашивают и где она работает в программах, как звучат условия задач и какие вопросы задают до кода. Затем — сам алгоритм: перебор для сравнения, идея, ручное упражнение, пошаговый прогон настоящего кода, доказательство. В конце — типичные ошибки с прогонами, замер нескольких способов и практика по стартовому набору с тестами.
Весь код в книге — Python 3.12. Вывод программ, пошаговые прогоны и замеры получены запуском.
Номер модуля совпадает с номером занятия в календарно-тематическом плане. Модули 8, 9 и 10 готовы целиком, модули 11–12 пока показаны планом глав: они будут написаны по тому же образцу.
Адрес по индексу, полуинтервал, ошибки на единицу, инвариант прохода, изменение на месте и ёмкость списка. Презентация на пару и стартовый набор.
Указатели навстречу и в одну сторону: пара с заданной суммой, удаление повторов, сжатие, разделение на группы. Доказательство, ошибки и замер четырёх способов.
Окно длины k, добавление и удаление элемента, пересчёт суммы или счётчика за O(1), границы окна.
Условие допустимости, расширение правой границы, сжатие левой, минимальный и максимальный отрезок, частотная карта.
Префиксная сумма, полуинтервал [l, r), много запросов, баланс подготовки и ответа, обзор двумерного случая.
Представление интервала, пересечение, объединение, расписания и логистика, сортировка по началу и по концу.
Главы модуля идут в порядке изучения, но каждую можно открыть отдельно. Интерактивные блоки работают прямо на странице, без установки программ.
| Блок | Что с ним делать |
|---|---|
| Пошаговый прогон | Кнопка «шаг →» или стрелка вправо: подсвечивается строка кода, справа меняются переменные и указатели, снизу — объяснение шага. |
| Ручное упражнение | Решение на каждом шаге принимаете вы. Неверный ход не выполняется, вместо него появляется объяснение. |
| Таблица пар, счётчик, график | Показывают одно и то же с разных сторон: как алгоритм исключает варианты и сколько это стоит. |
| Песочница | Функция пишется прямо на странице и проверяется тестами. Python загружается в браузер при первом запуске, около 10 МБ, нужен интернет. |
| Python в этой строке | Раскрывающиеся подсказки у кода: как работает конструкция языка, с настоящим выводом интерпретатора. |
| Сборка кода из строк | Строки перемешаны, их нужно расставить по порядку стрелками или перетаскиванием. |
| Проверьте себя | После ответа открывается разбор выбранного и верного вариантов. |