МДК 01.04 · 3 курс · 6 семестр

Системное программирование за два дня

Учебник для подготовки к дифференцированному зачёту: основы C, все 30 теоретических вопросов и 23 актуальных типа практических задач (№ 2–24) с решениями.

Начни с плана. Пиши код до открытия решения. Возвращайся к ошибкам на следующий день.

Содержание

Как готовиться эти два дня

Обновление от 29 октября: в практической части теперь две задачи. Преподаватель исключил № 1 (динамический массив) и № 25 (ОПЗ). Готовимся к 23 типам: № 2–24. Номера сохранены как в исходном документе.

Новые время и оценивание не уточнены. Старые 45 минут и 30 баллов не используем как действующий регламент. Теория сохранена отдельно; в пробнике её можно включить.

Один подход: посмотри → заполни пропуски → напиши по памяти → собери полную программу и запусти. После нескольких подходов отдохни 10–15 минут.

Не нужно читать всё подряд. На первом дне — основные приёмы, на втором — слабые места и билеты из двух задач. Вероятность выпадения отдельных задач неизвестна.

День первый

  1. Начни с короткого. № 3, 2, 23: копирование, обратный обход, замена символа. Пойми *p и p++.
  2. Числа. № 8, 15, 21, 10, 11: факториал, цифры, НОД, НОК. Для каждой — обычный вход и граница.
  3. Ещё числа. № 9, 12, 13, 14, 16: пара Фибоначчи, делители, степень, двоичная запись.
  4. Массивы. № 5, 7, 24: два указателя, обмен, границы бинарного поиска.
  5. Память. № 4 и 6: слияние и матрица. Запомни размер выделения, проверку NULL и free.
  6. Закрепи. Напиши две пройденные задачи с чистого листа. Запусти и запиши три ошибки. Теорию открывай по непонятному понятию.

День второй

  1. Вспомни вчерашнее. Без чтения: copy_array, factorial, gcd. Исправь свои три ошибки.
  2. Предикаты. № 17–19: поиск, фильтр, partition. Объясни, когда двигается выходной указатель.
  3. Строки и скобки. № 20 и 22. Повтори № 23. Стек проверяет последнюю открытую скобку.
  4. Слабые места. Перепиши два фрагмента, где ошибался. Затем собери полные программы.
  5. Пробник. Две разные задачи из № 2–24. На экране одна задача за раз. Время измеряется для тебя, официальный лимит не задан.
  6. Разбор. Скомпилируй обе программы. Проверь обычные и граничные входы. Исправь ошибки и попробуй ещё один билет. Перед зачётом — краткое повторение и отдых.

Если осталось всего несколько часов

Если осталось 4 часа: 40 минут — указатели и № 2, 3, 5, 23; 40 — числа; 40 — слияние, матрица и поиск; 30 — предикаты и скобки; 60 — две задачи без подсказок; 30 — разбор ошибок. Это учебный график, не время зачёта. Он не даёт одинаково глубокой подготовки ко всем 23 типам. Теорию смотри по непонятным местам.

Минимальный C перед указателями

int хранит целое число, char — символ, size_t — неотрицательный размер объекта или количество элементов. unsigned long long нужен для больших неотрицательных результатов. Знак = присваивает, == сравнивает. В условии 0 означает ложь, ненулевое — истину. return завершает функцию и передаёт результат вызывающему коду.

#include <stdio.h>

int sum_to(int n) {
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += i;
    }
    return sum;
}

int main(void) {
    printf("%d\n", sum_to(5)); // 15
    return 0;
}

Цикл for: сначала один раз создать i, затем перед каждым шагом проверить условие, выполнить тело и увеличить i. while повторяет тело, пока условие истинно. break выходит из цикла, continue начинает следующий шаг. Здесь предполагается небольшой n, при котором сумма помещается в int.

Массив int a[]={10,20,30}; имеет три элемента. Их индексы 0, 1, 2. Длина отдельно передаётся в функции: указатель сам её не знает. sizeof a / sizeof *a даёт число элементов настоящего массива в той области, где он объявлен; внутри функции с параметром int* это уже не длина массива.

Указатели без магии

Представь три ячейки с условными адресами 1000, 1004, 1008 и числами 10, 20, 30. Это иллюстрация для sizeof(int)=4, а не обещание реальных адресов. p хранит адрес ячейки. *p означает её содержимое. &x даёт адрес x.

int a[] = {10, 20, 30};
int *p = a;     // первый элемент
*p = 11;        // теперь a: 11, 20, 30
++p;            // p у второго элемента
(*p)++;         // теперь a: 11, 21, 30
int x = *p++;   // x=21, p у третьего элемента

Звёздочка в int *p объявляет тип указателя; звёздочка в *p=11 разыменовывает его. *(a+i) и a[i] обозначают тот же элемент. В ряде заданий требуют первую запись, чтобы проверить понимание адресов.

Граница: если длина n, допустимые элементы от a до a+n-1. a+n можно хранить и сравнивать как конец, но нельзя читать. a-1 вообще не формируй. Для пустого массива выходи до вычисления arr+n, если arr может быть NULL. Указатель на уже освобождённый блок тоже нельзя разыменовывать.

Проверь себя: после кода выше x=21, *p=30, а массив равен 11,21,30. Если не можешь объяснить каждую строку, ещё раз пройди её с рисунком трёх ячеек.

Память и структуры с нуля

У обычного массива размер выбран при создании. Если он выяснится во время работы, просишь блок у аллокатора. sizeof *p автоматически использует размер нужного типа; приведение результата malloc в C не требуется.

#include <stdlib.h>
#include <stdint.h>

size_t n = 10;
if (n > SIZE_MAX / sizeof(int)) return 1;
int *p = malloc(n * sizeof *p);
if (p == NULL) return 1;
for (size_t i = 0; i < n; ++i) *(p + i) = 0;
// пользоваться p можно здесь
free(p);
p = NULL;

Этот фрагмент вставляется внутрь main после заголовков. После malloc элементы не инициализированы: перед чтением запиши значения. free вызывается для начала выделенного блока, не для p+1. После free объект перестаёт существовать; присваивание p=NULL не исправляет другие копии указателя.

Структура объединяет поля: typedef struct { int *data; size_t length, capacity; } DynArray;. У обычной переменной поля доступны через a.length. Если p указывает на структуру, p->length означает (*p).length. В push передаётся адрес структуры, чтобы функция могла изменить её поля.

При росте: новый размер → проверка → tmp=realloc(...) → проверка tmp → замена указателя. Если realloc не удался при ненулевом размере, старый блок остаётся у тебя. Размер нельзя считать умножением без проверки: size_t тоже способен переполниться.

Строки и ввод

Строка C — последовательность char, заканчивающаяся '\0'. Для текста cat нужны четыре байта: c, a, t и нуль. char s[]="cat"; создаёт изменяемый массив. Строковый литерал через указатель изменять нельзя.

int n;
if (scanf("%d", &n) != 1) return 1;
printf("n=%d\n", n);

char line[256];
if (fgets(line, sizeof line, stdin) != NULL) {
    // fgets может сохранить перевод строки
}

Это два отдельных шаблона ввода. Если сразу после scanf вызвать fgets, он может прочитать оставшийся перевод строки; для строковой задачи проще использовать только fgets. Для int печать %d, size_t — %zu, unsigned long long — %llu, long long — %lld. В scanf для переменной нужен её адрес; массив символов уже обычно передаётся как адрес первого элемента.

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

Семь шаблонов вместо двадцати пяти отдельных задач

  1. Линейный обход. Повторить n раз: прочитать *p, выполнить действие, ++p. Копирование, поиск, фильтрация, замена.
  2. Два края. left и right движутся навстречу; сначала проверить пустоту. Палиндром.
  3. Два входа и один выход. Сравнивать текущие элементы и переносить меньший. Слияние.
  4. Накопитель. Начальное значение плюс действие в цикле. Факториал, сумма цифр, переворот, степень.
  5. Уменьшение задачи. Остаток Евклида, деление числа на основание, деление степени или диапазона пополам.
  6. Граница готовой части. Всё до указателя уже правильно. Фильтр, partition, пузырёк с закреплённым хвостом.
  7. Стек. Последним положили — первым достали. Скобочная последовательность.

Перед кодом скажи одну фразу: «что уже правильно после каждого шага». Это инвариант. Для фильтра: первые count элементов результата — все подходящие из просмотренной части. Для бинарного поиска: если цель есть, она остаётся в [left,right).

Как запускать и проверять

