AOP_Tom1 (1021736), страница 6

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

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

Так, например, операцию 'и <- г, гп < — г" моюкно записать как кв ~- гп ~- г". Операцию взаимного обмена значениями двух переменных можно записать так: "Обмен т <-> и". Ее можно записать и с помощью новой переменной 1 следующим образом: "Присвоить 1+- т, т ~ — и, и +- 1".

Выполнение алгоритма начинается с шага, имеющего наименьший номер (обычно это шаг 1). Затем последовательно выполняются следующие шаги, если нет каких-либо указаний, нарушающих естественный порядок выполнения. На шаге ЕЗ указание "Вернуться к шагу Е1" явным образом определяет порядок вычислений. На шаге Е2 действию предшествует условие "Если г = 0" и если г ф О, то оставшаяся часть предложения не применяется и нет указаний на выполнение в этом случае каких-либо действий. Конечно, мы могли бы добавить дополнительное предложение "Если г ф О, то перейти к шагу ЕЗ", но это совершенно излишне.

Жирная вертикальная черточка "з ", помещенная в конце шага ЕЗ, обозначает окончание алгоритма и продолжение текста. Итак, мы обсудили практически все соглашения об обозначениях, которые используются в алгоритмах, приведенных в книге. Осталось выяснить только, как обозначать величины с индексами (нли "подстрочными' индексами), которые являются элементами упорядоченного массива. Предположим, у нас есть и величин: сы ею..., и„. Для обозначения у-го элемента вместо записи е часто используется запись и[1]. Аналогично массив иногда предпочитают обозначать как а~1,Я, вместо того чтобы использовать два подстрочных индекса, как в записи а; .. Иногда для обозначения переменных используются имена, состоящие из нескольких букв, обычно прописных.

Например, ТЕИР может быть именем переменной, использующейся для временного хранения вычисленного значения, а Рй1МЕ П13 может обозначать К-е простое число, и т. д. До сих пор мы говорили о форме зитшси алгоритмов, а теперь давайте попробуем выполмитпь один из них.

Хочу сразу заметить, что читателю не следует рассчитывать на то, что алгоритмы можно читать, как роман. Такое чтение приведет к тому, что вам будет трудно понять, что же на самом деле происходит при выполнении алгоритма. Чтобы проверить алгоритм, в нем нужно разобраться, и лучший способ понять, как он работает, — испытать его. Поэтому я предлагаю вам взять карандаш и бумагу и прорабатывать от начала до конца каждый алгоритм сразу же, как только он встретится в тексте. Обычно к примеру алгоритма прилагается схема, в противном случае читатель легко сможет представить ее. Это самый простой и доступный способ разобраться в алгоритме, в то время как все остальные подходы оказываются неэффективными. Итак, давайте в качестве примера разберем алгоритм Е.

Предположим, что т = 119 и и = 544; начнем с шага Е1. (Сейчас можете просто следить за изложением, так как мы разберем алгоритм и подробно все выпишем.) Деление т на и в этом случае выполняется просто, даже очень просто, так как частное равно нулю, а остаток— 119. Таким образом, т 4 — 119. Переходим к шагу Е2. Поскольку г ф О, на этом шаге никакие действия не выполняются.

На шаге ЕЗ присваиваем т 4 — 544, и 4 — 119. Очевидно, что если первоначально т ( п, то частное на шаге Е1 всегда оказывается равным нулю и в ходе выполнения алгоритма всегда происходит взаимный обмен значений переменных т и и, хотя и таким громоздким способом. Поэтому можно добавить дополнительный шаг. ЕО.

1Гарантировать, что т > и.) Если т ( и, то выполнить взаимный обмен т 4+ и, В результате алгоритм изменится незначительно (разве что увеличится на один шаг), но зато время его выполнения сократится примерно в половине случаев. Вернемся к шагу Е1. Находим, что — „д — — 4 — „д, поэтому г 4 — 68. В результате 544 бб на шаге Е2 снова не выполняются никакие действия, а на шаге ЕЗ присваиваем т +- П9, и 4- 68. В следующих циклах сначала получаем т 4- 51 и т 4- 68, и 4- 51, а затем — г 4- 17 и т 4 — 51, и 4 — 17. Наконец, в результате деления 51 на 17 получаем т 4 — О. Таким образом, на шаге Е2 выполнение алгоритма прекращается. Наибольший общий делитель 119 и 544 равен 17. Вот что такое алгоритм.

Современное значение слова "алгоритм" во многом аналогично таким понятиям, как рецепт, процесс, метод, способ, процедура, программа, но все-таки слово "а!8оНбйш" имеет дополнительный смысловой оттенок. Алгоритм — это не просто набор конечного числа правил, задающих последовательность выполнения операций для решения задачи определенного типа. Помимо этого, он имеет пять важных особенностей.

1) Конечность. Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов. Алгоритм Е удовлетворяет этоллу условию, потому что после шага Е1 значение г меньше, чем и. Поэтому если г ~ О, то в следующем цккле на шаге Е1 значение и уменьшается. Убываклцая последовательность положительных целых чисел имеет конечное число членов, поэтому шаг Е1 может выполняться только конечное число раз для любого первоначально заданного значения и. Но имейте в виду, что количество шагов может быть сколь угодно большим; выбор слишком больших значений т и и приведет к тому, что шаг Е1 будет выполняться более ллиллиона раз.

Процедура, обладающая всемк характеристиками алгоритма, за исключением, возможно, конечности, называется методом вычислений. Евклид (Еис!Ы) предложил не только алгоритм нахождения наибольшего общего делителя, но и аналогичное ему геометрическое построение "наибольшей общей меры" длин двух отрезков прямой; это уже метод вычислений, выполнение которого не заканчивается, если заданные длины оказываются несоизмеримыми. 2) Опредслсллность. Каждый шаг алгоритма должен быть точно определен.

Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая. Я надеюсь, что алгоритмы, приведенные в данной книге, удовлетворяют этому критерию. Но дело.в 7олц что онн описываются обычным языком, и поэтому существует возможность неточного пош~ллапня читателем мысли автора. Чтобы преодолеть зто затруднение, для описания алгоритмов были разработанй формально определенные ломки программирования, или машинные языки, в которр|х каждый оператор имеет строго определенное значение. Многие алгоритмы в этой книге даются как на обычном языке, так и на языке программирования. Метод вычислений, выраженный на языке программирования, называется программой. Рассмотрим в качестве примера алгоритм Е. Применительно к шагу Е1 критерий определенности означает, что читатель обязан точно понимать, что значит разделить п1 на п и что такое остаток.

