Read the book: «Алгоритмы на Python. 24 задачи с решениями и проверками»

От работающего примера к обоснованному решению

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

В этой книге 24 самостоятельные задачи. Это не курс синтаксиса Python с нуля. Предполагается, что вы можете определить функцию, написать цикл, обратиться к списку и словарю и понять логическое условие. Новые структуры и приёмы появляются через конкретную работу: сначала формулируем контракт, затем выбираем состояние, которое будет поддерживать алгоритм.

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

Условия, учебные данные и объяснения подготовлены для этого практикума. Сами алгоритмические идеи общеизвестны: мы не выдаём двоичный поиск или поиск в ширину за авторские открытия. Книга подготовлена с помощью ИИ; решения выполняются и проверяются на примерах и дополнительных случаях. Автоматические тесты помогают найти ошибки, но не заменяют понимания условий и не доказывают пригодность программы для любых производственных данных.

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

Среда и безопасный учебный запуск

Решения проверяются на Python 3.12. Используются только встроенные возможности и стандартная библиотека; установка пакетов не нужна. Интерпретатор берите из официального источника python.org. Команда запуска зависит от системы: часто это python3 task.py или py task.py. Важно, чтобы выбранная команда действительно запускала Python 3, а не другую установленную программу.

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

Данные вне явно оговорённого контракта не обязаны обрабатываться красиво. Например, двоичный поиск здесь получает уже отсортированный список, а алгоритм Дейкстры — неотрицательные веса. Отдельная промышленная оболочка могла бы проверять и отклонять неверный ввод. Такие проверки стоят времени и места; отсутствие оболочки не превращает ограниченный учебный алгоритм в универсальный сервис.

Функция называется solve во всех заданиях, но это разные функции. Не складывайте решения подряд в один файл: последнее определение заменит предыдущие. Для очередной задачи используйте отдельную пустую папку или новое имя файла и переносите полный блок решения вместе с блоком проверок этой же задачи. Условия и ожидаемый вывод копировать как Python-код не нужно.

Перенос кода из электронной книги

Отступы Python имеют смысл, но электронная читалка может схлопывать несколько пробелов в один. Поэтому перед каждой строкой решения и проверок стоит служебная вертикальная черта │, а каждый пробел ОБЯЗАТЕЛЬНОГО НАЧАЛЬНОГО отступа показан средней точкой ·. Например, │····return result означает четыре обычных пробела перед return result. Восемь точек означают восемь пробелов. Слева от черты читалка может добавлять собственные поля; они не относятся к программе.

Черта и средние точки — обозначения оформления, а не синтаксис Python и не знаки умножения. При переносе удалите черту вместе с полями слева от неё и замените каждую среднюю точку одним обычным пробелом. Обычные точки в именах методов, например list.append, не трогайте: это другой символ. Можно перепечатать короткое решение вручную или воспользоваться подготовительным скриптом ниже. Он снимает оформление, не меняя вычислений алгоритма. Средние точки используются только для начальных отступов, не внутри строковых данных задач.

Для автоматического переноса создайте новую пустую папку. Скопируйте из ОДНОЙ задачи весь блок решения, затем её блок «Проверки для запуска» в обычный текстовый файл copied.txt, сохранённый как UTF-8. Создайте в той же папке clean.py и введите следующие десять строк без служебных черт. У всех этих десяти строк левый край одинаковый: обязательных отступов в самом подготовительном скрипте нет. Запустите python3 clean.py, затем python3 task.py.

from pathlib import Path

text = Path("copied.txt").read_text(encoding="utf-8")

lines = text.splitlines()

marked = [s for s in lines if "│" in s]

stripped = [s.split("│", 1)[1] for s in marked]

clean = [s.replace("·", " ") for s in stripped]

result = "\n".join(clean).replace("\u00a0", " ") + "\n"

f = open("task.py", "x", encoding="utf-8")

f.write(result)

f.close()

Подготовительный скрипт создаёт task.py в режиме x: если такой файл уже существует, выполнение остановится с FileExistsError и старый файл останется нетронутым. Для следующей задачи безопаснее взять новую папку. Не меняйте режим на w только ради обхода ошибки, если в папке лежит нужная работа. Скрипт ничего не скачивает и не запускает автоматически; просмотрите получившийся task.py перед запуском.

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

Контракт, инвариант и контрпример

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

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

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

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

Как читать оценки времени и памяти

Буква n обычно обозначает число входных элементов; для графа отдельно используются число вершин V и число рёбер E. Запись O(n) описывает порядок роста числа операций при увеличении размера задачи, а не время в миллисекундах. Два линейных алгоритма могут заметно различаться на конкретной машине. Измерение помогает выбирать реализацию, но не заменяет оценку поведения на растущем вводе.

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