Самый быстрый старт — OnlineGDB для C. Выбери C, вставь один полный .c файл из комплекта и нажми Run. Для задачи о буквах введи, например, Hello, C! в stdin. Остальные файлы сами вызывают функции на примерах. Не вставляй все 25 файлов в одну программу: в каждом есть собственный main.

gcc -std=c11 -Wall -Wextra -Wpedantic -O0 -g 03_copy_array.c -o task
# Linux или macOS
./task
# PowerShell в Windows с установленным GCC
.\task.exe

Команда GCC предполагает уже установленный компилятор. Не трать первый вечер на настройку сложной среды, если браузерный запуск доступен. Для проверки памяти в поддерживаемой среде можно собрать с -fsanitize=address,undefined; доступность зависит от компилятора и ОС.

assert — проверка ожидания: при ложном условии программа прерывается. В учебных main это готовые мини тесты, а не алгоритм решения. errno=ERANGE в ряде функций означает, что результат вне принятого диапазона. Перед проверкой ошибки поставь errno=0: успешная функция не обязана его очищать.

Сайт сохраняет черновики и отметки в текущем браузере. Он не компилирует произвольный C: скачай черновик или скопируй его в компилятор. Автоматические тесты здесь проверяют выбранные ответы по теории; оценка свободного кода остаётся за компилятором и твоими тестами.

Как действовать на зачёте

Практика — две задачи. Быстро прочитай обе и начни с более понятной. Для каждой: вход и выход → границы → алгоритм → код → проверка.

Пиши сначала знакомый каркас. Для указателей проверь границы, для памяти — NULL и free, для чисел — диапазон. Не заменяй условие задачи удобным упрощением.

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

Новые время и баллы не уточнены. Пробник измеряет затраченное время и сохраняет черновики, но не выставляет оценку. Если теория тоже остаётся, включи два вопроса в настройке пробника и отвечай: определение → механизм → пример → ограничение.

Памятка перед зачётом

Тридцать вопросов по теории

Сначала прочитай простое объяснение. Затем закрой текст и напиши ответ по памяти. Раздел «Ответ для зачёта» — компактная заготовка, которую нужно понимать, а не воспроизводить механически.

1 Архитектура фон Неймана

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

Ответ для зачёта

Архитектура фон Неймана основана на хранении команд и данных в общей адресуемой памяти. Основные компоненты: процессор с арифметико логическим устройством, устройством управления и регистрами; память; устройства ввода и вывода; связи между ними. Счётчик команд указывает, откуда взять следующую инструкцию. Цикл работы включает выборку, декодирование и исполнение. Команды обычно идут последовательно, а переходы меняют порядок. Обмен процессора с памятью ограничивает производительность — это узкое место фон Неймана.

Пример. Загрузить два числа из памяти → сложить в АЛУ → сохранить результат.

Не перепутай. Не путай память с процессором. У современных CPU кэши команд и данных могут быть раздельными, хотя модель памяти программы остаётся общей.

Самопроверка. Назови пять компонентов и три стадии исполнения.

Ключ: Процессор, память, ввод, вывод, связи; выборка, декодирование, исполнение.

2 Конвейеризация

Просто. Как конвейер на кухне: пока один заказ готовят, второй нарезают, третий принимают. Несколько команд находятся на разных стадиях одновременно.

Ответ для зачёта

Конвейер делит исполнение команды на стадии, например выборку, декодирование, выполнение, доступ к памяти и запись результата. Стадии разных команд перекрываются во времени. После заполнения конвейера повышается пропускная способность, но задержка одной команды не обязана уменьшаться. Мешают конфликты по данным, ресурсам и управлению. Используют остановки, перенаправление результатов и предсказание переходов. Ошибка предсказания требует сбросить неверно начатые команды и теряет такты.

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

Не перепутай. Конвейеризация и суперскалярность — разные способы ускорения.

Самопроверка. Почему ветвление может замедлить конвейер?

Ключ: Нужно знать следующий адрес; ошибочно выбранный путь сбрасывается.

3 Регистры процессора

Просто. Регистры — маленькие рабочие ячейки прямо в процессоре. Память хранит много данных, регистры держат то, с чем CPU работает сейчас.

Ответ для зачёта

Регистры дают быстрый доступ к операндам и состоянию процессора. Регистры общего назначения хранят числа, адреса и промежуточные результаты. Счётчик команд хранит адрес следующей инструкции, указатель стека — положение вершины стека. Регистр флагов содержит признаки результата, например нуль, перенос и знак, а также управляющие биты. Сегментные регистры x86 связаны с сегментной организацией памяти. Это классификация по назначению, а не универсальная иерархия скоростей. В иерархии хранения регистры находятся ближе к вычислениям, чем кэши и ОЗУ.

Пример. После сравнения чисел условный переход использует флаги.

Не перепутай. Устройство сегментных регистров зависит от архитектуры и режима CPU.

Самопроверка. Чем регистр флагов отличается от регистра общего назначения?

Ключ: Хранит признаки и управление, а не произвольный операнд программы.

4 Тактовая частота

Просто. Частота показывает количество тактов в секунду, но не количество готовых полезных команд. На результат влияют и работа за такт, и ожидание памяти.

Ответ для зачёта

Тактовая частота — число тактов процессора в секунду, измеряемое в герцах. При прочих равных повышение частоты уменьшает время выполнения. Приближённо время CPU равно числу инструкций, умноженному на среднее число тактов на инструкцию и делённому на частоту. Производительность также зависит от архитектуры, IPC, кэшей, памяти, параллелизма и ограничений мощности. Поэтому сравнивать разные процессоры только по гигагерцам некорректно.

Пример. Если программа требует 6 миллиардов тактов, при 3 ГГц это около 2 секунд CPU, при неизменных остальных условиях.

Не перепутай. 1 ГГц не означает миллиард выполненных инструкций в секунду.

Самопроверка. Назови два фактора производительности кроме частоты.

Ключ: IPC или CPI, память, кэш, число ядер при параллельной нагрузке.

5 Прерывания

Просто. Устройство или сама программа заставляет процессор временно переключиться на специальный обработчик. Это способ реагировать на события.

Ответ для зачёта

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

Пример. Таймер даёт ОС возможность переключить выполняемый поток.

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

Самопроверка. Зачем нужна таблица векторов?

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

6 Режимы привилегий

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

Ответ для зачёта

Режимы привилегий ограничивают допустимые инструкции и доступ к памяти и устройствам. В x86 предусмотрены кольца 0–3: кольцо 0 наиболее привилегированное, кольцо 3 наименее привилегированное. Типичная ОС использует их для ядра и пользовательских программ. Для защищённой операции приложение выполняет системный вызов, а ядро проверяет аргументы и права. Нарушение защиты вызывает исключение. Такое разделение обеспечивает изоляцию, устойчивость и безопасность системы.

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

Не перепутай. Кольца 1 и 2 существуют в x86, но обычно не нужны обычной схеме ядро плюс приложения.

Самопроверка. Почему обычная функция библиотеки не всегда является системным вызовом?

Ключ: Она может полностью выполняться в пользовательском режиме.

7 Кэш и когерентность

Просто. Кэш держит рядом с CPU копии недавно использованных данных. Если у ядер разные копии одной ячейки, их нужно согласовывать.

Ответ для зачёта

Кэш уменьшает среднюю задержку доступа к памяти за счёт временной и пространственной локальности. Данные переносятся блоками — строками кэша. L1 обычно самый маленький и быстрый, L2 больше, L3 обычно ещё больше и нередко общий для нескольких ядер. При попадании данные берутся из кэша, при промахе — из следующего уровня. Когерентность поддерживает согласованность копий одной области памяти у разных ядер, например инвалидируя старые копии при записи. Когерентность сама по себе не делает составные операции потокобезопасными.

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

Не перепутай. Когерентность не заменяет мьютекс и не гарантирует нужный порядок всех операций программы.

Самопроверка. Почему counter++ остаётся опасным при когерентных кэшах?

Ключ: Это чтение, изменение и запись; два потока могут потерять обновление.

8 Суперскалярность и внеочередное выполнение

Просто. Суперскалярность — несколько исполнительных устройств могут работать с несколькими командами за такт. Out of order — готовую независимую команду можно выполнить раньше застрявшей.

Ответ для зачёта

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

Пример. Пока одна команда ждёт чтение памяти, независимое сложение может быть выполнено.

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

Самопроверка. В чём отличие от обычного конвейера?

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

9 Виртуальная память

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

Ответ для зачёта

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

Пример. Две соседние виртуальные страницы могут лежать в несоседних физических кадрах.

Не перепутай. Виртуальная память — не просто дополнительная память на диске.

Самопроверка. Чем страница отличается от сегмента?

