Cтраница 4
В приведенном описании алгоритма Евклида в качестве элементарных операций, на которые расчленяется процесс решения задачи, фигурирует вычитание двух чисел, сравнение двух чисел и перестановка двух чисел местами, нелегко понять, что это расчленение может быть продвинуто гораздо дальше. Например, указание 5 о вычитании двух обозреваемых чисел может быть само развернуто в систему указаний, описывающих алгоритмы вычитания двух чисел. Однако для большей простоты и привычности правил арифметических действий в подобных случаях дальнейшая детализация алгоритма не проводится. [46]
Он называется еще алгоритмом Евклида. Чтобы найти НОД двух чисел, делят большее число на меньшее, и если получается остаток, то делят меньшее число на остаток; если снова получается остаток, то делят первый остаток на второй. Так продолжают делить до тех пор, пока в остатке не получится нуль. Последний делитель и есть НОД данных чисел. [47]
В примере 2.9 описан алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел хну. [48]
Мы видели, что алгоритм Евклида 4.5.2 А для целых чисел можно легко переделать в алгоритм для нахождения наибольшего общего делителя многочленов. Можно ли подобным образом переделать бинарный алгоритм нахождения нод ( алгоритм 4.5.2 В), Чтобы он был применим к многочленам. [49]
Рассмотрим в качестве примера алгоритм Евклида. Задача, решаемая с помощью этого алгоритма, формулируется так: даны два целых положительных числа. [50]