Но в действительности нет никакого общепринятого соглашения по поводу того, что это означает, если т и и не являются целыми положительными числами. Каким будет остаток от деления — 8 на — к? Что понимать под остатком от деления 59/13 на нуль? Поэтому в данном случае критерий определенности означает следующее: мы должны быть уверены, что в каждом случае выполнения шага Е1 значениями т и и всегда будут целые положительные числа.

Если сначала по предположению это верно, то после шага Е1 г — это целое неотрицательное число; при условии перехода к шагу Е3 оно является также ненулевым. Таким образом, поставленное требование выполнено и т и и— это действительно целые положительные числа. 3) Ввод. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных, т. е. величин, которые задаются до начала его работы или определяются динамически во время его работы. Эти входные данные берутся из определенного набора объектов.

Например, в алгоритме Е есть два входных значения, а именно— т и и, которые принадлежат множеству целых положительных чисел. 4) Вывод. У алгоритма есть одно или несколько выходных даиимх, т. е. величин, имеющих вполне определенную связь с входными данными. У алгоритма Е имеется только одно выходное значение, а именно — и, получаемое на шаге Е2. Это наибольший общий делитель двух входных значений. (Можно легко доказать, что это число действительно является наибольшим общим делителем. После шага Е1 имеем где о — некоторое целое число. Если г = О, то т кратно п и, очевидно, в этом случае п — наибольший общий делитель т и и.

Если г ф О, то любой делитель обоих чисел т и и должен быть также делителем т — дп = г и любой делитель и и г — также делителем оп + г = т. Таким образом, множество делителей чисел 1гп, и) совпадает с множеством делителей чисел 1п, г). Следовательно, пары чисел ггп, и) и )п, г) имеют один и тот же наибольший общий делитель. Таким образом, шаг Е3 не изменяет ответа исходной задачи,) 5) Э44ективность. Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бу маги.

В алгоритме Е используются только следующие операции: деление одного целого положительного числа на другое, сравнение с нулем и присвоение одной переменной значения другой. Эти операции являются эффективными, так как целые числа можно представить на бумаге с помощью конечного числа знаков и так как существует по меньшей мере один способ (валгоритм деления") деления одного целого числа на другое, Но те же самые операции были бы неэ44ектввными, если бы они выполнялись над действительными числами, представляющими собой бесконечные десятичные дроби, либо над величинами, выражающими длины физических отрезков прямой, которые нельзя измерить абсолютно точно. Приведем еще один пример неэффективного шага: нЕсли 4 — это наиболыпее целое п, при котором существует решение уравнения ш" + хи+ у" = дн для целых положительных чисел и>, х, у и д, то перейти к |лагу Е4'.

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

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

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