Ключ: Страница фиксированного размера; сегмент отражает логическую область и имеет переменный размер.

10 Таблицы страниц и трансляция адреса

Просто. Виртуальный адрес делится на номер страницы и смещение внутри неё. Номер переводится, смещение сохраняется.

Ответ для зачёта

MMU преобразует виртуальный адрес в физический. Адрес разбивается на номер виртуальной страницы и смещение. TLB кэширует недавние трансляции; при промахе выполняется обход таблиц страниц аппаратурой или с участием ОС, в зависимости от архитектуры. Запись таблицы содержит номер кадра и признаки присутствия, доступа и изменения. После проверки прав физический адрес получается из номера кадра и исходного смещения. Если страница отсутствует или доступ запрещён, возникает исключение page fault, которое обрабатывает ОС.

Пример. Страница 4096 байт, адрес 0x1234: страница 1, смещение 0x234. Если её кадр 9, физический адрес 0x9234.

Не перепутай. Промах TLB не равен page fault: запись может существовать в таблице страниц.

Самопроверка. Что меняется при трансляции, а что остаётся?

Ключ: Номер страницы заменяется номером кадра, смещение не меняется.

11 Замещение страниц

Просто. Если свободных кадров мало, ОС выбирает, какую страницу убрать из ОЗУ. Хороший выбор уменьшает число будущих загрузок.

Ответ для зачёта

Алгоритм замещения выбирает страницу для вытеснения, когда необходимо освободить физический кадр. FIFO удаляет страницу, загруженную раньше остальных; LRU — ту, к которой дольше всего не обращались; Clock приближает оценку недавнего использования через бит обращения. Оптимальный алгоритм вытеснил бы страницу с самым далёким будущим обращением, но будущее неизвестно, поэтому это эталон сравнения. Изменённую страницу может потребоваться записать в хранилище. Слишком частые вытеснения вызывают thrashing — система тратит большую часть времени на подкачку.

Пример. При кадрах [1,2,3] и загрузке 4 FIFO вытесняет 1, если она была загружена первой.

Не перепутай. LRU и FIFO могут выбирать разные страницы: возраст загрузки не равен давности обращения.

Самопроверка. Что учитывает Clock?

Ключ: Бит недавнего обращения и циклический просмотр кандидатов.

12 Фрагментация памяти

Просто. Внутренняя — место пропадает внутри выделенных блоков. Внешняя — свободное место есть, но оно разбито на неудобные куски.

Ответ для зачёта

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

Пример. Нужен блок 10 КБ, а свободны два несоседних по 6 КБ — пример внешней фрагментации.

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

Самопроверка. Потеря 3 КБ внутри выделенной страницы — какая фрагментация?

Ключ: Внутренняя.

13 Динамическая память в C

Просто. malloc просит блок, calloc даёт обнулённые байты, realloc меняет размер, free возвращает блок аллокатору.

Ответ для зачёта

malloc выделяет запрошенное число байтов без инициализации, calloc выделяет массив и обнуляет его байты. realloc изменяет размер блока, может переместить его и сохраняет старые данные в пределах меньшего размера. При неудаче realloc с ненулевым размером возвращает NULL, а старый блок остаётся действительным. free освобождает блок; free(NULL) допустим. Это функции библиотеки, а не прямые системные вызовы. Аллокатор управляет аренами и свободными блоками и при необходимости запрашивает память у ОС; в Linux для этого могут использоваться brk и mmap. Каждый malloc не обязан обращаться к ядру.

Пример. int *tmp = realloc(p, bytes); if (tmp != NULL) p = tmp; Размер bytes заранее проверен и больше нуля.

Не перепутай. Нельзя сразу писать p = realloc(p, bytes): при неудаче теряется единственный адрес старого блока. Здесь не используется realloc(p, 0).

Самопроверка. Возвращает ли free память ОС немедленно?

Ключ: Не обязательно: аллокатор может сохранить блок для следующих запросов.

14 Утечки памяти и инструменты

Просто. Блок выделили, но забыли освободить или потеряли его адрес. Утечка и обращение после free — разные ошибки.

Ответ для зачёта

Утечка памяти — сохранение выделенной памяти после того, как она перестала быть нужна, без возможности или намерения своевременно её освободить. Типичная причина — потеря последнего указателя или пропуск free на ветке ошибки. Valgrind Memcheck отслеживает обращения к памяти и сообщает, в частности, об утечках и недопустимых доступах. AddressSanitizer добавляет проверки при компиляции и помогает найти выходы за границы, use after free и другие ошибки. Обнаружение утечек через LeakSanitizer зависит от платформы и настроек. Отсутствие отчёта не доказывает отсутствие ошибок на непроверенных путях.

Пример. clang -std=c11 -g -fsanitize=address -fno-omit-frame-pointer main.c -o app
В Linux: valgrind --leak-check=full ./app

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

Самопроверка. Чем утечка отличается от висячего указателя?

Ключ: При утечке память ещё выделена; висячий указатель указывает на объект, чьё время жизни уже закончилось.

15 Стек и куча

Просто. Локальная переменная обычно живёт до выхода из блока, а выделенный через malloc блок — до free. Указатель на блок и сам блок могут жить в разных местах.

Ответ для зачёта

Стек обычно используется для кадров вызовов, служебных данных и автоматических локальных объектов. Их время жизни управляется областью выполнения, а выделение часто сводится к изменению указателя стека. Куча предоставляет динамические блоки, временем жизни которых управляют malloc и free. Она удобна, когда размер известен только во время работы или данные должны пережить вызов функции. Выделение в куче обычно сложнее, но доступ к данным определяется также кэшами и расположением; сам адрес в куче не означает обязательно медленный доступ. Стандарт C задаёт длительности хранения, а не обязательное физическое размещение на стеке.

Пример. В int *p = malloc(10 * sizeof *p) локальный p и выделенный блок имеют разное время жизни.

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

Самопроверка. Можно ли вернуть указатель на malloc блок?

Ключ: Да, если блок ещё существует и вызывающая сторона получает обязанность освободить его.

16 Выравнивание данных

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

Ответ для зачёта

Выравнивание — требование к адресам объектов данного типа, например кратность четырём для некоторой реализации int. Правильное выравнивание позволяет выполнять доступ эффективно, а на некоторых архитектурах необходимо для его корректности. Компилятор вставляет padding между полями и в конце структур, чтобы элементы массива структур также были выровнены. Поэтому sizeof структуры может превышать сумму размеров полей. Перестановка полей иногда уменьшает потери. Нарушение требований типа при доступе через указатель может дать неопределённое поведение.

Пример. struct { char c; int x; }; часто занимает 8 байтов при char=1, int=4 и выравнивании int=4, но это не универсальная гарантия C.

Не перепутай. Упаковка структуры может уменьшить размер, но усложнить или замедлить доступ.

Самопроверка. Почему нельзя всегда вычислять размер структуры сложением полей?

Ключ: Есть внутренний и завершающий padding.

17 Семафор Дейкстры

Просто. Семафор — счётчик разрешений. Если разрешения закончились, следующий поток ждёт.

Ответ для зачёта

Семафор — примитив синхронизации с неотрицательным числом доступных разрешений и атомарными операциями P и V. P, или wait, получает разрешение, уменьшая счётчик, либо блокируется до его появления. V, или post, возвращает разрешение и позволяет ожидающему потоку продолжить. Счётный семафор ограничивает число одновременных пользователей ресурса, двоичный моделирует доступность одного разрешения. Конкретное внутреннее представление счётчика зависит от реализации. Атомарность операций необходима, чтобы два потока не получили одно разрешение.

Пример. Семафор с начальным значением 3 допускает до трёх одновременных пользователей ресурса.

Не перепутай. Обычный int и операция -- не образуют корректный семафор между потоками.

Самопроверка. Что происходит при P, когда разрешений нет?

Ключ: Поток ждёт разрешение, обычно блокируясь.

18 Двоичный семафор и мьютекс

Просто. Мьютекс — замок с владельцем. Семафор — передаваемое разрешение, которое удобно использовать и для сигнализации.

Ответ для зачёта

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

Пример. Поток производителя делает post после подготовки данных, потребитель выполняет wait.

Не перепутай. Обычный счётный семафор с начальным значением 1 не всегда принудительно ограничен единицей: лишние post могут увеличить счётчик.

Самопроверка. Кто имеет право unlock обычного мьютекса?

Ключ: Поток владелец.

19 Взаимная блокировка

Просто. Поток А держит первый замок и ждёт второй, поток Б держит второй и ждёт первый. Никто не сможет продолжить.

Ответ для зачёта

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

Пример. Все потоки сначала берут A, потом B — цикл A→B→A не возникнет.

