# 100 задач по Python: отладка кода

Юрий Белк

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

Внутри 100 задач разного уровня сложности и теория, как сделать код чистым.

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

Для кого этот сборник

- для начинающего Python-разработчика, который уже знает основы (переменные, условия, циклы, списки, функции).

Некоторые решения могут потребовать внимательной проверки ввода/вывода. Они с ошибками. Это сделано не из вредности это задумка: отладка важнее кодинга.

И это именно то, что превращает новичка в уверенного разработчика.

## Глава 1. Установка Python

Эта глава поможет установить интерпретатор Python 3, проверить что он работает, и выбрать удобный редактор/IDE. Инструкция рассчитана на новичков.

Кто занимается изучением Python, эту главу можно пропустить, что является логичным, потому что задачник не для новичков, которые ничего не знают в Python, но по сложившейся традиции главу с установщиками включаем, так сказать дань традиции.

1) Что именно нужно установить

Python (интерпретатор) – программа, которая запускает ваш код .py.

pip – менеджер пакетов (нужен для установки библиотек).

(По желанию) IDE/редактор – среда, где удобнее писать код.

Важно: для обучения почти всегда выбирают Python 3.x. Python 2 – устарел.

2) Где брать установочные файлы

Скачивайте Python только с официального сайта проекта Python (раздел загрузок для вашей ОС) или из официальных магазинов/репозиториев вашей ОС:

Windows/macOS: на официальном сайте Python (раздел Downloads).

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

Не используйте “левые” сборки с неизвестных сайтов.

3) Установка на Windows (10/11)

Шаг 1. Скачайте установщик

На официальном сайте Python выберите Windows installer (64-bit) для актуальной версии Python 3.

Шаг 2. Запустите установщик правильно

Откройте .exe-установщик.

На первом экране обязательно поставьте галочку:

Add Python to PATH (Добавить Python в PATH)

Нажмите Install Now (подходит большинству).

Если выбираете Customize installation, убедитесь, что включены:

pip

py launcher

(опционально) tcl/tk and IDLE – если хотите иметь IDLE

Подсказка: галочка Add Python to PATH сильно упрощает жизнь. Без неё команда python в терминале может “не находиться”.

Шаг 3. Проверка установки

Откройте PowerShell или Командную строку.

Введите:

python –version

Должно показать что-то вроде Python 3.12.x.

Проверьте pip:

pip –version

Если команда python не работает

Попробуйте:

py –version

На Windows часто используется запуск через py launcher.

Если py работает, можно запускать так:

py -m pip –version

4) Установка на macOS

На macOS часто уже есть Python, но он может быть системным и не тем, который нужен. Рекомендуется установить актуальный Python 3 отдельно.

Вариант A (рекомендуется новичкам): официальный установщик

На официальном сайте Python выберите macOS installer для вашей версии macOS.

Откройте .pkg и пройдите установку.

Проверка

Откройте Terminal и выполните:

python3 –version

pip3 –version

Подсказка: на macOS команда чаще python3, а не python.

Важное замечание про системный Python

Не удаляйте и не “ломайте” системный Python, который использует macOS. Работайте с установленным вами python3.

5) Установка на Linux (Ubuntu/Debian, Fedora, Arch и др.)

Во многих дистрибутивах Python уже установлен. Задача – убедиться, что есть Python 3 и pip.

Шаг 1. Проверка

Откройте терминал:

python3 –version

Шаг 2. Установка через менеджер пакетов (типовой путь)

Дальше команды зависят от дистрибутива:

Ubuntu/Debian:

обычно пакет называется python3 и python3-pip

Fedora:

пакеты вида python3 и python3-pip

Arch:

пакеты python и python-pip (в Arch python обычно уже Python 3)

Установку выполняйте через стандартный менеджер пакетов вашей системы (APT/DNF/Pacman и т.п.).

Шаг 3. Проверка pip

pip3 –version

Подсказка: если pip3 не находится, установите пакет pip для Python 3 (часто называется python3-pip).

6) Первое включение: интерактивный режим и запуск файла

Интерактивный режим (REPL)

Это режим “ввёл команду – сразу получил результат”.

Windows:

python

или

py

