Cтраница 1
Алгоритм Эвклида применим для любых значений пары чисел, что характеризует его массовость. Отысканием ответа решения получаем проявление другого свойства алгоритма - его результативности. В то же время это свойство позволяет получать сигнал о невозможности применения алгоритма Эвклида к некоторым значениям исходных данных, например к отрицательным или дробным числам. Наконец, предписываемый алгоритмом вычислительный процесс всегда и везде должен иметь однозначное толкование. [1]
Алгоритм Эвклида предназначен для вычисления наибольшего общего делителя двух натуральных чисел, и мы посвятим начало этого параграфа подробному определению наибольшего общего делителя. [2]
У алгоритма Эвклида, описанного в предыдущем параграфе, есть еще один вариант, более мощный. Мощный в данном случае не означает более быстрый. [3]
Напомним, что алгоритм Эвклида состоит из последовательности делений с остатком. Наибольший общий множитель представляет собой последний ненулевой остаток в этой последовательности. [4]
Ук 1ж1сгс глубину рекурсии алгоритма Эвклида при вводе двух [ тослеиователь - ы чисс. [5]
По существу, такая программа реализует расширенный алгоритм Эвклида. [6]
Сам НОД может быть найден с помощью алгоритма Эвклида, подобно тому как определяется НОД двух целых чисел. Следует только подчеркнуть, что в условиях приближенных вычислений, когда коэффициенты многочлена известны с некоторой точностью и все действия выполняются с неизбежным округлением, кратный корень может оказаться неотличимым от близких, но различных корней. [7]
Свойство 3 доказывается с использованием свойств 1, 2 и алгоритма Эвклида. [8]
Кроме того, приведенный метод решения линейных сравнений легко применим, поскольку использует только расширенный алгоритм Эвклида. Однако, когда решения будут получены, у нас могут возникнуть несколько поводов для удивления. [9]
Циклические программы применяются не только в области решения экономических задач, но и при обработке иной информации. Алгоритм Эвклида также содержит циклы вычислений, прекращаемые в случае установления равенства двух сравниваемых чисел. [10]
Именно поэтому новая процедура называется расширенным алгоритмом Эвклида. Приводимый здесь вариант этого алгоритма принадлежит Кнуту, автору знаменитой книги Искусство программирования. [11]
Пришло время разобраться, почему алгоритм дает правильный ответ и почему он завершает свою работу. Как и подразумевается названием, расширенный алгоритм Эвкли-да представляет собой просто алгоритм Эвклида из предыдущего параграфа, дополненный инструкциями для вычисления значений ж и у. Поэтому он останавливается, и наибольший общий делитель составляет часть выходных данных. Кроме того, в каждой строке числа из столбцов х та у удовлетворяют равенству типа (6.1), в котором число d заменено остатком из соответствующей строки. В частности, равенство (6.1) выполняется, если в качестве а и / 3 взять числа из столбцов ж и у строки, отвечающей последнему ненулевому остатку. Расширенный алгоритм Эвклида приводит к следующей теореме. [12]
Мы должны показать справедливость утверждения леммы. Воспользуемся, однако, сначала этой леммой и покажем, что последний ненулевой остаток в алгоритме Эвклида действительно равен наибольшему общему делителю. [13]
Оба они были известны математикам Древней Греции - они содержатся в Началах Эвклида, написанных около 300 г. до н.э. Алгоритм деления предназначен для вычисления неполного частного и остатка при делении двух целых чисел. Алгоритм Эвклида вычисляет наибольший общий делитель двух целых чисел. [14]
Эвклид приводит его в предложениях 1 и 2 книги VII своих Элементов. Алгоритм Эвклида действует следующим образом. Если r О, то разделим Ъ на г с остатком; пусть га - остаток второго деления. Аналогично, если г % ф О, то разделим т на г % и получим новый остаток гз - Таким образом, г-ый цикл алгоритма состоит из одного деления с остатком, причем делимое равно остатку, полученному в ( г - 2) - ом цикле, а делитель - остатку, полученному в ( г - 1) - ом цикле. [15]