Дополнительная память — то, что алгоритм создаёт сверх входа. Если возвращаемый результат сам может содержать n элементов, мы отдельно говорим, включён ли он в оценку. Копия входного списка занимает память, даже если сортировка этой копии называется «на месте». Рекурсивные вызовы также используют стек. Экономия одной таблицы не означает отсутствия остальных затрат.

Для динамического программирования размер числового параметра может быть важнее количества входных элементов. Таблица до суммы T содержит T+1 ячейку, хотя само число T записывается гораздо короче. Поэтому решение, быстрое для небольшого учебного T, не обязательно подходит для огромных значений. В этой книге нет обещаний, что любые большие входы уложатся в память.

Пять шагов на одну задачу

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

В блоке проверок строка assert сравнивает фактический ответ с ожидаемым. Если сравнение ложно, Python выдаёт AssertionError и не доходит до заключительного сообщения OK. Отсутствие ошибки означает лишь прохождение именно этих проверок. Не запускайте учебные проверки с флагом -O: в таком режиме assert может быть отключён.

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

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

Задача 1. Первое появление в журнале

Редактор выгрузил названия рубрик в порядке открытия вкладок. Ему нужен список рубрик без повторов, но именно в порядке первого появления: алфавитная сортировка скроет последовательность работы. Функция solve(items) получает конечный список строк и возвращает новый список. Равенство строк обычное, чувствительное к регистру и пробелам: 'Код', 'код' и 'код ' — разные значения. Пустая строка допустима, пустой вход даёт пустой результат. Вход не изменяется; каждое различное значение должно остаться ровно один раз.

Пример

Аргументы solve: (['карты', 'почта', 'карты', 'архив', 'почта'],)

Ожидаемый ответ: ['карты', 'почта', 'архив']

Подсказка

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

Решение

│def solve(items):

│····seen = set()

│····result = []

│····for item in items:

│········if item not in seen:

│············seen.add(item)

│············result.append(item)

│····return result

Проверки для запуска

│cases = [((['карты', 'почта', 'карты', 'архив', 'почта'],),

│··['карты', 'почта', 'архив']),

│·(([],), []),

│·((['', '', 'а', ''],), ['', 'а']),

│·((['Код', 'код', 'Код', 'код '],), ['Код', 'код', 'код ']),

│·((['x', 'x', 'x'],), ['x'])]

│for args, expected in cases:

│····assert solve(*args) == expected

│print('OK: задача 1')

После успешных проверок: OK: задача 1

Почему это работает

На примере сначала обе структуры пусты. 'карты' отсутствует в seen, поэтому попадает и в множество, и в ответ. С 'почта' происходит то же самое. Второе появление 'карты' не меняет ни одну структуру. Затем добавляется 'архив', а последняя 'почта' пропускается. Таким образом, позиция добавления строки зависит только от её первого появления во входном журнале.

Инвариант после обработки любого префикса таков: seen содержит все различные строки этого префикса, а result — их первые появления в исходном порядке. Если новая строка уже известна, префикс не приобрёл нового значения и менять ответ нельзя. Если строка неизвестна, её текущая позиция неизбежно первая; добавление в конец сохраняет порядок всех предыдущих значений.

Когда обход завершён, инвариант описывает весь вход, а значит, доказывает и полноту результата, и отсутствие повторов, и устойчивость порядка. Само множество не задаёт порядок ответа: его перебор здесь вообще не используется. Строки хешируемы, поэтому подходят для множества; списки внутри items потребовали бы другого контракта. Мы не исправляем регистр и пробелы незаметно для вызывающего кода: это отдельная задача.

Время и память

n — число строк, u — число различных строк. В среднем O(n) хеш-операций и O(u) дополнительной памяти без ответа. Это не гарантия худшего случая: при коллизиях возможно O(n²) сравнений. Хеширование и сравнение длинных строк оплачиваются отдельно по числу просмотренных символов.

Типичная ошибка

Вернуть list(set(items)): повторы исчезнут, но требуемый порядок первого появления не гарантирован. Проверять членство только в result корректно, однако на разных строках даёт O(n²) сравнений.

Измените условие

Можно ли сохранить порядок первых появлений, но вывести каждую строку в верхнем регистре?

Разбор вопроса

Да: проверяйте исходную строку в seen, а в result добавляйте item.upper(). Но разные исходные строки могут дать одинаковый вывод. Если уникальность нужна уже после преобразования, в множество следует класть преобразованное значение.