Как однажды заметил мой коллега, учиться можно как по теоретическим материалам, так и по примерам и листингам. Хороших учебников по программированию написано уже достаточно много. А вот найти книгу, посвященную интересным практическим примерам, уже сложнее. Можно упомянуть, в частности, Жемчужины программирования Джона Бентли, Этюды для программистов Чарльза Уэзерелла, Практика программирования Брайана Кернигаиа и Роба Пайка. Ситуация, по правде говоря, не особо радует. Если, скажем, юристы и врачи посвящают достаточно много времени изучению случаев из практики, почему бы программистам не делать то же самое?

Конечно, здесь надо сделать пару оговорок. Во-первых, практические примеры встречаются во многих книгах, но, как правило, лишь в качестве пояснений к теоретическому материалу. Во-вторых, сборники задач (иногда с решениями) тоже публикуются, но здесь уже вступают в игру принципы отбора примеров. Как правило, задачники предназначены либо для школ, и в этом случае состоят из типовых упражнений, либо для кружков, занимающихся подготовкой к олимпиадам по программированию (соответственно, составлены такие сборники из задач олимпиадного характера). К сожалению, авторы далеко не всегда берут на себя труд завернуть задачу в какую-либо осмысленную обёртку, помогающую понять практическую пользу того или иного иллюстрируемого алгоритма. Иногда условия задания становятся совсем уж нереалистичными ( двигаясь из комнаты в комнату, принц закрывал на ключ дверь, через которую он прошел, после он уже не мог воспользоваться этой дверью ), а идеи решений - слишком узкоспециализированными.

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

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

приведённые в книге алгоритмы довольно далеки от совершенства. Если можете поделиться лучшим подходом - напишите мне письмо, буду только рад возможности повысить качество решений в следующем издании книги. Адрес моей электронной почты - maxim mozgovoy@hotbox.ru.

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

В заключение хочу поблагодарить Сергея Караковского, который не только сделал, несколько ценных замечаний по формулировке заданий, но и помог мне вовремя подготовить репхения (ему принадлежат программы Автострада , Лабиринт для лазера и Сортировка сайтов ), а также Марка Фипкова, много сделавшего для повышения качества книги и по возможности старавшегося ускорить её выход. Ему также принадлежит замечательная фраза, в двух словах объясняющая идеолошческую направленность сборника: Грубо говоря, изначально человек знает, что такое топор, и, в принципе, знает как им долбать. Мы же этому человеку показываем, какие вещи и как он может сделать .

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

На мой взгляд, именно задача построения здания, а не изготовления кирпичей является центральной для разработчика программного обеспечения. Сложность систем, а не отдельных алгоритмов заставляет создавать новые парадигмы программирования, такие как структурное программирование или ООП, заниматься архитектурой проекта, использовать методики программотехники (software engineering).

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

Книга, которую вы держите в руках, посвящена, в первую очередь, задачам проектного типа. Мне также хочется, чтобы решение иллюстрировало некоторый важный или интересный принцип (поиск методом А*, черепашью графику, метод Монте-Карло) и было полезным в повседневной практике программирования. Иногда можно и расслабиться, рассмотреть какую-нибудь малополезную, но интересную задачку. Впрочем, я старался особо этим не увлекаться. Поскольку основная цель книги - научить чему-то новому, а не заставить решать задачи самостоятельно любой ценой, многие проекты снабжены подсказками и решениями. Разумеется, чтобы не раздувать код, везде приходилось предполагать корректность входных данных, наличие достаточного объёма свободной памяти и тому подобные иногда вступающие в противоречие с практикой вещи.

У приводимых листингов тоже есть своя отличительная особенность: используя язык С++, я старался не избегать его современных возможностей, таких как шаблоны и алгоритмы библиотеки STL. При описании решений алгоритмических задач авторы книг почему-то редко выходят за пределы программирования в стиле семидесятых годов (Pascal и С). Получается своего рода порочный круг: авторы намеренно упрощают листинги, чтобы их мог понять даже начинающий, а читатели затем пользуются программами из книг в качестве эталонов хорошего стиля разработки. В итоге даже сейчас то и дело приходится сталкиваться с кодом, написанным в совершенно устаревшем стиле и, соответственно, наделённым массой недостатков (ради искоренения которых и были разработаны современные технологии программирования). Поэтому решения - это не просто ответы на задачи, но и важная часть книги. Даже если вы сами можете справиться с заданием, загляните в решение. Если оно окажется лучше вашего, вы научитесь чему-то новому. Если хуже - порадуетесь своему успеху. Кстати, многие

ГЛАВА 1. СТРУКТУРЫ ДАННЫХ