Не перепутай. В исходном списке написано «по Коберну»; общепринятое название — условия Коффмана. Четыре условия описывай уверенно, спорить о фамилии не требуется.

Самопроверка. Перечисли четыре условия без подсказки.

Ключ: Взаимное исключение; удержание и ожидание; отсутствие принудительного отъёма; цикл ожидания.

20 Критическая секция

Просто. Это участок, где несколько потоков трогают общие данные и могут помешать друг другу.

Ответ для зачёта

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

Пример. lock(m); counter++; unlock(m); Все потоки используют один и тот же m.

Не перепутай. Защитить только запись недостаточно, если другие потоки читают тот же неатомарный объект без синхронизации.

Самопроверка. Почему два разных мьютекса не защищают один счётчик?

Ключ: Потоки могут одновременно владеть разными замками и войти в секцию.

21 Условные переменные

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

Ответ для зачёта

Условная переменная используется вместе с мьютексом и предикатом над общими данными. wait атомарно отпускает мьютекс и начинает ожидание, а перед возвратом вновь захватывает его. Условие проверяют в цикле while, потому что возможны ложные пробуждения и изменение состояния другим потоком. signal будит одного ожидающего, broadcast — всех. В отличие от семафора, условная переменная не накапливает разрешения: состояние хранится в защищаемых данных.

Пример. lock(m); while (empty) wait(cv, m); take_item(); unlock(m); Это псевдокод.

Не перепутай. if вместо while не гарантирует истинность условия после пробуждения.

Самопроверка. Кто хранит факт наличия работы — cv или очередь?

Ключ: Очередь и её состояние под мьютексом; cv только помогает ожидать изменение.

22 Состояние гонки и гонка данных

Просто. Два потока читают 10, оба прибавляют 1, оба записывают 11. Ожидалось 12, но одно обновление пропало.

Ответ для зачёта

Race condition — зависимость корректности результата от непредсказуемого порядка выполнения. Data race в модели C возникает при конфликтующих действиях разных потоков над одной областью памяти, когда хотя бы одно действие — неатомарная запись и нет требуемого отношения синхронизации. Такая гонка данных приводит к неопределённому поведению. Защита: мьютексы, подходящие атомарные операции, разделение владения или передача сообщений. Атомарность отдельных обращений не всегда устраняет логическую гонку составной операции.

Пример. Проверить, что очередь не пуста, и удалить элемент нужно как одно согласованное действие.

Не перепутай. volatile не делает counter++ атомарным и не создаёт межпоточную синхронизацию.

Самопроверка. Достаточно ли атомарных чтения и записи для атомарного увеличения?

Ключ: Нет; нужна атомарная read modify write операция либо замок.

23 Алгоритм Петерсона

Просто. Два потока объявляют желание войти, а переменная turn решает, кто уступает при одновременном желании.

Ответ для зачёта

Алгоритм Петерсона обеспечивает взаимное исключение для двух участников с флагами желания войти и переменной очереди. Участник i устанавливает flag[i], уступает очередь j и ждёт, пока flag[j] истинен и turn равен j. После секции он сбрасывает свой флаг. При классических предположениях атомарных обращений и последовательной согласованности достигаются взаимное исключение, прогресс и ограниченное ожидание. В современном C обычные общие переменные дают гонку данных; для учебной реализации требуются атомарные объекты с подходящим порядком памяти, например sequential consistency. volatile этого не исправляет.

Пример. Псевдокод: flag[i]=true; turn=j; while(flag[j] && turn==j) {} critical_section(); flag[i]=false;

Не перепутай. Классический алгоритм предназначен для двух потоков и использует активное ожидание.

Самопроверка. Зачем turn, если уже есть два флага?

Ключ: Разрешить конфликт, когда оба одновременно хотят войти.

24 Указатели и ссылки

Просто. Указатель хранит адрес. & берёт адрес переменной, * обращается к значению по адресу. Сам адрес и значение — разные вещи.

Ответ для зачёта

Указатель — объект, хранящий адрес другого объекта или функции. В выражении &var получают адрес var, а *ptr обозначает объект по адресу ptr, если указатель действителен. ptr++ перемещает указатель к следующему элементу его типа, а не увеличивает хранимое число. В C нет ссылок как отдельного типа языка; для сравнения, ссылка C++ обычно служит псевдонимом существующего объекта, должна быть инициализирована и не переназначается как указатель. Указатель можно переназначить и присвоить ему NULL.

Пример. int x=7; int *p=&x; *p=9; Теперь x равен 9. Выражение (*p)++ увеличило бы x.

Не перепутай. Нельзя выполнять p++ и затем разыменовывать его, если p указывал на одиночный x: там нет второго элемента.

Самопроверка. Чем отличаются p++, (*p)++ и *p++?

Ключ: Следующий указатель; увеличение значения; получить прежнее значение и затем сдвинуть указатель.

25 Указатель на функцию

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

Ответ для зачёта

Указатель на функцию хранит адрес функции совместимого типа и позволяет вызывать её косвенно. Объявление int (*pred)(int) задаёт указатель на функцию с аргументом int и результатом int. Вызов pred(x) эквивалентен (*pred)(x). Такие указатели применяют для обратных вызовов, предикатов, обработчиков событий и таблиц операций. Тип аргументов и возвращаемого значения должен соответствовать вызываемой функции. Скобки в объявлении существенны: int *f(int) объявляет функцию, возвращающую указатель.

Пример. int positive(int x) { return x > 0; } Затем find_if(a, n, positive).

Не перепутай. Передают positive, а не positive(3): второе уже вызывает функцию и даёт число.

Самопроверка. Прочитай int (*pred)(int) словами.

Ключ: pred — указатель на функцию, которая принимает int и возвращает int.

26 Арифметика указателей

Просто. Прибавление единицы означает следующий элемент. Тип определяет длину шага.

Ответ для зачёта

К указателю на элемент массива можно прибавлять и вычитать целое число в границах того же массива, включая позицию сразу за его концом. Смещение на k соответствует k элементам, а не k байтам. Указатель за концом допустим как граница, но его нельзя разыменовывать. Разность двух указателей внутри одного массива даёт число элементов и имеет тип ptrdiff_t, если результат представим. Складывать два указателя нельзя. Арифметика void* не входит в стандартный C; для обхода байтов используют unsigned char*.

Пример. Если sizeof(int)=4, то p+3 соответствует смещению на 12 байтов. *(a+2) обозначает третий элемент.

Не перепутай. Нельзя даже формировать указатель a-1, чтобы потом сравнить его с a. NULL+0 также не является допустимым способом получить границу массива.

Самопроверка. Можно ли читать *(a+n) при длине n?

Ключ: Нет: это позиция сразу за массивом.

27 Квалификатор volatile

Просто. volatile сообщает, что обращения к объекту нельзя считать обычными обращениями к неизменяющейся снаружи переменной. Но он не выдаёт замок.

Ответ для зачёта

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

Пример. volatile sig_atomic_t stop; может применяться как простой флаг в обработчике сигнала при соблюдении ограничений C.

Не перепутай. volatile не означает «значение обязательно каждый раз берётся из физической ОЗУ, минуя кэш».

Самопроверка. Защитит ли volatile int counter операцию counter++?

Ключ: Нет.

28 Препроцессор C

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

Ответ для зачёта

Препроцессор выполняет обработку директив до компиляции C. #include включает содержимое заголовка, #define определяет объектный или функциональный макрос, #if, #ifdef и #endif управляют условной компиляцией. Защита от повторного включения строится через include guards. Макрос подставляет токены и не является обычной типизированной функцией, поэтому аргументы и всё выражение заключают в скобки и избегают аргументов с побочными эффектами. Для простых вычислений функция часто безопаснее макроса.

Пример. #define SQR(x) ((x) * (x))
Для SQR(2+3) получится 25, но SQR(i++) опасен.

Не перепутай. Даже правильно расставленные скобки не устраняют повторное вычисление аргумента макроса.

Самопроверка. Чем #ifdef отличается от обычного if?

Ключ: Выбирает текст при подготовке исходника, а if выбирает действие во время выполнения.

29 Неопределённое поведение

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

Ответ для зачёта

Неопределённое поведение — ситуация, для которой стандарт C не устанавливает требований к поведению программы. Примеры: выход за границы массива при доступе, разыменование NULL, использование освобождённой памяти, повторный free, переполнение знакового целого, деление целого на ноль и гонка данных. Компилятор вправе исходить из того, что корректная программа не совершает UB, поэтому последствия не ограничены местом ошибки. Предотвращение: проверка границ и времени жизни, контроль диапазонов, предупреждения компилятора, тесты и санитайзеры.

