Д. Кнут - Искусство программирования том 1 (1119450), страница 4
Текст из файла (страница 4)
Наконец-то мне удалось внести полный текст' этой книги в персональный компьютер и таким образом получить ее электронную версию, что позволит в дальнейшем вносить любые изменения в технологию печати и отображения на экране. Такой способ работы дал мне возможность сделать буквально тысячи улучшений; я добился того, о чем так долго мечтал. В этом новом издании я смог проверить каждое слово в тексте, стараясь сохранить юношеский задор моих первоначальных исследований и в то же время внести ббльшую зрелость суждений.
Были добавлены десятки новых упражнений, а на десятки старых даны новые или улучшенные ответы. Таким образом, работа над книгой Искусство программирования продолжает- Ф .. ся. Именно поэтому некоторые части давной книги начинаются пиктограммой "В процессе построения" (это своеобразное извинение за то, что приведены не самые новые данные). Мои папки переполнены важными материалами, которые я планирую включить в окончательное, славное четвертое издание тома 1; оно выйдет, вероятно, через 15 лет.
Но сначала я должен закончить тома 4 и 5. Я хочу, чтобы они были опубликованы сразу же, как только будут готовы к печати. Ббльшая часть тяжелой работы по подготовке этого нового издания была выполнена Филлис Винклер (РЪу111э 'тт11пЫег) и Сильвио Леви (511т1о адану), которые профессионально набирали и редактировали текст второго издания, а также Джеффри Олдхэмом (йейгеу О!дйаш), который конвертировал почти все оригинальные иллюстрации в формат МЕТ1яРОЕТ. Я исправил все ошибки, которые бдительные чнтател~ (Барри) обнаружили во втором издании (а также ошибки, которые, увы, не заметил никто), и постарался избежать появления новых ошибок в новом материале.
Тем не менее я допускаю, что некоторые огрехи все же остались, и хотел бы исправить их как можно скорее. Поэтому за каждую опечатку*, а также ошибку, относящуюся к сути излагаемого материала или к приведенным историяеским сведениям, я охотно заплачу $2,56 тому, кто первым ее найдет. На ЖеЪ-странице, адрес которой приведен на обороте титульной страницы, содержится текущий список всех ошибок, о которых мне сообщили*".
Стпаифорд, Калифорния Апрель 1997 За последние двадцать лет мио изменился. — ьилл гейтс (ви аэсез) (гээб) * Имеется в виду оригинал настоящего издания. — Прим, рее. 'т Ощибкн, известные ня момент подгошеки русско. о издания, были исправлены. — Прим. ред. 1, Начать 3. айь-1 18.
Отдохнуть Нет 17. й? < 12? ресно? Нет 5. Инте 1б. Увеличить ?У Конец главы 15. Спать! Первый раз Да тали? 14. Ус Нет Да Нет Да 9. 2-1-2 =5? Нет Блок-схема процедуры чтения книг этой серии. 2. Читать с х?11 — х1х 4. Начать главу Г? ?. Начать новый раздел 1б. Проверить формулы б. ?У < 2? Да 11.
Просиотреть математический материал 12. Выполнить упражнения 13. Проверить ответы Процедура чтения книг этой серии 1. Начните читать настоящую процедуру, если вы этого еще не сделали. Продологеайте в точном еоотвеглствии с указанными шагами. (Общая форма этой процедуры и сопровождающей ее блок-схемы будет использоваться на протяжении всей книги.) 2.
Прочтите примечания к упражнениям (с. 23-25). 3. Установите Х равным 1. 4. Начните чтение главы Х. Не читайте эпиграфы, помещенные в ее начале. 5. Вам интересен предмет этой главы7 Если да, перейдите к шагу. 7; если нет, перейдите к шагу 6. 6. ?1т < 2? Если нет, перейдите к шагу. 16; если да, то все-таки просмотрите главу. (В главах 1 и 2 содержится важный вводный материал, а также обзор основных методов программирования.
Эти главы следует хотя бы просмотреть, чтобы ознакомиться с условными обозначениями и компьютером И1Х.) 7. Начните чтение следующего раздела главы; но, если вы уже дошли до конца главы, перейдите к шагу 16. 8. Отмечен ли номер раздела символом ««а? Если да, то при первом чтении этот раздел можно пропустить (в нем рассматривается специальный вопрос, который интересен, но не имеет первостепенного значения). Вернитесь к шагу 7, 9.
Есть ли у вас наклонности к математике? Если математика для вас — китайская грамота, то перейдите к шагу 11; в противном случае перейдите к шагу 10. 10. Проверьте математические выкладки, выполненные в этом разделе (и сообщите автору о замеченных ошибках). Перейдите к шагу 12. 11. Если в текущем разделе содержится много математических выкладок, то лучше не читайте их. Том не менее вам следует ознакомиться с основными результатами раздела; они, квк правило, либо приводятся в самом начале раздела, либо выделены курсовом в самом конце сложной части текста. 12. Выполните рекомендуемые упражнения к разделу в соответствии с указаниями, приведенными в примечаниях к упражнениям (которые вы прочитали на шаге 2). 13.
Поработав над упражнениями в свое удовольствие, сравните полученные ответы с теми, которые приведены в соответствующем разделе в конце книги (если для этих задач даны ответы). Прочтите также ответы к упражнениям, над которыми у вас не было времени поработать. (Замечание. В большинстве случаев имеет смысл сначала прочесть ответ к упражнению н, а затем приступить к упражнению и + 1, поэтому шаги 12 и 13 обычно выполняются одновременно ) 14. Вы устали? Если нет, вернитесь к шагу 7. 13. Отправляйтесь спать.
А когда проснетесь, вернитесь к шагу 7. 16. Увеличьте Аг на 1. Если Л = 3, 3, 7, 9, 11 или 12, то возьмите следующий том этой серии книг. 17. Если У меныпе или равно 12, то вернитесь к шагу 4. 18. Поздравляю! Теперь постарайтесь убедить друзей в том, что необходимо приобрести экземпляр тома 1 и начать его читать. Сами же возвращайтесь к шагу 3.
ГодЕ твму, ктО ЧитаЕт тОЛ~Ко одну КниГУ. — джОРдЖ ГЕРБеРТ (БеОВВЕ НЕВВЕВТ), таси!а Ргииелсит, 1144 (1б40) Единственный недостаток всех литеоатуоных лдоиэведений в том, что они слишком длинны. — ВОВЕНАРГ (1ГАОЧЕМАВВПЕ5), Гтобех(олв, 628 (174б) Книги банальны. Гениальна только жизнь. — тОьадс НАРдейдь (тнОыА5 сАВ1Т1.е), уоигла1 (1взэ) ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ Рей~пинэ Обвлснение Чрезвычайно простое упражнение, ца которое можно ответить сразу же, если прочитанный материал понят. Упражнения подобного типа почти всегда можно решить "в уме". Простая задача, которая заставляет задуматься над прочитанным, но не представляет особых трудностей.
На ее решение вы затратите не больше минуты; в процессе решения могут понадобиться карандаш и бумага. Средняя задача, которая позволяет проверить, понял лн читатель основ- ные положения изложенного материала. Чтобы получить исчерпываю- щий ответ, может понадобиться примерно Ы-20 минут. Задача умеренной сложности. Для ее решения может понадобиться более двух часов (а если одновременно вы смотрите телевизор, то еще больше). ОО Упглжнкния, приведенные в этой серии книг, предназначены как для самостоятельной проработки, так и для семинарских занятий. Очень трудно и, наверное, просто невозможно выучить предмет, только читая теорию и не применяя ее для решения конкретных задач, которые заставляют задуматься о прочитанном.
Более того, мы лучше всего заучиваем то, до чего дошли самостоятельно, своим умом. Поэтому упражнения занимают важное место в данном издании, Я приложил немало усилий, чтобы сделать их как ьюжно более информативными, а также отобрать задачи, которые были бы не только поучительны, но и позволяли читателю получить удовольствие от их решения. Во многих книгах простые упражнения даются вперемешку с исключительно сложными, Это не всегда удобно, так как читателю хочется знать заранее, сколько времени ему придется затратить на решение задач 1иначе в лучшем случае он их только просмотрит). В качестве классического примера подобной ситуации можно привести книгу Ричарда Беллмана (БйсЬагд Ве!!п1ап) Динамическое программирование (М.; Изд-во иностр.
лиг., 19бО). Это очень важная, новаторская работа, но у нее есть один недостаток: в конце некоторых глав в разделе "Упражнения и научные проблемы" среди серьезных, еще нерешенных проблем, попадаются простейшие вопросы. Говорят, что кто-то однажды спросил д-ра Беллмана, как отличить упражнения от научяых проблем, и он ответил: "Если вы можете решить задачу, значит, это упражнение; в противном случае это научная проблема". Совершенно очевидно, что в книге, подобной этой, должны быть приведены и сложные научные проблемы, и простейшие упражнения. Поэтому, чтобы читатель не ломал голову; пытаясь отличить одно от другого, были введены рейтинги, которые определяют степень сложности каждого упражнения. Эти рейтинги имеют следующее значение.
Достаточно сложная или трудоемкая задача, которую вполне можно включить в план семинарских занятий. Предполагается, что студент должен справиться с ией, затратив не слишком много времени, и решение будет нетривиальным. Научная проблема, которая (насколько известно автору в момент написания книги) пока еще не получила удовлетворительного решения, хотя найти его пытались очень многие. Если вы нашли решение подобной проблемы, то опубликуйте его, более того, автор данной книги будет очень признателен, если ему сообщат решение как можно скорее (при условии, что оно правильно).
Интерполируя по этой "логарифмической" шкале, можно понять, что означает любой промежуточный рейтинг, Например, рейтинг 17 говорит о том, что упражнение немного проще, чем задача средней сложности. Если задача с рейтингом 50 будет впоследствии решена каким-либо читателем, то в следующих изданиях данной книги и в списке ошибок, опубликованных в 1п1егпе$, она может иметь рейтинг 45 (адрес %еб-страницы приводится на обороте титульной страницы).
Остаток от деления рейтинга на 5 показывает, какой объем рутинной работы потребуется для решения данной. задачи. Таким образом, для решения упражнения с рейтингом 24 может потребоваться больше времени, чем для упражнения с рейтингом Я5, но для последнего необходим более творческий подход. Автор очень старался правильно присвоить рейтинги упражнениям, но тому, кто составляет задачи, трудно предвидеть, насколько сложными они окажутся для кого-то другого.
К тому же одному человеку некая задача может показаться простой, а другому — сложной. Таким образом, определение рейтингов — дело достаточно субъективное и относительное. Я надеюсь, что рейтинги помогут вам получить правильное представление о степени трудности задач, но их следует воспринимать в качестве ориентира, а ие в качестве абсолюта. Эта книга написана для читателей с различным уровнем математической подготовки и научного кругозора, поэтому некоторые упражнения рассчитаны исключительно па тех, кто серьезно интересуется математикой или занимается ею профессионально. Если рейтингу предшествует буква И, значит, математические понятия и обоснования используются в упражнении в большей степени, чем это необходимо тому, кто интересуется в основном программированием алгоритмов. Если же упражнение отмечено буквами НМ, то для его решения необходимо знание высшей математики в большем объеме, чем дается в настоящей книге.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