macOS/Linux:

python3

Проверьте:

print("Hello, Python!")

Выход из режима:

exit() или quit()

либо Ctrl+Z (Windows) / Ctrl+D (macOS/Linux)

Запуск программы из файла

Создайте файл hello.py с содержимым:

print("Hello!")

Запустите:

Windows:

python hello.py

или:

py hello.py

macOS/Linux:

python3 hello.py

7) Редакторы и IDE: что выбрать новичку

Ниже – варианты от простого к более “профессиональному”. Выберите один и работайте в нём первые недели, чтобы не распыляться.

1) Thonny (очень удобен для начинающих)

Плюсы:

максимально простой интерфейс

легко запускать код, есть подсказки

удобно разбирать ошибки

Минусы:

меньше функций для больших проектов

Где взять: официальный сайт Thonny (раздел загрузок под вашу ОС).

2) Visual Studio Code (универсальный редактор)

Плюсы:

популярный, мощный, бесплатный

расширения для Python, подсветка, автодополнение, терминал

Минусы:

нужно поставить расширение Python и немного настроить

Где взять: официальный сайт VS Code или магазин приложений вашей ОС.

Мини-настройка:

Установите расширение Python (внутри VS Code: Extensions).

Выберите интерпретатор (обычно VS Code сам предложит).

3) PyCharm (IDE для Python)

Плюсы:

“всё в одном”: проекты, запуск, отладка, подсказки

подходит для серьёзной разработки

Минусы:

может быть тяжеловат для слабого ПК

интерфейс насыщенный

Где взять: официальный сайт JetBrains (версия Community обычно достаточна для обучения).

4) IDLE (идёт вместе с Python)

Плюсы: уже установлен вместе с Python, простое окно редактора.

Минусы: функциональность ограничена, чаще используют как запасной вариант.

8) Частые проблемы и быстрые решения

Проблема: “python не является внутренней или внешней командой” (Windows)

Переустановите Python и включите Add Python to PATH.

Либо используйте py вместо python.

Проблема: установилось несколько Python, путаница версий

Проверьте версии:

python –version

python3 –version

py –version

На Windows удобно так:

py -0

(покажет доступные версии, если установлен launcher)

Проблема: pip устанавливает не туда / не находится

Используйте надёжный способ через модуль:

Windows:

py -m pip –version

py -m pip install requests

macOS/Linux:

python3 -m pip –version

python3 -m pip install requests

9) Рекомендация по рабочей папке для задач

Создайте папку, например:

PythonTasks Внутри – подпапки по темам:

01_basics, 02_conditions, 03_loops и т.д.

Именуйте файлы понятно:

task_01.py, task_02.py или sum_numbers.py.

10) Итог: минимальный чек-лист

Установлен Python 3.x

В терминале работает:

python –version

или:

python3 –version

Работает pip:

python -m pip –version

или:

python3 -m pip –version

Выбран редактор: Thonny / VS Code / PyCharm

Умеете:

открыть REPL

запустить файл hello.py

## Глава 2. Функции Python

В Python нет “команд” как отдельной сущности: обычно под этим понимают ключевые слова (keywords) и встроенные функции (built-ins). Ниже – списки с кратким синтаксисом.

Ключевые слова Python (keywords)

Литералы и логика

True, False – булевы значения

Синтаксис: x = True

None – отсутствие значения

Синтаксис: x = None

and, or, not – логические операторы

Синтаксис: a and b, a or b, not a

is, is not – тождество объектов

Синтаксис: a is b, a is not b

in, not in – принадлежность

Синтаксис: x in seq, x not in seq

Условия

if / elif / else

Синтаксис: if cond: … elif other_cond: … else: …

Циклы и управление потоком

for

Синтаксис: for item in iterable: …

while

Синтаксис: while cond: …

break – выход из цикла

Синтаксис: break

continue – следующая итерация

Синтаксис: continue

pass – пустой оператор (заглушка)

Синтаксис: pass

else в циклах – выполнится, если цикл завершился без break

Синтаксис: for x in xs: … else: …

Функции

def – объявление функции

Синтаксис: def name(params): … return value

return – возврат значения

Синтаксис: return expr / return