Пример. int a[3]; a[3]=1; — выход за границы: разрешены индексы 0, 1, 2.

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

Самопроверка. Почему «у меня один раз работало» не оправдывает UB?

Ключ: Стандарт не гарантирует результат при другом запуске, вводе или оптимизации.

30 Соглашения о вызовах

Просто. Вызывающий и вызываемый код должны договориться, куда положить аргументы, где вернуть результат и кто восстановит стек.

Ответ для зачёта

Соглашение о вызовах определяет передачу аргументов и результата, сохранение регистров и очистку стека. В типичных 32 битных соглашениях Microsoft x86 cdecl передаёт аргументы через стек справа налево, стек очищает вызывающая функция. stdcall использует похожую передачу, но очищает стек вызываемая функция. fastcall передаёт часть подходящих аргументов через регистры, остальные через стек. Эти детали зависят от платформы и ABI. На Windows x64 действует отдельное соглашение с первыми четырьмя аргументами в соответствующих регистрах; переносить туда таблицу x86 буквально нельзя.

Пример. Для Microsoft x86 fastcall первые два подходящих целочисленных аргумента обычно передаются через ECX и EDX.

Не перепутай. Слова caller и callee означают вызывающую и вызываемую функции соответственно.

Самопроверка. Кто очищает стек в типичном x86 cdecl и stdcall?

Ключ: cdecl — caller; stdcall — callee.

23 типа задач: № 2–24

В каждом решении ниже показаны функции. Полные запускаемые программы с заголовками, main и мини тестами лежат в папке code и архиве. Сложность предикатных задач указана при O(1) стоимости одного предиката.

2 Обратный вывод массива

База · 10 минут на отдельную тренировку

Условие. void print_reverse(int* arr, size_t n): обратный вывод без [] и индексов.

Идея. Стартуй сразу за концом массива. Сначала сдвигай указатель назад, затем читай элемент.

  1. При n=0 выведи перевод строки и выйди до любой арифметики над arr.
  2. p=arr+n — допустимая граница, читать *p пока нельзя.
  3. Пока p не равен arr, выполни --p, выведи *p. После первого элемента остановись, не создавая arr-1.

Ручной пример. 10 20 30: p стоит после 30 → --p читает 30 → затем 20 → затем 10 → стоп.

void print_reverse(int *arr, size_t n) {
    if (n == 0) { putchar('\n'); return; }
    int *p = arr + n;
    while (p != arr) {
        --p;
        printf("%d", *p);
        if (p != arr) putchar(' ');
    }
    putchar('\n');
}

Границы и ошибки. Цикл p>=arr с p-- после первого элемента создаёт указатель перед массивом. Беззнаковое i>=0 тоже не останавливается.

Сложность. O(n) времени, O(1) памяти.

Проверь. n=0; n=1; три элемента. Ожидается 3 2 1 для 1 2 3.

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

Запускаемый файл: 02_print_reverse.c

3 Копирование массива

База · 10 минут на отдельную тренировку

Условие. void copy_array(int* dest, const int* src, size_t n), без индексов и memcpy.

Идея. У тебя два курсора. Прочитай по одному, запиши по другому и сдвинь оба.

  1. Контракт: dest вмещает n int, src содержит n int; частично перекрывающиеся области не поддерживаются.
  2. *dest++ = *src++ эквивалентно *dest=*src; затем ++dest и ++src.
  3. Счётчик n говорит, сколько копирований осталось. При нуле указатели не трогаем.

Ручной пример. src: 4 -1 4. После первого шага dest содержит 4, оба курсора смотрят на второй элемент.

void copy_array(int *dest, const int *src, size_t n) {
    while (n > 0) {
        *dest++ = *src++;
        --n;
    }
}

Границы и ошибки. Увеличить *dest — изменить число. Увеличить dest — перейти к следующей ячейке. Это разные действия.

Сложность. O(n) времени, O(1) дополнительной памяти.

Проверь. Пустой массив; отрицательные числа; повторяющиеся значения.

Повтори сам. Напиши аналог, который копирует только положительные числа и возвращает их количество.

Запускаемый файл: 03_copy_array.c

4 Слияние отсортированных массивов

Обязательно · 25 минут на отдельную тренировку

Условие. Выделить массив размера m+n и слить два массива по возрастанию с тремя курсорами.

Идея. На каждом шаге меньшая из двух текущих голов — следующий элемент результата.

  1. Проверь сложение m+n, умножение на sizeof(int), затем malloc. Оба исходных массива уже должны быть отсортированы.
  2. Пока оба непусты, сравни *a и *b, перенеси меньший, сдвинь соответствующий вход и выход.
  3. Скопируй хвост оставшегося массива. Верни сохранённое начало result, а не сдвинутый out. Освобождает результат вызывающий.

Ручной пример. 1 4 и 2 3: выбираем 1, затем 2, затем 3, затем оставшийся 4.

int *merge(const int *a, size_t m, const int *b, size_t n) {
    if (m > SIZE_MAX - n) return NULL;
    size_t total = m + n;
    if (total == 0 || total > SIZE_MAX / sizeof(int))
        return NULL;
    int *result = malloc(total * sizeof *result);
    if (result == NULL) return NULL;
    int *out = result;
    while (m > 0 && n > 0) {
        if (*a <= *b) { *out++ = *a++; --m; }
        else { *out++ = *b++; --n; }
    }
    while (m > 0) { *out++ = *a++; --m; }
    while (n > 0) { *out++ = *b++; --n; }
    return result;
}

Границы и ошибки. Проверяй оставшуюся длину до разыменования. При общей длине 0 NULL здесь означает пустой результат; при положительной — отказ.

Сложность. O(m+n) времени, O(m+n) памяти результата.

Проверь. Один массив пуст; оба пусты; дубликаты; отрицательные числа.

Повтори сам. Разбери руками слияние 1 3 3 и -2 3 8.

Запускаемый файл: 04_merge.c

5 Палиндром массива

База · 10 минут на отдельную тренировку

Условие. int is_palindrome(const int* arr, size_t n), два указателя навстречу.

Идея. Равенство зеркальных пар достаточно для проверки всего массива.

  1. При длине меньше 2 ответ 1; это также предотвращает n-1 при n=0.
  2. left указывает на первый, right на последний элемент.
  3. Пока left<right, сравни значения. При несовпадении верни 0; иначе сдвинь оба к центру.

Ручной пример. 1 2 1: сравни 1 и 1, курсоры сходятся на 2. Центральный элемент сравнивать не нужно.

int is_palindrome(const int *arr, size_t n) {
    if (n < 2) return 1;
    const int *left = arr, *right = arr + n - 1;
    while (left < right) {
        if (*left != *right) return 0;
        ++left;
        --right;
    }
    return 1;
}

Границы и ошибки. Сравнивают *left и *right — значения, а не равенство адресов.

Сложность. O(n) времени, O(1) памяти.

Проверь. Пустой; один элемент; чётный и нечётный палиндром; несовпадение.

Повтори сам. Измени массив 1 2 2 1 минимально, чтобы ответ стал 0.

Запускаемый файл: 05_palindrome.c

6 Матрица одним блоком

Обязательно · 25 минут на отдельную тренировку

Условие. Один int* блок, функции get и set, заполнение и вывод матрицы.

Идея. Матрица хранится строка за строкой. Чтобы попасть в строку i, пропусти i*cols элементов, затем добавь j.

  1. Перед malloc проверь произведения rows*cols и count*sizeof(int).
  2. Доступ *(mat+i*cols+j) разрешён при i<rows и j<cols. assert в примере проверяет этот контракт во время отладки; не заменяет обработку произвольного пользовательского ввода.
  3. Два вложенных цикла заполняют и выводят матрицу. Один malloc соответствует одному free.

Ручной пример. Матрица 2×3: позиции 0 1 2 / 3 4 5. Ячейка (1,2) имеет смещение 1*3+2=5.

int get(const int *mat, size_t rows, size_t cols,
        size_t i, size_t j) {
    assert(i < rows && j < cols);
    (void)rows;
    return *(mat + i * cols + j);
}
void set(int *mat, size_t rows, size_t cols,
         size_t i, size_t j, int value) {
    assert(i < rows && j < cols);
    (void)rows;
    *(mat + i * cols + j) = value;
}

Границы и ошибки. Умножать i нужно на число столбцов, не строк. int** — другая схема хранения.

Сложность. get/set O(1); заполнение O(rows*cols); память O(rows*cols).

Проверь. Матрица 1×1; 2×3; одна строка; проверка граничной ячейки.

Повтори сам. Напиши сумму второй строки, используя только *(mat+...).

