Д. Кнут - Искусство программирования том 1 (1119450), страница 5
Текст из файла (страница 5)
Но пометка НМ совсем необязательно означает, что упражнение трудное. Перед некоторыми упражнениями стоит стрелка "ь", которая означает, что опи особенно поучительны и их очень рекомендуется выполнить. Само собой разумеется, никто не ожидает, что читатель (или студент) будет решать все задачи, поэтому наиболее важные из иих и были выделены. Но это ни в коем случае не означает, что другие упражнения выполнять не стоит! Каждый читатель должен хотя бы попытаться решить все задачи, рейтинг которых меньше или равен 10. Стрелки помогут выбрать задачи с более высокими рейтингами, которые следует решать в первую очередь. К большинству упражнений приведены ответы, помещенные в отдельном разделе в конце книги.
Пожалуйста, пользуйтесь ими разумно: ответ смотрите только Условные обозначения ,00 Простейшее (ответ дать немедленно) 10 Простое (на одну минуту) 00 Средней трудности (иа четверть часа) 80 Повышенной трудности 40 Высокой трудности 50 Научная проблема Рекомендуется М С математическим уклоном НМ Требует знания высшей мате- матики УПРАЖНЕНИЯ 1. )00) Что означает рейтинг М30? 2. )10) Какое значение для читателя имеют упражнения, которые приводятся в учебниках? 3, (Ц) Докажите, что 13а = 2197. Обобщите ответ. (Скучных задач, подобных этой, автор старался избегать.) 4. (НМ45) Докажите, что если и — целое число, и > 2, то уравнение х" + рк = ак неразрешимо в целых положительных числах х, р, х.
ааы обсудили этот вопрос со всех стооон. Перед нами факты, изложенные систематично и по порядку, — ЭРКЮЛЬ ПУАРО (НЕРСО~ Е РО!РОТ), убийство в восточном экспрессе (1934) после того, как приложите все усилия, чтобы решить задачу самостоятельно, либо если у вас совершенно нет времени иа ее решение. Ответ будет поучителен и полезен для вас только в том случае, если вы ознакомитесь с ним после того, как найдете свое решение или изрядно потрудитесь над задачей. Ответы к задачам излагаются очень кратко и схематично, так как предполагается, что читатель честно пытался решить задачу собственными силами.
Иногда в приведенном решении дается меньше информации, чем спрашивалось, но чаще бывает наоборот. Вполне возможно, что полученный вами ответ окажется лучше того, который помещен в книге, или вы найдете ошибку в ответе. В таком случае автор был бы очень признателен, если бы вы как можно скорее подробно сообщили ему об этом; тогда в последующих изданиях книги будет опубликовано более удачное решение, а также имя его автора. Решая задачи, вы, как правило, можете пользоваться ответами к предыдущим упражнениям, за исключением случаев, когда это будет оговорено особо. Рейтинги упражнениям присваивались в расчете именно на это, и вполне возможно, что рейтинг упражнения и + 1 ниже рейтинга упражнения и, даже если результат упражнения и является его частным случаем.
ОСНОВНЫЕ ПОНЯТИЯ многие не сведущие в математике люди думают, что поскольку назначение аналитической машины Бзббиджэ (Ваььайе)— выдавать результаты в численном виде, то природа происходящих в ней процессов должна быть арифметической и численной, а не алгебраической и аналитической. мо они ошибаются. машина мгикет упорядочивать н комбинировать числовые значения так же, как и буквы или любые другие символы общего характера. В сущности, при выполнении соответствующих условий она моглэ бы выдавать Результаты и в алгебраиЧЕСКом ВИДЕ.
— августа лдл (лиапбта лгзд), графиня лавлейсч (соте!асе) (зв44) пРошу вас, Ради всего святого, сначала научитесь простому и только потом пеРеходите к сложному. — эпикте'Г (ЕР!Стетпб), Беседы !ХГЗ 1.1. АЛГОРИТМЫ Понятии алгоришлт является основным для всей области компьютерного программирования, поэтому начать мы должнгя с тщательного анализа этого термина. Олово "алгоритм" (а1йог1()тш) (иногда используется устаревшее слово чалгорифмч.— Прим. перев.) уже само по себе представляет большой интерес, На первый взгляд может показаться, будто кто-то собирался написать слово "логарифм" (1ояаг1(1тш), но случайно переставил первые четыре буквы. Этого слова еще не было в издании словаря Н'еЬвгег'в №и Игог1г) Р!сс!благу, вышедшем в 1957 году.
Мы находим там только устаревшую форму "а!дог!зть — старинное слово, которое означает "выполнение арифметических действий с помощью арабских цифр". В'средние века абакисты считали на абаках (счетных досках), а алгоритмики использовали ча!пог!яш". В эпоху Возрождения происхождение этого слова оказалось забытым.
Одни лингвисты того времени пытались объяснить его значение путем сочетания " Дочь великого английского поэта Дж, Г. Байрона, которую считают основоположницей программнрозяння. Большинство млей н принципов прогряммнрпзяння'лля янялнтнческой няшины Ьзббнлжя было рассмотрено в ее книге "Ксмментярнн". Прим. перев. слов а1дсгоя (больной] и аН1Ьтая (число], другие не соглашались с таким толкованием и утверждали, что это слово происходит от кК!п8 А!бог о1 Саяс!1е". Наконец историки математики обнаружсали истинное происхождение слова ка!8ог!яш": оно берет начало от имени автора знаменитого персидского учебника по математике, АЬО 'АЬс1 А11аЬ МиЬапппас1 !Ьп Мияа а1-К!пчааг!гш! (Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми) (ок. 825 г.), означающего буквачьно "Отец Абдуллы, Мухаммед, сын Мусы, уроженец Хорезма"*.
Аральское море в Центральной Азии когда-то называлось озером Хорезм, и район Хорезма (КЬжапгш) расположен в бассейне реки Амударьи южнее этого моря. Аль-Хорезми написал знаменитую книгу КйаЬ а1-!аЬг н а'1-спидаба)а (Китаб аль-джебр валь-мукабала — "Книга о восстановлении и противопоставлении" ). От названия этой книги, которая была посвящена решению линейных и квадратных уравнений, произошло еще одно слово — "алгебра".
(О жизни и научной деятельности аль-Хорезми речь идет в работе Н. Еешапе!с, Ьессиге стосея т Сошригег Бс!енсе 122 (1981), 1-81.] Постепенно форма и значение слова а1догмт исказились; как объясняется в словаре Ох1Ьгс! Епб!!я!с 3Э!с1!ипату, зто слово "претерпело множество псевдоэтимологических искажений, включая последний вариант а!допййт, где произошла путаницак с корнем слова греческого происхождения аП!!сте11с. Этот переход от ка!8опяши к ка18опСЬспи кажется вполне закономерным ввиду того, что происхождение рассматриваемого слова было полностью забыто.
В старинном немецком математическом словаре Ъо!1ясапс!!8ея та!бета!!ясЬея Ьех!соп (Ьесрлй, 1747) дается следующее определение слова а1уогТЬтиес "Этот термин включает в себя понятие о четырех типах арифметических операций, а именно: о сложении, умножении, вычитании и делении"'. Латинское выражение а1доП1Бспия си!Си!!еяста1ся в то время использовалось для определения "способов выполнения действий с бесконечно малыми величинами, открытых Лейбницем (ЬесЬшг)". К 1950 году слово "алгоритм" чаще всего ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя двух чисел. Этот алгоритм приведен в книге Евклида (Еис!!с() Начала (книга 7, предложения 1 и 2). Думаю, имеет смысл привести здесь описание этого алгоритма.
Алгоритм Е (Алгоритпм Евклида). Даны два целых положительных числа т и и. Требуется найти их наибольший обсций делитель, т. е. наибольшее целое положительное число, которое нацело делит оба числа т и и. Е1. [Нахождение остатка.] Разделим т на и, и пусть остаток от деления будет равен г (где 0 < г < и). Е2. (Сравнение с нулем.] Если г = О, то выполнение алгоритма прекращается; ив искомое значение. ЕЗ. (Замещение.] Присвоить т с — и, и с — г и вернуться к шагу Е1. $ Разумеется, у Евклида этот алгоритм сформулирован не совсем так. Приведенная выше формулировка иллюстрирует стиль, в котором алгоритмы будут представлены на протяжении всей этой книги.
Каждому рассматриваемому алгоритму присваивается идентифицирующая буква (в предыдущем примере использовалась буква Е), а шагам алгоритма — эта ь В русскоязычных источниках зто историческое лицо обычно унолсинается оод именем "аньХорюмн .— Прим. нерее. же буква в сочетании с числом (Е1, Е2, ЕЗ). Главы книги подразделяются на пронумерованные разделы; внутри раздела алгоритмы обозначаются только буквами. Но когда на эти алгоритмы делаются ссылки из других разделов, то к букве присоединяется номер соответствующего раздела.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
