Как готовиться к экзамену по программированию: код на бумаге и за ПК

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

Экзамен по программированию устроен иначе, чем устный экзамен по теории. Пересказать лекцию мало: нужно написать работающий код, иногда на бумаге без компилятора, иногда за компьютером с таймером. Ещё бывают задания «что выведет программа» и «найди ошибку». Ниже о том, как готовиться к каждому типу: трассировка, код на бумаге, базовые алгоритмы, разбор своих лабораторных и тренировка на время. В конце план на неделю.

Какие бывают задания

Тип Что проверяют Как готовиться
Теоретический вопрос Типы данных, указатели, рекурсия, классы, сложность алгоритмов Определение плюс пример кода на пять строк
«Что выведет программа» Умеете ли выполнять код в голове Трассировка на бумаге
«Найди ошибку» Знаете ли ловушки языка Список ловушек и разбор своих ошибок
Функция на бумаге Пишете ли код без подсказок среды Базовые алгоритмы от руки
Задача за компьютером Решаете ли за ограниченное время и проверяете ли решение Тренировка с таймером и тестами
Вопросы по своему коду Понимаете ли свои лабораторные Разбор лабораторных

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

Трассировка: выполните код на бумаге

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

Лист бумаги с нарисованной от руки таблицей, часть клеток отмечена оранжевыми точками, рядом карандаш, ластик и закрытый ноутбук

s = 0
for i in range(1, 10, 3):
    s += i // 2
print(s)
Шаг i i // 2 s
до цикла 0
1 1 0 0
2 4 2 2
3 7 3 5

range(1, 10, 3) даёт 1, 4 и 7, число 10 в него не входит. Программа выведет 5.

Правила трассировки:

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

Задания «что выведет» часто строят на ловушках. Классическая:

#include <stdio.h>

int main(void) {
    int k = 2;
    switch (k) {
        case 1: printf("A");
        case 2: printf("B");
        case 3: printf("C");
        default: printf("D");
    }
    printf("\n");
    return 0;
}

Программа выведет BCD: без break выполнение проваливается в следующие ветки. GCC с флагом -Wextra предупреждает о таком проваливании.

Ещё частые ловушки:

  • целочисленное деление: в C 7 / 2 равно 3, в Python 7 // 2 равно 3, а 7 / 2 равно 3.5;
  • i++ и ++i в выражении: при i = 5 запись a = i++ даёт a = 5, а a = ++i даёт a = 6;
  • = вместо ==: if (x = 0) присваивает ноль, и условие всегда ложно;
  • <= вместо < в границе цикла: лишняя итерация и выход за пределы массива;
  • в Python b = a не копирует список:
a = [1, 2, 3]
b = a
b.append(4)
print(len(a))  # 4: a и b указывают на один список

Код на бумаге

На бумаге нет подсветки, автодополнения и компилятора. Помогает порядок действий:

  1. Сигнатура и пример. Запишите, что функция принимает и возвращает, и маленький пример: вход и ожидаемый ответ.
  2. Каркас. Сначала циклы и условия, потом их содержимое. Оставляйте пустые строки между блоками, чтобы было куда дописать.
  3. Трассировка своего кода на примере из первого пункта.
  4. Крайние случаи: пустой массив, один элемент, все элементы равны, отрицательные числа, искомого элемента нет.
  5. Синтаксис в конце: скобки, точки с запятой, return, типы.

Пример: бинарный поиск в отсортированном массиве. В нём легко ошибиться на единицу.

int binary_search(const int a[], int n, int x) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Проверьте на массиве {1, 3, 5, 7, 9}. Для x = 7: mid = 2, a[2] = 5 < 7, значит lo = 3; дальше mid = 3, a[3] = 7, ответ 3. Для x = 4: mid = 2, 5 > 4, hi = 1; mid = 0, 1 < 4, lo = 1; mid = 1, 3 < 4, lo = 2; теперь lo > hi, ответ -1.

Типичные ошибки в этой задаче. Условие while (lo < hi) пропускает случай, когда остался один элемент. Запись lo = mid вместо lo = mid + 1 может зациклить программу. Середина (lo + hi) / 2 на очень больших массивах переполняет int, поэтому её считают как lo + (hi - lo) / 2.

Базовые алгоритмы, которые надо писать без подсказки

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

  • массивы: сумма, минимум и максимум, линейный поиск, разворот, подсчёт по условию, сдвиг;
  • сортировки: пузырьком, выбором и вставками со сложностью O(n²); для сортировки слиянием и быстрой знайте идею и сложность O(n log n), у быстрой в худшем случае O(n²);
  • поиск: бинарный, O(log n), только на отсортированном массиве;
  • числа: НОД по алгоритму Евклида, проверка на простоту делением до √n, разбор числа на цифры;
  • строки: палиндром, подсчёт слов, замена символов;
  • рекурсия: факториал, числа Фибоначчи, условие выхода;
  • структуры данных: стек, очередь, односвязный список со вставкой и удалением, а в C ещё malloc и free;
  • матрицы: обход, транспонирование, сумма по диагонали.

Алгоритм Евклида, например, помещается в четыре строки:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 18))  # 6

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

Разберите свои лабораторные

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

  1. Ответьте себе: что делает программа, почему она устроена именно так, какая сложность у основного алгоритма, что будет на пустом вводе.
  2. Перепишите главную функцию с нуля, не глядя, за 20–30 минут.
  3. Найдите места, которые понимаете не до конца, особенно где брали чужой код или подсказку. Их разберите первыми.
  4. Перечитайте замечания преподавателя. Это готовый список ваших типичных ошибок.

Тренировка с ограничением времени

Дома над задачей можно сидеть весь вечер, на экзамене есть таймер. Поэтому тренируйтесь в тех же условиях:

  1. Возьмите две-три задачи из практики или прошлых лет и столько времени, сколько дадут на экзамене.

  2. Работайте в той же среде, что будет в аудитории. Если там простой редактор и терминал, собирайте и проверяйте из терминала:

    gcc -Wall -Wextra -std=c11 main.c -o main
    ./main < in1.txt > out1.txt
    diff out1.txt expected1.txt
    

    diff ничего не выводит, если файлы совпали, и показывает разные строки, если нет. Для Python то же самое: python3 main.py < in1.txt > out1.txt.

  3. Сначала прочитайте все задачи и начните с той, которую точно решите. Напишите самое простое правильное решение, оптимизируйте потом.

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

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

План на неделю

День Что делать
1 Узнать формат, собрать задания прошлых лет и лабораторные, теория с примерами кода
2 Трассировка: 10–15 фрагментов «что выведет», свой список ловушек
3–4 Базовые алгоритмы на бумаге, потом проверка за компьютером
5 Разбор лабораторных
6 Пробный экзамен с таймером
7 Слабые места, теория вслух, вечером спать

Как с этим помогает Tilpi

Напишите решение тренировочной задачи сами, а потом попросите исполнителя Tilpi из чата задания его проверить. Исполнитель собирает и запускает код в отдельной изолированной машине, пишет и прогоняет тесты, ищет ошибки и предлагает исправления, а перед запуском показывает план. Чат задания объясняет решение по шагам: можно спросить, почему ваша трассировка не совпала с выводом программы. Без тарифа исполнитель работает на уровне «Быстрая» из бесплатных ежемесячных кредитов, общих с чатом; нужна подтверждённая почта.

ИИ для учёбы. По вашим лекциям.

Пришлите в чат лекцию, задачу или свой текст. Тилпи объяснит тему со ссылкой на страницу, разберёт решение по шагам и проверит оформление.

Проверить своё решение в Tilpi