Запускаемый файл: 06_matrix.c

7 Сортировка пузырьком

База · 20 минут на отдельную тренировку

Условие. void bubbleSort(int* array, size_t size).

Идея. Сравнивай соседей и меняй местами. За проход максимум неотсортированной части уйдёт вправо.

  1. При size<2 ничего делать не надо.
  2. Внешний цикл уменьшает неотсортированный конец. Внутренний доходит только до предпоследнего элемента этой части.
  3. Если за проход не было обменов, массив уже отсортирован и можно закончить.

Ручной пример. 3 1 2 → 1 3 2 → 1 2 3. Теперь 3 закреплён справа.

void bubbleSort(int *array, size_t size) {
    if (size < 2) return;
    for (size_t end = size; end > 1; --end) {
        int changed = 0;
        for (int *p = array; p < array + end - 1; ++p) {
            if (*p > *(p + 1)) {
                int tmp = *p;
                *p = *(p + 1);
                *(p + 1) = tmp;
                changed = 1;
            }
        }
        if (!changed) break;
    }
}

Границы и ошибки. Для чтения *(p+1) справа должен существовать сосед. Не делай size-1 до проверки пустого массива.

Сложность. O(n²) в худшем случае; O(n) на уже отсортированном массиве с флагом; память O(1).

Проверь. Пустой; один; уже отсортирован; обратный порядок; равные элементы.

Повтори сам. Сделай сортировку по убыванию, изменив одно сравнение.

Запускаемый файл: 07_bubble_sort.c

8 Факториал

База · 10 минут на отдельную тренировку

Условие. unsigned long long factorial(int n); 0!=1.

Идея. Начни с 1 и перемножь числа от 2 до n.

  1. 0 и 1 дают 1 без входа в цикл.
  2. Накопитель имеет тип unsigned long long.
  3. В учебной версии принят диапазон 0..20, безопасный и для 64 битного типа. Вне диапазона возвращаем 0 и устанавливаем errno=ERANGE.

Ручной пример. 5!: 1 → 2 → 6 → 24 → 120.

unsigned long long factorial(int n) {
    if (n < 0 || n > 20) { errno = ERANGE; return 0; }
    unsigned long long result = 1;
    for (int i = 2; i <= n; ++i)
        result *= (unsigned long long)i;
    return result;
}

Границы и ошибки. Если начать накопитель с нуля, результат всегда будет ноль. 21! не помещается в 64 бита.

Сложность. O(n) времени, O(1) памяти.

Проверь. 0→1; 1→1; 5→120; 20; недопустимые -1 и 21.

Повтори сам. Напиши факториал по памяти и объясни, почему рекурсия здесь не обязательна.

Запускаемый файл: 08_factorial.c

9 Числа Фибоначчи

База · 15 минут на отдельную тренировку

Условие. unsigned long long fib(int n). Используем F0=0, F1=1.

Идея. Для следующего числа нужны только два предыдущих.

  1. Отдельно обработай n=0 и n=1.
  2. На каждом шаге вычисли next=a+b, затем a=b, b=next.
  3. Верни b. Диапазон 0..93; вне его 0 и errno=ERANGE. Не вычисляй лишнее F94 ради ответа F93.

Ручной пример. a=0,b=1 → 1,1 → 1,2 → 2,3 → 3,5.

unsigned long long fib(int n) {
    if (n < 0 || n > 93) { errno = ERANGE; return 0; }
    if (n < 2) return (unsigned long long)n;
    unsigned long long a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        unsigned long long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

Границы и ошибки. Наивная рекурсия многократно пересчитывает одно и то же. Не перезаписывай a до вычисления суммы.

Сложность. O(n) времени, O(1) памяти.

Проверь. 0→0; 1→1; 2→1; 10→55; 93; 94 вне диапазона.

Повтори сам. Выпиши значения a и b после каждого шага для n=6.

Запускаемый файл: 09_fibonacci.c

10 Наибольший общий делитель

База · 15 минут на отдельную тренировку

Условие. int gcd(int a, int b), алгоритм Евклида.

Идея. НОД(a,b)=НОД(b,a%b). Повторяй, пока второй аргумент не станет нулём.

  1. Работай с неотрицательными модулями. unsigned приём в magnitude обрабатывает и INT_MIN, для которого обычное -n может переполниться.
  2. Сохрани остаток, сдвинь b в a, остаток в b.
  3. Если положительный НОД не помещается в int, верни 0 с errno=ERANGE. Для (0,0) принимаем результат 0.

Ручной пример. 48,18 → 18,12 → 12,6 → 6,0. Ответ 6.

static unsigned magnitude(int x) {
    return x < 0 ? 0u - (unsigned)x : (unsigned)x;
}
int gcd(int a, int b) {
    unsigned x = magnitude(a), y = magnitude(b);
    while (y != 0) {
        unsigned rem = x % y;
        x = y;
        y = rem;
    }
    if (x > INT_MAX) { errno = ERANGE; return 0; }
    return (int)x;
}

Границы и ошибки. Остаток вычисляют до изменения переменных. Нельзя брать %0.

Сложность. O(log max(|a|,|b|)) времени, O(1) памяти.

Проверь. 48 и 18; отрицательный аргумент; один ноль; оба нуля; INT_MIN и 2.

Повтори сам. Найди вручную gcd(84,30), затем напиши цикл.

Запускаемый файл: 10_gcd.c

11 Наименьшее общее кратное

База · 15 минут на отдельную тренировку

Условие. int lcm(int a, int b).

Идея. НОК = |a| / НОД × |b|. Сначала деление, затем умножение.

  1. Если хотя бы один аргумент ноль, результат ноль.
  2. Вычисли НОД модулей алгоритмом Евклида. Он встроен в файл, чтобы пример запускался отдельно.
  3. Проверь q<=INT_MAX/y перед умножением. При слишком большом результате верни 0 и errno=ERANGE.

Ручной пример. 12 и 18: НОД=6, НОК=(12/6)*18=36.

static unsigned magnitude(int x) {
    return x < 0 ? 0u - (unsigned)x : (unsigned)x;
}
int lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    unsigned x = magnitude(a), y = magnitude(b);
    unsigned u = x, v = y;
    while (v != 0) {
        unsigned rem = u % v;
        u = v;
        v = rem;
    }
    unsigned q = x / u;
    if (q > (unsigned)INT_MAX / y) {
        errno = ERANGE;
        return 0;
    }
    return (int)(q * y);
}

Границы и ошибки. Формула a*b/gcd может переполниться ещё до деления.

Сложность. Как у алгоритма Евклида, O(log max(|a|,|b|)); память O(1).

Проверь. 12,18→36; -12,18→36; 0,7→0; переполнение.

Повтори сам. Объясни, почему lcm(0,0) нужно обработать до деления.

Запускаемый файл: 11_lcm.c

12 Проверка простоты

База · 15 минут на отдельную тренировку

Условие. int is_prime(int n), 1 для простого, 0 иначе.

Идея. У составного числа есть делитель не больше квадратного корня. Достаточно искать до него.

  1. Для n<2 верни 0.
  2. Пробуй d от 2, пока d<=n/d. Это проверка d²<=n без риска переполнить d*d.
  3. Если остаток равен нулю — число составное. Если делителей не нашлось — простое.

Ручной пример. 49: d=2,3,4,5,6 не делят; d=7 делит, ответ 0.

int is_prime(int n) {
    if (n < 2) return 0;
    for (int d = 2; d <= n / d; ++d)
        if (n % d == 0) return 0;
    return 1;
}

Границы и ошибки. 1 не является простым. Нельзя остановиться перед точным квадратным корнем.

Сложность. O(√n) времени, O(1) памяти.

Проверь. -3,0,1→0; 2→1; 49→0; 97→1.

Повтори сам. Почему проверка только чётности не доказывает простоту 9?

Запускаемый файл: 12_is_prime.c

13 Разложение на простые множители

Обязательно · 20 минут на отдельную тренировку

Условие. Вывести n=p1^k1 * p2^k2 * ... для n>1.

Идея. Пока число делится на текущий делитель, дели и считай повторения.

  1. Запомни исходное число для начала вывода. Для каждого d обнуляй счётчик k.
  2. Внутренний while удаляет все множители d. Если k>0, выведи d^k с разделителем между группами.
  3. После цикла остаток n>1 является последним простым множителем. Выведи его со степенью 1.

Ручной пример. 360 → делим на 2 трижды: 45 → на 3 дважды: 5 → остаток 5. Получаем 2^3 * 3^2 * 5^1.

