Cтраница 2
Алгоритм Эвклида применим для любых значений пары чисел, что характеризует его массовость. Отысканием ответа решения получаем проявление другого свойства алгоритма - его результативности. В то же время это свойство позволяет получать сигнал о невозможности применения алгоритма Эвклида к некоторым значениям исходных данных, например к отрицательным или дробным числам. Наконец, предписываемый алгоритмом вычислительный процесс всегда и везде должен иметь однозначное толкование. [16]
Например, при вычислении функции factorial ( 3) в соответствии с рекурсивным описанием нужно вычислить factorial ( 2), factorial ( 1) и factorial ( 0); в этом случае рекурсия имеет глубину в три уровня. Для факториальной функции глубина рекурсии при любом заданном значении аргумента видна сразу. Однако это - исключение, а обычно глубина рекурсии не является очевидной даже при простейших описаниях. Например, рассмотрим алгоритм Эвклида для вычисления наибольшего общего делителя ( НОД) двух положительных целых чисел. [17]
Например, при вычислении функции factorial ( 3) в соответствии с рекурсивным описанием нужно вычислить factorial ( 2), factorial ( 1) и factorial); в этом случае рекурсия имеет глубину в три уровня. Для факториальной функции глубина рекурсии при любом заданном значении аргумента видна сразу. Однако это - исключение, а обычно глубина рекурсии не является очевидной даже при простейших описаниях. Например, рассмотрим алгоритм Эвклида для вычисления наибольшего общего делителя ( НОД) двух положительных целых чисел. [18]
Наиболее важные алгоритмы ( с точки зрения вычислительной сложности) должны быть в некотором смысле особенными; они в основном дают удивительно быстрый способ решения какой-нибудь простой или важной задачи. Ниже я перечисляю некоторые из наиболее интересных алгоритмов, изобретенных начиная с 1960 г. ( Кстати, интересно порассуждать о том, какие именно алгоритмы признаны за это время наиболее важными. Бесспорно, арифметические операции, -, , - г-над десятичными числами являются основными. После этого, я думаю, следующими кандидатами являются быстрая сортировка и поиск, исключение по Гауссу, алгоритм Эвклида и симплексный алгоритм. [19]
Пришло время разобраться, почему алгоритм дает правильный ответ и почему он завершает свою работу. Как и подразумевается названием, расширенный алгоритм Эвкли-да представляет собой просто алгоритм Эвклида из предыдущего параграфа, дополненный инструкциями для вычисления значений ж и у. Поэтому он останавливается, и наибольший общий делитель составляет часть выходных данных. Кроме того, в каждой строке числа из столбцов х та у удовлетворяют равенству типа (6.1), в котором число d заменено остатком из соответствующей строки. В частности, равенство (6.1) выполняется, если в качестве а и / 3 взять числа из столбцов ж и у строки, отвечающей последнему ненулевому остатку. Расширенный алгоритм Эвклида приводит к следующей теореме. [20]