lambda – анонимная функция

Синтаксис: lambda args: expression

Исключения

try / except / else / finally

Синтаксис: try: … except SomeError as e: … else: … finally: …

raise – выбросить исключение

Синтаксис: raise ErrorType("message") или raise

assert – проверка утверждения

Синтаксис: assert condition, "message"

Контекстный менеджер

with – вход/выход из контекста

Синтаксис: with expr as var: …

Импорт

import

Синтаксис: import module / import module as alias

from … import …

Синтаксис: from module import name / from module import name as alias / from module import *

Классы и области видимости

class – объявление класса

Синтаксис: class Name(Base): …

global – имя из глобальной области

Синтаксис: global x

nonlocal – имя из внешней (но не глобальной) области

Синтаксис: nonlocal x

Генераторы

yield – вернуть значение из генератора

Синтаксис: yield expr

yield from – делегировать генерацию

Синтаксис: yield from iterable

Удаление

del – удалить имя/элемент/срез

Синтаксис: del name, del a[i], del a[i:j]

Асинхронность

async def – асинхронная функция

Синтаксис: async def f(): …

await – ожидание

Синтаксис: result = await coro

async for

Синтаксис: async for item in aiter: …

async with

Синтаксис: async with expr as var: …

Структурное сопоставление (Python 3.10+)

match / case

Синтаксис: match value: case pattern: … case _: …

2) Встроенные функции Python (built-in functions)

Приведение типов и конструкторы

bool(x=False)

int(x=0, base=10)

float(x=0.0)

complex(real=0, imag=0)

str(obj="")

bytes(source=b"", encoding=None, errors="strict")

bytearray(source=b"", encoding=None, errors="strict")

memoryview(obj)

list(iterable=())

tuple(iterable=())

set(iterable=())

frozenset(iterable=())

dict(mapping_or_iterable=(), kwargs)

range(stop) / range(start, stop[, step])

Числа и агрегирование

abs(x)

round(number[, ndigits])

pow(base, exp[, mod])

divmod(a, b)

sum(iterable, start=0)

min(iterable, *[, key, default]) / min(a, b, … *[, key])

max(iterable, *[, key, default]) / max(a, b, … *[, key])

Проверки и сравнения

all(iterable)

any(iterable)

isinstance(obj, classinfo)

issubclass(cls, classinfo)

callable(obj)

Последовательности, итераторы, преобразования

len(s)

sorted(iterable, *, key=None, reverse=False)

reversed(seq)

enumerate(iterable, start=0)

zip(*iterables, strict=False)

map(func, iterable, …)

filter(func, iterable)

iter(obj[, sentinel])

next(iterator[, default])

slice(stop) / slice(start, stop[, step])

Ввод/вывод

print(*objects, sep=" ", end="\n", file=None, flush=False)

input([prompt])

Атрибуты и интроспекция объектов

type(obj) / type(name, bases, dict)

id(obj)

hash(obj)

repr(obj)

format(value[, format_spec])

ascii(obj)

getattr(obj, name[, default])

setattr(obj, name, value)

hasattr(obj, name)

delattr(obj, name)

dir([obj])

Пространства имён, выполнение кода

globals()

locals()

vars([obj])

eval(expression[, globals[, locals]])

exec(object[, globals[, locals]])

compile(source, filename, mode, flags=0, dont_inherit=False, optimize=-1)

Файлы

open(file, mode="r", buffering=-1, encoding=None, errors=None, newline=None, closefd=True, opener=None)

ООП и дескрипторы

object()

super([type[, obj]])

property(fget=None, fset=None, fdel=None, doc=None)

classmethod(function)

staticmethod(function)

Документация и отладка

help([object])

breakpoint(*args, kws)

Unicode и представления чисел

ord(c)

chr(i)

bin(x)

oct(x)

hex(x)

Асинхронные итераторы (в новых Python 3.x)

aiter(async_iterable)

anext(async_iterator[, default])

Низкоуровневый импорт

__import__(name, globals=None, locals=None, fromlist=(), level=0)

3) Часто путают с “встроенными командами”, но это синтаксис (не функции)

Операторы (не built-ins)

Арифметика: + – * / // %