void print_factors(int n) {
    if (n <= 1) return;
    printf("%d = ", n);
    int first = 1;
    for (int d = 2; d <= n / d; ++d) {
        int k = 0;
        while (n % d == 0) { n /= d; ++k; }
        if (k != 0) {
            if (!first) printf(" * ");
            printf("%d^%d", d, k);
            first = 0;
        }
    }
    if (n > 1) {
        if (!first) printf(" * ");
        printf("%d^1", n);
    }
    putchar('\n');
}

Границы и ошибки. Забытый остаток теряет последний большой простой множитель. Проверять делитель нужно против текущего остатка.

Сложность. O(√n) пробных делителей в худшем случае; O(1) памяти.

Проверь. 360; простое 13; 2; степень 16→2^4.

Повтори сам. Разложи 84 и выпиши остаток после каждого успешного деления.

Запускаемый файл: 13_prime_factors.c

14 Быстрое возведение в степень

Обязательно · 20 минут на отдельную тренировку

Условие. long long power(long long base, int exp), exp>=0, O(log exp).

Идея. При чётной степени возводи основание в квадрат и дели степень пополам. При нечётной сначала забери один множитель в результат.

  1. result=1. Если exp нечётный, result*=base.
  2. exp/=2. Если ещё нужны шаги, base*=base.
  3. Повторяй до нуля. Контракт: все выполняемые умножения помещаются в long long. Проверка переполнения в этой краткой функции не реализована; большие значения вне контракта.

Ручной пример. 3^5: result=3, base=9, exp=2 → base=81, exp=1 → result=243, exp=0.

/* Contract: exp >= 0; all needed products fit long long. */
long long power(long long base, int exp) {
    if (exp < 0) { errno = EDOM; return 0; }
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 != 0) result *= base;
        exp /= 2;
        if (exp > 0) base *= base;
    }
    return result;
}

Границы и ошибки. Не считай base*base после последнего шага: это лишняя операция и лишний риск переполнения. Для 0^0 здесь принято 1.

Сложность. O(log exp) времени при exp>0, O(1) памяти.

Проверь. 2^10=1024; (-2)^3=-8; 5^0=1; максимальное long long в степени 1.

Повтори сам. Проследи 2^13 по битам 1101.

Запускаемый файл: 14_power.c

15 Сумма цифр

База · 10 минут на отдельную тренировку

Условие. int digit_sum(int n), отрицательные числа по модулю.

Идея. %10 достаёт последнюю цифру, /10 отрезает её.

  1. Переведи модуль в unsigned без вычисления -INT_MIN в типе int.
  2. Добавь x%10 к сумме.
  3. Раздели x на 10, пока не получишь ноль. do while также естественно обрабатывает исходный ноль.

Ручной пример. -203: модуль 203 → цифра 3 → 20 → 0 → 2 → 2; сумма 5.

int digit_sum(int n) {
    unsigned x = n < 0 ? 0u - (unsigned)n : (unsigned)n;
    int sum = 0;
    do {
        sum += (int)(x % 10);
        x /= 10;
    } while (x != 0);
    return sum;
}

Границы и ошибки. Знак не является цифрой. Для минимального int обычный abs может не дать представимый результат.

Сложность. O(k), где k — число цифр; O(1) памяти.

Проверь. 0→0; -123→6; 9001→10; минимальный int.

Повтори сам. На том же шаблоне посчитай количество цифр числа, считая у нуля одну цифру.

Запускаемый файл: 15_digit_sum.c

16 Десятичное число в двоичное

База · 15 минут на отдельную тренировку

Условие. Вывести неотрицательное число в двоичной записи как последовательность символов.

Идея. Остатки от деления на 2 дают биты с конца. Сохрани их, затем выведи обратно.

  1. Используй unsigned и массив символов, достаточный для всех битов типа и нулевого символа.
  2. Записывай '0'+n%2 и дели n на 2. Цикл do while нужен для нуля.
  3. Пройди заполненную часть буфера с конца. В примере main показывает тестовые числа; для ввода неотрицательного unsigned можно использовать scanf с %u и проверкой результата.

Ручной пример. 13: остатки 1,0,1,1. Обратный вывод даёт 1101.

void print_binary(unsigned n) {
    char bits[sizeof(unsigned) * CHAR_BIT + 1];
    char *out = bits;
    do {
        *out++ = (char)('0' + n % 2);
        n /= 2;
    } while (n != 0);
    *out = '\0';
    while (out != bits) putchar(*--out);
    putchar('\n');
}

Границы и ошибки. Прямой вывод остатков даст обратную запись. Это текст из битов, а не десятичное число 1101 для арифметики.

Сложность. O(log(n+1)) времени и битов памяти, для машинного типа буфер ограничен константой.

Проверь. 0→0; 1→1; 13→1101; 16→10000.

Повтори сам. Замени основание 2 на 8 и объясни, что получится.

Запускаемый файл: 16_binary.c

17 Первый элемент по предикату

Обязательно · 15 минут на отдельную тренировку

Условие. int* find_if(int* arr, size_t n, int (*pred)(int)).

Идея. Обход всегда одинаковый; правило выбора передаётся как функция.

  1. pred должен указывать на функцию совместимого типа.
  2. Если pred(*arr) ненулевой, верни arr — адрес текущего элемента.
  3. Если прошёл весь массив, верни NULL. Вызывающий проверяет результат перед разыменованием.

Ручной пример. -1 0 5 7 и positive: первые два не подходят, вернётся a+2, а *результат равен 5.

int *find_if(int *arr, size_t n, int (*pred)(int)) {
    while (n > 0) {
        if (pred(*arr)) return arr;
        ++arr;
        --n;
    }
    return NULL;
}

Границы и ошибки. Вернуть *arr — вернуть число вместо указателя. Передавать нужно имя функции, не результат её вызова.

Сложность. O(n) вызовов предиката, O(1) дополнительной памяти.

Проверь. Первый подходит; подходит в середине; никто; пустой массив.

Повтори сам. Напиши предикат кратности трём и найди первое такое число.

Запускаемый файл: 17_find_if.c

18 Фильтрация по предикату

Обязательно · 20 минут на отдельную тренировку

Условие. size_t filter(int* arr, size_t n, int (*pred)(int), int* result).

Идея. Входной курсор двигается всегда, выходной — только для подходящих элементов.

  1. Результат должен вмещать до n элементов; проще выделить n. Используй отдельный буфер; произвольное частичное перекрытие не поддерживается.
  2. При истинном pred копируй значение, двигай result и увеличивай count.
  3. Верни count: только первые count элементов выходного буфера имеют смысл.

Ручной пример. 1 2 3 4 и even → записали 2, затем 4, count=2.

size_t filter(int *arr, size_t n, int (*pred)(int),
              int *result) {
    size_t count = 0;
    while (n > 0) {
        if (pred(*arr)) {
            *result++ = *arr;
            ++count;
        }
        ++arr;
        --n;
    }
    return count;
}

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

Сложность. O(n) вызовов предиката, O(1) служебной памяти плюс выходной буфер.

Проверь. Все подходят; никто; пустой; отрицательные чётные числа.

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

Запускаемый файл: 18_filter.c

19 Разбиение по предикату

Обязательно · 25 минут на отдельную тренировку

Условие. int* partition(int* arr, size_t n, int (*pred)(int)): подходящие в начало, вернуть границу.

Идея. boundary отмечает конец уже собранной подходящей части. Когда находишь подходящее число, меняй его с boundary и сдвигай границу.

  1. До boundary лежат только подходящие элементы; между boundary и курсором — неподходящие из уже просмотренных.
  2. Истинный pred вызывает обмен текущего элемента с boundary.
  3. Верни boundary. Если подходят все, это допустимый указатель сразу за концом; разыменовывать его нельзя.

Ручной пример. 1 2 3 4 → 2 1 3 4 → 2 4 3 1. Граница указывает на 3.

int *partition(int *arr, size_t n, int (*pred)(int)) {
    int *boundary = arr;
    while (n > 0) {
        if (pred(*arr)) {
            int tmp = *boundary;
            *boundary = *arr;
            *arr = tmp;
            ++boundary;
        }
        ++arr;
        --n;
    }
    return boundary;
}

Границы и ошибки. Это разбиение, не полная сортировка. Порядок неподходящих элементов может измениться.

Сложность. O(n) вызовов предиката, O(1) дополнительной памяти.

Проверь. Все; никто; пустой; чередование. Проверь оба участка относительно возвращённой границы.

Повтори сам. Разбери вручную 1 2 3 4 6 по чётности и отметь boundary после каждого шага.

Запускаемый файл: 19_partition.c

20 Гласные и согласные

База · 20 минут на отдельную тренировку

