Читать онлайн «Жемчужины творчества программистов»

Programming Pearls JON BENTLEY AT&T Bell Laboratories Murray Hill, New Jersey ADDISON-WESLEY PUBLISHING COMPANY Л • Бентл и Жемчужины творчества программистов Перевод с английского М. Г. Логунова Под редакцией И. Г. Шестакова Москва «Радио и связь» 1990 Редакция переводной литературы Бентли Д. Б 46 Жемчужины творчества программистов: Пер. с англ. - М. : Радио и связь, 1990. - 224 с: ил. ISBN 5-256-00704-L В книге американского автора на различных примерах из практики программирования показано, как хорошее понимание особенностей поставленной задачи позволяет нантн оптимальное по быстродействию, объему требуемой памяти, легкости модификации решения. Наряду с конкретными примерами даны общие рекомендации по составлению оптимальных алгоритмов и программ. Рассмотрение построено по следующему принципу: постановка задачи, пример традиционного решения н объяснение его недостатков, углубленный анализ задачи и найденное в результате этого лучшее решение, изложение ряда принципов грамотного программирования. Для программистов. Б 2404010000-06S ^ ББК 32. 973 046 (01)-90 БЕНТЛИ ДЖОН Жемчужины творчества программистов Заведующий редакцией Ю. Г. Ивашов Редактор М. Г. Коробочкина Обложка художника Б. И. Николашина Художественный редактор А. С. Широков Технический редактор Т. Г. Родина Корректор Л. А. Буданцева ИБ№1845 Подписано в печать 12. 02. 90 Формат 60 х 88/16 Бумага офсетная № 2 Гарнитура "Пресс-роман" Печать офсетная Усл. печ. л. 13,72 Усл. кр. -отт. 14,33 Уч. нзд. л. 13,75 Тираж 20 000 экз. Изд. № 22732 Зак. № 6998 Цена 90 к. Издательство "Радио и связь". 101000, Москва, Почтамт, а/я 693 Ордена Октябрьской Революции и ордена Трудового Красного Знамени МПО "Первая Образцовая типография" Государственного комитета СССР по печати. 113054, Москва, Валовая, 28. ISBN 5-256-00704-1 (рус. ) © 1986 by Bell Telephone Laboratories, ISBN 0-20ЫОЗЗЫ (англ. ) Incorporated © Перевод на русский язык, примечания. Логунов М. Г. , 1990 ОГЛАВЛЕНИЕ Предисловие . 8 ЧАСТЬ 1. Введение 11 Глава 1- Как расколоть орешек. 11 1. 1. Дружеский разговор 12 1. 2. Точная формулировка задачи 13 1. 3. Разработка программы 13 1. 4. Набросок решения 15 1. 5. Основные принципы 16 1. 6. Задачи 17 1. 7. Литература для дополнительного чтения 20 Глава 2. Ага! Алгоритмы 21 2. 1. Три задачи. * 21 2. 2. Вездесущии двоичный поиск 22 2. 3. Снпа примитивов , 24 2. 4. Соберем все вместе (сортировка) 26 2. 5. Основные принципы * 27 2. 6. Задачи 29 2. 7. Литература для вспомогательного чтения < 31 2. 8. Реализация программы для анаграмм {дополнение) 31 Глава 3. Программы, работающие со структурами данных 34 3. 1. Программа обработки результатов обследования 34 3. 2. Формирование писем 37 3. 3. Примеры 41 3. 4. Большая по объему программа 43 3. 5. Основные принципы 45 3. 6. Задачи 46 3. 7. Литература для дополнительного чтения 49 Глава 4. Написание программ, не содержащих ошибок 49 4. 1. Двоичный поиск "бросает вызов" 49 4. 2. Написание программы 51 4. 3. Разбор программы 54 4-4. Реализация программы 57 4. 5. Основные принципы 59 4. 6.