Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

лиг., 1960). Это очень важная, новаторская работа„по у пее есть един недостаток; в конце некоторых глав в разделе "Упражнения и научные проблемы" среди серьезных, еще нерешенных проблем приводятся простейшие вопросы. Говорят, что кто-то однажды спросил д-ра Беллмана, как отличить упражнения от научных проблем, и он ответил: "Если вы можете решить задачу, значит, это упражнение; в противном случае это научная проблема". Совершенно очевидно, что в книге, подобной этой,.

должны быть приведены н сложные научные проблемы, и простейшие упражнения. Поэтому, чтобы читатель не ломал гозову, пытаясь отличить одно от другого, были введены рейтинги, которые определяют степень сложности каждого упражнения. Эти рейтинги имеют следующее значение. Рейшннг Обвлснение Чрезвычайно простое упражнение, на которое можно ответить сразу же, если прочитанный материал понят. Упражнения подобного типа почти исегда можно решить "в уме". Простая задача, которая заставляет задуматься над прочитанным, ио ие представляет особых трудностей. На ее решение вы затратите не больше минуты; в процессе решения могут понадобиться карандаш и бумага.

Средняя задача. которая позволяет проверить, понял ли читатель основные положения изложенного материала. Чтобы получить исчерпывающий ответ, может понадобиться примерно 15-20 минут. Задача умеренной сложности. Для ее решения может понадобиться более двух часов (а если одновременно вы смотрите телевизор, то еще больше). Достаточно сложная или трудоемкая защгча, которую вполне можно включить в план семинарских занятий.

Предполагается, что студент должен справиться с ней, затратив ие слишком много времени, н решение будет нетривиальным. Научная проблема, которая (насколько известно автору в момент написания книги) пока еще ие получила удовлетворительного решения, хотя найти его пытались очень многие. Если вы нашли решение подобяой проблемы, то опубликуйте его; более того, автор данной книги будет очень признателен, если ему сообщат решение как можно скорее (при условии, что оно правильно). Интерполируя по этой "логариФмической" шкале, можно понять, что означает любой промежуточный рейтинг. Например, рейтинг 17 говорит о том, что упражнение немного проще, чем задача средней сложности. Если задача с рейтингом ЛО будет впоследствии решена какнм-тобо читателем, то в слелующих изданиях данной книги и в списке ошибок, опубликованных в )псегпес, оиа может иметь рейтинг ~Б (адрес ууеЬ.страницы приводится на обложке книги).

Остаток ат деления рейтинга на 5 показывает, какой объем рутинной работы потребуется для решения данной задачи. Таким образом, для выполнения упражнения с рейтингом й( может потребоваться больше времени, чем для упражнения с рейтингом йй, но для последнего необходим более творческий подход. Автор очень старался правильно присвоить рейтинги упражнениям, но тому, кто составляет задачи, трудно предвидеть, насколько сложными они окажутся для кого-то другого. К тому же одному человеку некая задача может показаться простой, а другому — сложной.

Таким образом, определение рейтингов — дела достаточно субъективное и относитштьное. Я надеюсь, что рейтинги помогут вам получить правильное представление о степени трудности задач, ио их следует воспринимать в качестве ориентира, а не в качестве абсолюта. Эта книга написана для читателей с различяым уровнем математической подготовки и научного кругозора, поэтому некоторые упражнения рассчитаны исключительно на тех, кто серьезно интересуется математикой или занимается ею профессионально.

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

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

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

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

УПРАЖНЕНИЯ 1. [ОО) Что означает рейтинг Мйдт 2. (10] Какое значение для читателя имеют упражнения, которые приводятся в учебникаху 3. (т)Лщ докажите, что если и — целое чншю, ц > 2, то уравнение х" + у" = хн неразрешимо в целых положительных числах х, у, х. двух часов ежедневных упражнений ... достаточно, чтобы и клячу обучить атой работе, — м. х. маха (м, н. маном), выездка лошадей (тне наобу ншзе воо«) (твен) ГЛАВА 5 СОРТИРОВКА ьгет дела, коего Устройство было бы труднее, ведение опаснее, а успех сомнительнее, нежели замена стаоых порядков новыми.

— никколо мдкидйелли, государь (1э1з) "Но мы не успеем просмотреть все номера автомобилей", — возразил дрейк. "А иам и не нужно этого делать, Пап. Мы просто Расположим их по порядку и поищем одинаковыа" — пв ри мейсон, из тпе сазе ог гпе Апдгу моцгпег (1ээ1) компьютер "тгеезогг" г при иовом эюмпьютерном подходе" к изучвииЮ природы вы получите воаможнОСть быстро распознавать более 260 видов деревьев США, Аляски и Канады, включал пальмы, растительность пустынь и прочую "зкзотикус чтобы определить породу деРева, достаточно пРосто вставить спицу. — Каталог Ебптцпб зсгепбйс Согпрапу (1964) В этой главк мы изучим вопрос, который часто возникает в программировании: переразмещение элементов в порядке возрастания или убьсэания.

Представьте, насколысо трудно было бы пользоваться словарем, если бы слова в нем не располагались в алфавитном порядке. Точно так же от порядка, в котором хранятся элементы в памяти компьютера, во многом зависит скорость выполнения и простота алгоритмов, предназначенных для их сбработки. Хотя в словарях слово "сортировк~" (вогйпй) определяется как процесс разделения объектов по виду или сорту, программисты т)ищиционно используют его в гораздо более узком смысле, обозначая им такую перестановку предметов, при которой они располагаются в порядке возрастания или убывания.

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

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

Характеристики

Список файлов книги