Условие. Прочитать строку, посчитать английские гласные a e i o u и остальные латинские буквы без учёта регистра.

Идея. Сначала приведи английскую заглавную букву к строчной, затем отличи букву от знаков и цифр.

  1. fgets читает строку с пробелами, в примере до 1023 символов; длинный ввод потребует чтения продолжения.
  2. Проверяй диапазоны латиницы. Это учебный вариант для ASCII совместимой среды, не обработчик русского UTF-8 текста.
  3. Пять гласных перечислены явно; остальные буквы a..z считаются согласными. y здесь согласная по условию.

Ручной пример. Hello, C! → e,o: 2 гласные; H,l,l,C: 4 согласные.

void count_letters(const char *s, size_t *vowels,
                   size_t *consonants) {
    *vowels = *consonants = 0;
    while (*s != '\0') {
        unsigned char c = (unsigned char)*s++;
        if (c >= 'A' && c <= 'Z')
            c = (unsigned char)(c - 'A' + 'a');
        if (c < 'a' || c > 'z') continue;
        if (c == 'a' || c == 'e' || c == 'i' ||
            c == 'o' || c == 'u') ++*vowels;
        else ++*consonants;
    }
}

Границы и ошибки. Не считай пробелы и цифры согласными. При использовании ctype аргумент передают как unsigned char.

Сложность. O(n) времени, O(1) служебной памяти плюс входной буфер.

Проверь. Смешанный регистр; только знаки; AEIOU; пустая строка.

Повтори сам. Добавь отдельный счётчик цифр 0..9.

Запускаемый файл: 20_count_letters.c

21 Переворот числа

Обязательно · 20 минут на отдельную тренировку

Условие. int reverse_number(int n), сохранить знак.

Идея. Забирай цифры справа и дописывай их справа к результату: result=result*10+digit.

  1. Отдели знак и работай с модулем в unsigned.
  2. До умножения проверь, что новая величина не превысит допустимый предел. При переполнении верни 0 и errno=ERANGE.
  3. Восстанови знак; для величины INT_MAX+1 отрицательный ответ — INT_MIN. Начальные нули результата исчезают, потому что возвращается число.

Ручной пример. -120 → 0 → 2 → 21 → восстановить знак: -21.

int reverse_number(int n) {
    unsigned x = n < 0 ? 0u - (unsigned)n : (unsigned)n;
    unsigned result = 0;
    unsigned limit = n < 0 ? (unsigned)INT_MAX + 1u : INT_MAX;
    do {
        unsigned digit = x % 10;
        if (result > (limit - digit) / 10) {
            errno = ERANGE;
            return 0;
        }
        result = result * 10 + digit;
        x /= 10;
    } while (x != 0);
    if (n >= 0) return (int)result;
    if (result == (unsigned)INT_MAX + 1u) return INT_MIN;
    return -(int)result;
}

Границы и ошибки. Результат может не помещаться в int, хотя исходное число помещалось. Проверять после знакового переполнения уже поздно.

Сложность. O(k) по числу цифр, O(1) памяти.

Проверь. 0; -120; 1234; значение, чей переворот слишком велик.

Повтори сам. Объясни, почему переворот 1000 равен 1, а не строке 0001.

Запускаемый файл: 21_reverse_number.c

22 Скобочная последовательность

Сложнее · 30 минут на отдельную тренировку

Условие. int is_balanced(const char* s): (), [], {} должны быть сбалансированы и вложены правильно.

Идея. Последняя открытая скобка должна закрыться первой — нужен стек.

  1. Открывающую скобку положи в стек. top — количество элементов.
  2. Закрывающая требует непустого стека и совпадения типа с вершиной; затем уменьши top.
  3. В конце стек обязан быть пустым. Остальные символы игнорируются. Выделенный стек освобождается и при ошибке. Отказ malloc возвращает 0 и errno=ENOMEM.

Ручной пример. ([]): push (, push [, встретили ] — снять [, встретили ) — снять (. Стек пуст.

int is_balanced(const char *s) {
    size_t n = strlen(s);
    if (n == 0) return 1;
    char *stack = malloc(n);
    if (stack == NULL) { errno = ENOMEM; return 0; }
    size_t top = 0;
    int ok = 1;
    while (*s != '\0') {
        char c = *s++;
        if (c == '(' || c == '[' || c == '{') {
            *(stack + top++) = c;
        } else if (c == ')' || c == ']' || c == '}') {
            char expected = c == ')' ? '(' : c == ']' ? '[' : '{';
            if (top == 0 || *(stack + top - 1) != expected) {
                ok = 0;
                break;
            }
            --top;
        }
    }
    if (top != 0) ok = 0;
    free(stack);
    return ok;
}

Границы и ошибки. Один счётчик глубины не отличит ([)] от правильного вложения.

Сложность. O(n) времени, O(n) памяти в худшем случае.

Проверь. Пустая строка; ({[]}); ([)]; )(; лишняя открывающая.

Повтори сам. Нарисуй стек после каждого символа строки {[()]} и строки {[(])}.

Запускаемый файл: 22_balanced.c

23 Замена символов в строке

База · 10 минут на отдельную тренировку

Условие. void replace_char(char* str, char old_char, char new_char), изменение на месте.

Идея. Обходи строку до нулевого символа и меняй только совпадения.

  1. Передай изменяемый массив char, например char s[]="banana".
  2. Проверяй *str, при совпадении присваивай new_char.
  3. Сдвигай указатель. Завершающий нулевой символ не является частью обрабатываемого текста.

Ручной пример. banana, a→o: bonono.

void replace_char(char *str, char old_char, char new_char) {
    while (*str != '\0') {
        if (*str == old_char) *str = new_char;
        ++str;
    }
}

Границы и ошибки. Нельзя изменять строковый литерал через char *s="banana". Для обычной текстовой замены выбирай ненулевой new_char; '\0' обрежет видимую строку.

Сложность. O(n) времени, O(1) памяти.

Проверь. Пустая; совпадений нет; все символы совпадают; old==new.

Повтори сам. Замени пробелы на подчёркивания в строке hello world.

Запускаемый файл: 23_replace_char.c

24 Бинарный поиск

Обязательно · 25 минут на отдельную тренировку

Условие. int binary_search(const int* arr, size_t n, int target), индекс или -1, итеративно.

Идея. В отсортированном массиве сравнение с серединой исключает половину кандидатов.

  1. Храни полуинтервал [left,right), сначала [0,n). Это исключает right=n-1 при пустом массиве.
  2. mid=left+(right-left)/2. Если значение меньше цели, left=mid+1; иначе при большем right=mid.
  3. Совпало — верни индекс. Если left==right, кандидатов нет. Индекс должен помещаться в int; код проверяет это перед возвратом.

Ручной пример. 1 3 5 7 9, ищем 7: mid=2, значение 5 → диапазон [3,5), mid=4, значение 9 → [3,4), найдена 7.

int binary_search(const int *arr, size_t n, int target) {
    size_t left = 0, right = n;
    while (left < right) {
        size_t mid = left + (right - left) / 2;
        int value = *(arr + mid);
        if (value == target) {
            if (mid > INT_MAX) { errno = ERANGE; return -1; }
            return (int)mid;
        }
        if (value < target) left = mid + 1;
        else right = mid;
    }
    return -1;
}

Границы и ошибки. Без сортировки алгоритм не работает. При дубликатах возвращается одно из совпадений, не обязательно первое.

Сложность. O(log n) времени, O(1) памяти.

Проверь. Пустой; первый; последний; середина; отсутствующий; дубликаты.

Повтори сам. Разбери поиск отсутствующего 6 в массиве 1 3 5 7 9.

Запускаемый файл: 24_binary_search.c

Материалы и границы курса

Актуализация 29 октября 2026 по сообщению учащегося: две практические задачи, № 1 и № 25 исключены преподавателем. Исходный документ описывает прежний формат; в этой части действует уточнение. Теория сохранена как справочник. Новые время и оценивание неизвестны.

Основа подготовки — приложенный список «ПА Системное программирование 3 курс 6 семестр»: в нём 30 вопросов и 25 типов практики. Сейчас активны 23 типа с исходными номерами 2–24. В документе не заданы версия C, компилятор, диапазоны чисел, грамматика операндов для ОПЗ и проходной балл. В примерах выбран C11; дополнительные контракты явно указаны у задач. Теория архитектуры привязана к общим принципам и x86 там, где это требуется формулировкой.

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

Ссылки проверены 28 октября 2026 года. Решения — учебные реализации под оговорённые условия. Они показывают основной алгоритм и не превращают заданные функции без параметра ёмкости в универсальные безопасные библиотеки.