Итак, давайте в качестве примера разберем алгоритм Е. Предположим, что т = 119 и п = 544; начнем с шага El. (Сейчас можете просто следить за изложением, так как мы разберем алгоритм и подробно все выпишем.) Деление m на п в этом случае вьшолняется просто, даже очень просто, так как частное равно нулю, а остаток - 119. Таким образом, г 119. Переходим к шагу Е2. Поскольку г О, на этом шаге никакие действия не выполняются. На шаге ЕЗ присваиваем т 544, п <- 119. Очевидно, что если первоначально m < п, то частное на шаге El всегда оказывается равным нулю и в ходе вьшолнения алгоритма всегда происходит взаимный обмен значений переменных тип, хотя и таким громоздким способом. Поэтому можно добавить дополнительный шаг.

ЕО. [Гарантировать, что т > п.] Если m < п, то выполнить взаимный обмен т 44 п.

В результате алгоритм из.менится незначительно (разве что увеличится на один шаг), но зато время его вьшолнения сократится примерно в половине случаев.

Вернемся к шагу El. Находим, что у = 4-, поэтому г 68. В результате на шаге Е2 снова не выполняются никакие действия, а на шаге ЕЗ присваиваем т <- 119, п 68. В следующих циклах сначала получаем г 51 и m <- 68, п f- 51, а зате.м - г 17 и m 51, п 17. Наконец, в результате деления 51 на 17 получаем г 0. Таким образом, на шаге Е2 выполнение алгоритма прекращается. Наибольший общий делитель 119 и 544 равен 17.

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

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

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

2) Определенность. Каждый шаг алгоритма должен быть точно определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая. Я надеюсь, что алгоритмы, приведенные в данной книге, удовлетворяют этому критерию. Но дело в уом, что они описываются обычным языком, и поэтому существует возможность неточного понимания

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

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

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

4) Вывод. У алгоритма есть одно или несколько выходных данных, т. е. величин, имеющих вполне определенную связь с входными данными. У алгоритма Е имеется только одно выходное значение, а именно - п, получаемое на шаге Е2. Это наибольший общий делитель двух входных значений.

(Можно легко доказать, что это число действительно является наибольшим общим делителем. После шага Е1 имеем

т = qn-\-r,

где q - некоторое целое число. Если г = О, то m кратно п и, очевидно, в этом случае п - наибольший общий делитель тип. Если г О, то любой делитель обоих чисел тип должен быть также делителем т - qn - г н любой делитель п и г - также делителем qn -\- г = т. Таким образом, множество делителей чисел {т,п} совпадает с множеством делителей чисел {п,г}. Следовательно, пары чисел {т,п} и {п,г} имеют один и тот же наибольший общий делитель. Таким образом, шаг ЕЗ не изменяет ответа исходной задачи.)

5) Эффективность. Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бумаги. В алгоритме Е используются только следующие операции: деление одного целого положительного числа на другое, сравнение с нулем и присвоение одной переменной значения другой. Эти операции являются эффективными, так как целые числа можно представить на бумаге с помощью конечного числа знаков и так как существует по меньшей

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

Давайте попробуем сравнить понятие "алгоритм" с рецептом из кулинарной книги. Предполагается, что рецепт обладает свойством конечности (хотя и говорят, что "кто над чайником стоит, у того он не кипит"), имеет входные данные (такие, например, как яйца, мука и т. д.) и выходные данные (обед "на скорую руку" и т. п.), но хорошо известно, что ему не хватает определенности. Инструкции из кулинарных рецептов очень часто бывают неопределенными, например: "Добавьте щепотку соли". "Щепотка" определяется как количество, "меньшее i/g чайной ложки", и что такое соль, вероятно, тоже известно всем. Но куда именно нужно добавить соль - сверху? сбоку? Инструкции "Слегка потрясите, пока смесь не станет рассыпчатой" и "Подогрейте коньяк в маленькой кастрюльке" будут вполне понятны опытному повару, но они не годятся для алгоритма. Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер. Тем не менее программист может многому научиться, прочитав хорошую поваренную книгу. (Честно говоря, автор едва устоял перед искушением назвать настоящий том "Поваренная книга программиста". Но, может, когда-нибудь он попытается написать книгу под названием "Алгоритмы для кухни".)

Следует отметить, что для практических целей ограничение, состоящее в конечности алгоритма, в сущности, является недостаточно жестким. Используемый на практике алгоритм должен иметь не просто конечное, а достаточно ограниченное, разумное число шагов. Например, существует алгоритм определения того, может ли игра в шахматы всегда быть выиграна белыми при условии, что не было сделано ни одной ошибки (см. упр. 2.2.3-28). Этот алгоритм позволил бы решить проблему, представляюшую огромный интерес для тысяч людей, но можно биться об заклад, что окончательный ответ на данный вопрос мы не узнаем никогда. Все дело в том, что для выполнения указанного алгоритма требуется невероятно большой промежуток времени, хотя сам алгоритм и является конечным. В главе 8 будут-обсуждаться конечные числа, которые велики настолько, что, в сущности, находятся за пределами нашего понимания*.

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

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

* Глава 8 не входит в данное трехто.мное издание. - - Прим. ред.