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