Сравнение: == != < <= > >=

Побитовые: & | ^ ~ << >>

Присваивание: =, а также += -= *= /= //= %= = &= |= ^= <<= >>=

Присваивание в выражении: :=

Индексация/срезы: a[i], a[i:j], a[i:j:k]

Литералы коллекций

Список: [1, 2, 3]

Кортеж: (1, 2)

Множество: {1, 2}

Словарь: {"a": 1}

Генератор: (f(x) for x in xs)

Включения: [f(x) for x in xs if cond], {…}, {k: v …}

## Глава 3. Отладка кода

Отладка как навык – как находить ошибки и доводить код до работоспособности

Отладка – это не «пожарная команда», которая приезжает, когда всё сломалось. Это базовый инструмент программиста, такой же важный, как переменные, циклы и функции. Код почти никогда не начинает работать идеально с первой попытки, даже если вы опытны. Отличие сильного разработчика от начинающего чаще всего не в «умении сразу написать правильно», а в умении быстро и методично понять, почему неправильно, и исправить.

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

1) Три вида ошибок: сначала определите, что именно происходит

Почти любую проблему можно отнести к одной из трёх категорий:

1.1. Синтаксические ошибки (SyntaxError)

Код не запускается вообще.

Признаки:

– Python пишет `SyntaxError`, указывает строку и место.

– Часто это: пропущенная скобка, двоеточие, неправильные кавычки, смешение табов и пробелов.

Как чинить:

– верить указателю Python, но проверять строку выше (иногда ломается там);

– сверять скобки, кавычки, двоеточия в `if/for/while/def`;

– не смешивать tab и spaces (в IDE включить «показывать невидимые символы»).

1.2. Ошибки времени выполнения (RuntimeError/Exception)

Код запускается, но падает во время работы.

Признаки:

– `ValueError`, `IndexError`, `KeyError`, `TypeError`, `ZeroDivisionError` и т. д.

– Есть traceback (стек вызовов) – это карта того, где всё сломалось.

Как чинить:

– читать traceback снизу вверх: последняя строка – место аварии;

– понять, какие значения были у переменных в момент падения;

– добавить проверки, обработку крайних случаев, исправить логику.

1.3. Логические ошибки (Wrong Answer)

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

Признаки:

– программа не падает;

– но ответы не совпадают с ожиданием/тестами.

Как чинить:

– формализовать ожидаемое поведение;

– искать контрпример: минимальный вход, где ответ неправильный;

– проверять инварианты и промежуточные значения.

2) Traceback: умение читать его экономит часы

Пример:

python

a = [1, 2, 3]

print(a[3])

Отладка как навык – как находить ошибки и доводить код до работоспособности

2) Traceback: умение читать его экономит часы

Пример:

a = [1, 2, 3]

print(a[3])

Ошибка:

IndexError: list index out of range

Traceback (если пример внутри функции/файла) обычно выглядит примерно так:

Traceback (most recent call last):

File "main.py", line 10, in <module>

print(a[3])

IndexError: list index out of range

Как читать traceback:

– Читайте снизу вверх.

– Последняя строка содержит тип исключения и текст ошибки.

– Строки выше показывают цепочку вызовов (какие функции вызывали какие).

– Самая полезная часть: файл и номер строки, где произошло исключение.

Практика чтения:

1) Определить тип исключения: IndexError.

2) Понять, какое предположение нарушено: индекс 3 существует.

3) Проверить реальные данные: длина списка 3, допустимые индексы 0..2.

4) Исправить: проверить границы или изменить индекс.

Типовые подсказки по исключениям:

– ValueError: неверное преобразование типов или неверный формат данных.

Часто возникает при int(input()) на пустой строке или при split() на неожиданных данных.

– TypeError: операция применена к неподходящему типу.

Например, попытка сложить строку и число.

– KeyError: ключа нет в словаре.

Часто исправляется get() или предварительной проверкой in.

– IndexError: выход за границы списка/строки.

Часто исправляется корректной границей цикла или проверкой длины.

– ZeroDivisionError: деление на ноль.

Исправляется обработкой случая b == 0.

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

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

3) Минимальный воспроизводимый пример (MRE)

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

Цель MRE:

– убрать всё лишнее;

– оставить только код, необходимый для проявления ошибки;

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

Как сделать MRE на практике:

1) Зафиксируйте входные данные, на которых ошибка проявилась.

2) Уменьшайте вход:

– если список большой, оставьте несколько первых элементов;

– если матрица большая, оставьте маленькую матрицу (2x2, 3x3);

– если ошибка связана со строкой, попробуйте убрать лишние символы.

3) Убирайте код:

– комментируйте блоки, которые не влияют на ошибку;

– выносите логику в отдельный файл/функцию;

– оставьте только то, что нужно для воспроизведения.

Пример: ошибка при обработке массива длины 1.

Вместо большого теста используйте:

n = 1, a = [5]

Это поможет быстрее понять, где допущено предположение "n >= 2".

Почему MRE ускоряет отладку:

– меньше строк кода – меньше вариантов, где ошибка;

– быстрее запуск;

– легче добавить печать промежуточных значений;

– легче объяснить ошибку другому человеку (или самому себе через день).

4) Алгоритм отладки: методичный план действий

4.1. Шаг 1. Зафиксировать симптом

Симптом должен быть записан в явном виде:

– вход;

– фактический вывод;

– ожидаемый вывод;

– что именно пошло не так (падает/зависает/неверный ответ).

Пример фиксации:

Вход:

5

1 2 3 4 5

Ожидаю: 15

Получаю: 10

4.2. Шаг 2. Классифицировать ошибку

– SyntaxError: код не запускается.

– Exception: код падает.

– Wrong Answer: код работает, но ответ неверный.

– Timeout (TLE): код работает слишком долго.

– Memory Limit: расход памяти слишком большой.

Даже в учебных задачах полезно выделять отдельно "слишком долго" и "слишком много памяти".

4.3. Шаг 3. Проверить ввод/вывод

Проверка ввода/вывода часто даёт результат быстрее, чем проверка алгоритма.

Список типичных проблем:

– вход может быть в нескольких строках, а вы читаете в одной;

– в конце строки есть пробелы, переносы, пустые строки;

– вы печатаете лишние строки/слова;

– вы перепутали разделители;

– вы перепутали 0-based и 1-based индексацию;

– вы забыли привести типы (строки вместо чисел).

Практический приём:

Сначала выведите то, что вы считали:

print(n)

print(numbers)

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

4.4. Шаг 4. Проверить предположения о диапазонах

Типовые предположения, которые ломаются:

– n >= 1, а на самом деле n может быть 0;

– список не пустой, но может быть пуст;

– все числа положительные, а могут быть отрицательные;

– строки без пробелов, а пробелы возможны;

– граф связный, но может быть не связным.

4.5. Шаг 5. Локализовать место ошибки

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

Способы:

– print-debugging;

– asserts;

– отладчик pdb;

– логирование в файл (для больших выводов);

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

4.6. Шаг 6. Внести минимальное исправление

Правило: исправляйте одну вещь за раз.

Если вы исправили сразу три места, вы не узнаете, что именно было причиной.

4.7. Шаг 7. Регресс-тест

Прогоните:

– исходный тест, где было плохо;

– минимальные тесты;

– крайние случаи;

– несколько случайных тестов (при возможности).

Если задача алгоритмическая, полезно сравнить с "наивным" решением на маленьких размерах.

5) Print-debugging: как печатать так, чтобы это помогало

Print-debugging работает, если вывод организован.

Ошибки начинающих:

– печатать слишком много, тонуть в выводе;

– печатать без подписей, не понимать, что за число;

– печатать не там, где меняется состояние, а "где-то рядом".

5.1. Что печатать

– ключевые переменные состояния (сумма, индексы, текущий ответ);

– размеры структур (len массива, размеры матрицы);

– текущие значения на границах (первый/последний элемент);

– факт выполнения ветки if (например, "entered branch A").

Пример:

print("i=", i, "x=", x, "best=", best)

5.2. Где печатать

– сразу после чтения входа;

– внутри места, где ответ обновляется;

– внутри ветвлений, которые редко выполняются;

– перед местом, где программа падает (если известно).

5.3. Как ограничить вывод

Для больших циклов:

if i < 10:

print(…)

Или печатать раз в 1000 шагов:

if steps % 1000 == 0:

print(steps, state)

5.4. Как не забыть убрать отладочный вывод

– соберите все debug-печати под флагом:

DEBUG = False

if DEBUG:

print(…)

Перед сдачей решения поставьте DEBUG = False.

6) assert: дешёвая страховка и быстрый способ поймать логическую ошибку

assert проверяет условие и падает, если оно ложное.

Это способ превратить "неверный ответ" в "точку, где сломалась логика".

Примеры инвариантов:

– индексы в диапазоне:

assert 0 <= i < n

– длины совпадают:

assert len(a) == n

– значения не отрицательны (если по условию должны быть):

assert x >= 0

Пример для двух указателей:

assert 0 <= left <= right < n

Полезно добавлять сообщение:

assert condition, "explanation"

Пример:

assert right < n, "right pointer out of bounds"

Важно: assert стоит использовать в отладке и обучении.

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

7) Отладчик pdb: когда print уже не хватает

pdb полезен, когда:

– ошибка проявляется не сразу;

– нужно посмотреть последовательность изменений;

– много переменных, печатать неудобно.

Как поставить точку останова:

import pdb; pdb.set_trace()

Мини-команды:

– n (next): выполнить текущую строку и перейти к следующей

– s (step): зайти внутрь функции

– c (continue): продолжить до следующей остановки

– p expr (print): вывести значение выражения

– l (list): показать кусок кода вокруг текущей строки

– q (quit): выйти

Совет: в pdb важно задавать конкретный вопрос.

Например: "почему dist здесь стал отрицательным" или "почему не срабатывает ветка".

Практика:

– поставьте breakpoint перед подозрительным условием;

– выполните несколько шагов;

– посмотрите значения;

– проверьте, какая ветка выполняется и почему.

8) Типовые источники runtime-ошибок и как их диагностировать

8.1. IndexError в циклах

Типовая причина: неверная граница.

– range(n) даёт индексы 0..n-1

– range(1, n) даёт 1..n-1

– range(1, n+1) даёт 1..n

Диагностика:

– напечатать n и индекс i перед обращением;

– напечатать len массива;

– проверить условия остановки.

8.2. ValueError при int()

Причины:

– строка пустая;

– строка содержит не число (например, "10 20");

– есть лишние символы.

Диагностика:

– print(repr(line)) перед преобразованием;

– проверить split().

8.3. KeyError в словаре

Причины:

– ключ не добавлен;

– вы ожидаете, что ключ существует.

Исправления:

– использовать get(key, default);

– предварительно проверить if key in dict.

8.4. TypeError из-за смешения типов

Причины:

– числа как строки;

– None вместо значения;

– список вместо числа.

Диагностика:

– print(type(x), x)

– проследить, где переменная присваивается.

8.5. RecursionError

Причины:

– рекурсия слишком глубока (DFS на большом графе/дереве);

– бесконечная рекурсия из-за отсутствия базового случая.

Исправления:

– переписать на итеративный вариант;

– увеличить лимит, если это оправдано:

import sys

sys.setrecursionlimit(10**7)

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

9) Логические ошибки: как находить неверный ответ

9.1. Начать с маленького теста

Если вы не можете проверить ответ вручную, вы не можете эффективно отлаживать.

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

9.2. Метод "ручной прогон"

Возьмите маленький вход и выполните алгоритм на бумаге:

– какие значения переменных после каждого шага;

– когда должен обновиться ответ.

Сравните с реальным выводом debug-печати.

9.3. Дифференциальная проверка (сравнение с наивным решением)

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

Пример подхода:

– генерировать маленький массив длины до 8;

– вычислять ответ двумя способами;

– если ответы различаются, печатать тест и останавливать программу.

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

9.4. Инварианты

Поддерживайте свойства, которые всегда должны быть истинны.

Примеры:

– в BFS расстояния не убывают при извлечении из очереди (для обычного BFS);

– в Дейкстре извлечённая вершина имеет минимальное расстояние;

– в сортировке после i шагов первые i элементов отсортированы.

Если инвариант нарушен, место нарушения – точка ошибки.